【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=)