【GDKOI】2021提高Day2
提高組 第二試
2021 年 1 月 30 日
注意事項
- 嚴格按照題目所要求的格式進行輸入、輸出，否則嚴重影響得分。
- 題目測試資料有嚴格的時間限制，逾時不得分。
- 輸入檔案格式不用判錯；輸入輸出檔案名均已給定，不用鍵盤輸入。
- 送出檔案夾及儲存方式請參考《考生注意事項》。評測以源程式為準。
- 評測環境為 NOI 系列活動标準競賽環境，編譯器版本為 g++ 4.8.4。
- 對于 C++ 選手，64 位整數輸入輸出格式為 %lld。
-
本次競賽的最終解釋權歸 GDOI 評委會所有。
試題名稱 遊戲 群島 抄寫 堆
送出檔案名 game.cpp island.cpp copy.cpp heap.cpp
輸入檔案名 game.in island.in copy.in heap.in
輸出檔案名 game.out island.out copy.out heap.out
時間限制 1s 1s 1s 2s
空間限制 512MB 512MB 512MB 512MB
編譯選項 -O2
滿分 100 100 100 100
第 1 頁 共 7 頁
GDKOI 2021 TG Day2
第一題 遊戲
送出檔案: game.cpp
輸入檔案: game.in
輸出檔案: game.out
時間空間限制： 1s, 512MB
現在時間是晚上 23:00，您終于把所有的 DDL 給解決了。
于是您打算玩一下遊戲來愉悅身心。
您發現天梯快結算了，于是您打算快速沖到低保。
您現在有 0 顆星，獲得 n 顆星即為低保。每局遊戲勝利可以獲得一顆星，失敗則扣除一顆星。特别地，
當您持有 0 顆星時不再進行扣除。
為了友善，我們簡化掉對局的過程，當您持有 i 顆星的時候，您獲勝的機率為 pi。
您想知道，要沖到低保，期望需要進行多少次對局。出于特殊的考慮，您隻需要知道答案對 998244353 取
模之後的結果
輸入格式
第一行一個整數 n，表示低保所需要的的星數。
接下來 n 行，每行兩個整數 xi
, yi (i = 0, 1, · · · , n n 1)，表示機率 pi = xi yi 。
輸出格式
輸出一行一個整數，表示答案對 998244353 取模之後的結果。
換句話說，若答案可以表示為有理數 pq，則你需要輸出 d ∈ [0, 998244353)，滿足 dq ≡ p (mod 998244353)。
樣例資料
game.in game.out
2
1 2
1 2
6
資料範圍
對于 30% 的資料，n ≤ 100
對于另 30% 的資料，xi = 1, yi = 2
對于所有資料，1 ≤ n ≤ 106, 1 ≤ xi ≤ yi < 998244353
第 2 頁 共 7 頁
GDKOI 2021 TG Day2
第二題 群島
送出檔案: island.cpp
輸入檔案: island.in
輸出檔案: island.out
時間空間限制： 1s, 512MB
您來到了一處不知名的群島，島嶼從 1 到 n 編号。
您可以通過單向傳送門來在島嶼間穿行。出于當地的習俗，島嶼 i 上隻有通往島嶼 i + 1 和島嶼 ai 的兩
扇單向傳送門。
剛開始時，您在編号為 x 的島上，而您希望前往編号為 1 的島去完成任務，不過您發現這些傳送門并不
一定能把您傳送到 1 号島上，為了友善行動，您希望前往能到達的編号最小的島。
由于時空亂流的影響，島嶼之間的傳送門可能會發生變化。
您需要盡快解決這個問題。
輸入格式
第一行兩個整數 n, m，表示島嶼和事件的數量。
第二行 n 個整數，表示 a1, · · · , an。
接下來 m 行，每行第一個整數 type 表示事件的類型，如果 type = 1，接下來兩個整數 x, y，表示 ax 變
化為 y；如果 type = 2，接下來一個整數 x，表示詢問的起點。
輸出格式
對于每個詢問，輸出一行表示答案。
樣例資料
island.in island.out
4 3
4 1 4 3
2 4
1 3 2
2 4
31
資料範圍
對于所有資料，滿足 n, m ≤ 105, 1 ≤ ai ≤ n。
子任務 1（共 20 分）：n, m ≤ 100；
子任務 2（共 20 分）：type = 2；
子任務 3（共 60 分）：無特殊限制。
第 3 頁 共 7 頁
GDKOI 2021 TG Day2
第三題 抄寫
送出檔案: copy.cpp
輸入檔案: copy.in
輸出檔案: copy.out
時間空間限制： 1s, 512MB
現在你需要抄寫一段話，這段話是由若幹個對稱字元（不超過 26 種對稱字元，為友善表示，使用 aa z
表示這些字元）構成的，每抄寫一個字元 ch，你就需要花費 costch 的時間。
作為一名學生，你當然掌握了一種投機取巧的方法——你可以對折紙張，使得之前抄寫的墨水複制到另
外一半，進而避免機械重複的工作。
形式化地說，假設現在的抄寫進度為 s1s2 · · · sm，則可以做下面的兩種操作：
• 操作一：在 sm 正後面對折紙張，使得抄寫進度變成 s1s2 · · · smsmsmm 1 · · · sk，1 ≤ k ≤ m； • 操作二：在 sm 正中間對折紙張，使得抄寫進度變成 s1s2 · · · smsmm 1 · · · sk，1 ≤ k < m。
而每次對折紙張的時間為 C，那麼最快隻需要多少時間你就能抄完一段話呢？
輸入格式
第一行兩個整數 n, C，表示需要抄寫的字元串的長度，以及對折需要的時間。
第二行 26 個整數，第 i 個整數 costi 表示抄寫第 i 個字元所需要的時間。
第三行一個長度為 n 的字元串 s，保證隻由小寫字母構成。
輸出格式
輸出一個整數，表示抄寫需要的最小時間。
樣例資料
copy.in copy.out
20 2
9 1 7 5 2 1 10 1 6 7 9 10 5 2 6 4 1
10 10 6 5 8 5 5 5 3
aaabedcecdebccadecbc
67
樣例解釋
初始 s=””
- 抄寫 a，花費 9，s=”a”；
- 選擇操作一，花費 2，s=”aa”；
- 選擇操作二，花費 2，s=”aaa”；
- 抄寫 b，花費 1，s=”aaab”；
- 抄寫 e，花費 2，s=”aaabe”；
-
抄寫 d，花費 5，s=”aaabed”； 第 4 頁 共 7 頁
GDKOI 2021 TG Day2
- 抄寫 c，花費 7，s=”aaabedc”；
- 抄寫 e，花費 2，s=”aaabedce”；
- 選擇操作二，花費 2，s=”aaabedcecdeb”；
- 抄寫 c，花費 7，s=”aaabedcecdebc”；
- 選擇操作一，花費 2，s=”aaabedcecdebcc”；
- 抄寫 a，花費 9，s=”aaabedcecdebcca”；
- 抄寫 d，花費 5，s=”aaabedcecdebccad”；
- 抄寫 e，花費 2，s=”aaabedcecdebccade”；
- 抄寫 c，花費 7，s=”aaabedcecdebccadec”；
- 抄寫 b，花費 1，s=”aaabedcecdebccadecb”；
-
選擇操作二，花費 2，s=”aaabedcecdebccadecbc”；
總代價為 67。
資料範圍
data id n = costi
, C ≤ 性質
1 10 109 無 2 1000 103 保證 ∀i ≤ j, si = sj 能推出 ∀i ≤ k ≤ j, sk = si 3 1000 105 無 4 1000 109 無 5 105 103 保證 ∀i ≤ j, si = sj 能推出 ∀i ≤ k ≤ j, sk = si 6 105 105 無 7 105 109 無 8 106 103 保證 ∀i ≤ j, si = sj 能推出 ∀i ≤ k ≤ j, sk = si 9 106 105 無
10 106 109 無 第 5 頁 共 7 頁
GDKOI 2021 TG Day2
第四題 堆
送出檔案: heap.cpp
輸入檔案: heap.in
輸出檔案: heap.out
時間空間限制： 2s, 512MB
衆所周知，堆是一種可以高效取出最小值的資料結構，其關鍵操作有上濾和下濾。
具體來說，堆是二叉樹的結構，線性的存儲在數組 Heap[1…n] 中，節點 i(1 ≤ i ≤ n) 的權值為 Heap[i]，
左兒子為 2i，右兒子為 2i + 1，滿足 Heap[i] ≤ min{Heap[2i], Heap[2i + 1]}。
對節點 x(1 ≤ x ≤ n) 執行上濾操作即不斷比較節點 x 以及其父親的權值，如果更小則交換，C++ 代碼
如下：
1 void Up(int x):
2 while(x>1 && Heap[x]<Heap[x>>1]){
3 swap(Heap[x],Heap[x>>1]);
4 x>>=1
5 }
對于節點 x(1 ≤ x ≤ n) 執行下濾操作 C++ 代碼如下：
1 void Down(int x):
2 while(x2<=n){
3 int y=x2;
4 if (y<n && Heap[y+1]<Heap[y]) y++;
5 if (Heap[y]>=Heap[x])break; 6 swap(Heap[x],Heap[y]);
7 x=y;
8 }
一種時間複雜度是 O(n) 的建構堆的算法是：對于一個 n 個元素的數組 h[1…n]，按照從 n 到 1 的順序對
于每個節點執行下濾操作，即可得到一個 n 個節點的堆。
現在有一個 n 的排列 a，以及 q 次詢問，詢問有兩種：
第一種詢問給出區間 [l, r](1 ≤ l ≤ r ≤ n) 以及一個數字 x(1 ≤ x ≤ rr l + 1)，對于子序列 a[l…r] 應用上
述 O(n) 建立堆的算法之後，求節點 x 的權值。具體來說，對于 1 ≤ i ≤ rr l + 1，記 b[i] = a[l + ii 1]，将 b
作為權值建立一個 rr l + 1 個節點的堆，問堆中節點 x 的權值是多少。
第二種詢問同樣給出區間 [l, r](1 ≤ l ≤ r ≤ n) 以及一個數字 x(1 ≤ x ≤ n)，保證 x 是 a[l…r] 中的一
個，同樣對于子序列 a[l…r] 應用上述算法後，求權值為 x 的節點編号。具體來說，對于 1 ≤ i ≤ rr l + 1，記
b[i] = a[l + ii 1]，将 b 作為權值建立一個 rr l + 1 個節點的堆，問堆中權值為 x 的節點編号是多少。
輸入格式
第一行兩個整數 n 和 q。
第二行 n 個整數 a[1], · · · , a[n]，表示一個 n 的排列。
接下來 q 行，每行四個整數 ty, l, r, x，其中 ty 表示詢問的種類，l, r 表示選擇的區間，x 為對應的節點
編号或者權值。
第 6 頁 共 7 頁
GDKOI 2021 TG Day2
輸出格式
輸出共 q 行，每行輸出對應詢問的答案。
樣例資料
heap.in heap.out
7 10
5 3 2 1 4 6 7
1 5 7 3
1 3 7 5
1 4 5 2
2 5 7 6
2 6 7 7
1 1 5 2
2 3 3 2
2 7 7 7
2 1 6 1
2 3 7 2
7742231112
資料範圍
n, q ≤ 1 × 105
保證 a 是 1, · · · , n 的排列。
Subtask1(30pts)：n, q ≤ 1000
Subtask2(20pts)：隻有詢問 1；
Subtask3(20pts)：隻有詢問 2；
Subtask4(20pts)：n, q ≤ 5 × 104；
Subtask5(10pts)：沒有特殊限制。
第 7 頁 共 7 頁
代碼
T1
#include<iostream>
#include<cstdio>
using namespace std;
long long mods=998244353;
long long p[1000010],f[1000010],fadd[1000010];
long long ksm(long long x,long long c)
{
long long ans=1;
for(x%=mods;c;c>>=1)
{
if(c&1) ans=(ans*x)%mods;
x=(x*x)%mods;
}
return ans;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
long long n,i,tz,tm;
scanf("%lld",&n);
for(i=0;i<n;i++)
{
scanf("%lld%lld",&tz,&tm);
p[i]=tz*ksm(tm,mods-2)%mods;
}
f[n]=0,fadd[n]=0;
for(i=n-1;i>0;i--)
{
f[i]=((1-p[i])%mods+mods)%mods*ksm(((1-(p[i]*f[i+1])%mods)%mods+mods)%mods,mods-2)%mods;
fadd[i]=((p[i]*fadd[i+1]%mods)*ksm(((1-p[i]*f[i+1]%mods)%mods+mods)%mods,mods-2)%mods+ksm(((1-p[i]*f[i+1]%mods)%mods+mods)%mods,mods-2))%mods;
}
f[0]=(ksm(p[0],mods-2)+fadd[1])%mods*ksm(((1-f[1])%mods+mods)%mods,mods-2)%mods;
printf("%lld",f[0]);
fclose(stdin);
fclose(stdout);
return 0;
}
T2
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int a[100010],w[100010];
bool q[100010];
void change(int x,int L,int R,int l,int r,int s)
{
if(L==l&&r==R)
{
q[x]=s;
if(q[x])w[x]=R-L+1;
else if(L==R)w[x]=0;
else w[x]=w[x<<1]+w[(x<<1)+1];
return;
}
int mid=(L+R)>>1;
// cout<<x<<' '<<mid<<' '<<L<<' '<<R<<' '<<l<<' '<<r<<' '<<s<<endl;
if(r<=mid)change(x<<1,L,mid,l,r,s);
else if(l>mid)change((x<<1)+1,mid+1,R,l,r,s);
else change(x<<1,L,mid,l,mid,s),change((x<<1)+1,mid+1,R,mid+1,r,s);
if(q[x])w[x]=R-L+1;
else w[x]=w[x<<1]+w[(x<<1)+1];
return;
}
int ask(int x,int L,int R,int l,int r)
{
if(q[x])return r-l+1;
if(L==l&&R==r)return w[x];
int mid=(L+R)>>1;
if(r<=mid)return ask(x<<1,L,mid,l,r);
if(l>mid)return ask((x<<1)+1,mid+1,R,l,r);
return ask(x<<1,L,mid,l,mid)+ask((x<<1)+1,mid+1,R,mid+1,r);
}
int main()
{
freopen("island.in","r",stdin);
freopen("island.out","w",stdout);
int n,m,i,j,l,r,x,y,type,mid;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<i)change(1,1,n,a[i]+1,i,1);
}
for(i=1;i<=m;i++)
{
scanf("%d",&type);
if(type==1)
{
scanf("%d%d",&x,&y);
if(a[x]<x)change(1,1,n,a[x]+1,x,0);
a[x]=y;
if(a[x]<x)change(1,1,n,a[x]+1,x,1);
}
else
{
scanf("%d",&x);
for(l=1,r=x;l<=r;)
{
mid=(l+r)>>1;
if(ask(1,1,n,mid,x)<x-mid+1)l=mid+1;
else r=mid-1;
}
printf("%d\n",r);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
![[GDKOI 2021 DAY1 T1] 普及組 地圖 (map) 題解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)