信息学奥赛题目

《信息学奥赛题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、并查集题目描述这是一道模板题。维护一个n点的无向图，支持:加入一条连接u和v的无向边查询U和V的连通性由于本题数据较大，因此输出的吋候采用特殊的输出方式：用0或1代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数mod998244353的值。输入输出格式输入格式:第一行包含两个整数n,m,表示点的个数和操作的数目。接下来m行每行包括三个整数opuv。如果op二0,则表示加入一条连接u和v的无向边；如果op二1,则表示查询u和v的连通性。输出格式：一行包括一个整数表示答案

2、。输入输岀样例输入样例#1:复制36110001101112021121输出样例#1:复制5说明样例解释答案串为101o数据范圉与提示0<4000000^<8000000题解：#include#include#include#includeusingnamespacestd;intread(){intx=0;charch=getchar();while(ch<*0'

3、

4、ch>'9*)ch=getchar();while(ch>=,0'&&ch

5、<=,9,){x=x*10+ch-*0*;ch=getchar();}returnx;}constintMAXN=8000005;intff[MAXN],sz[MAXN];intfind(intx){returnff[x]==x?x:find(ff[x]);}voidmerge(intx’inty){intxx=find(x)Jyy=find(y);if(xx==yy)return;if(sz[xx]>sz[yy])ff[yy]=xxJsz[xx]+=sz[yy];elseff[xx]=yyJsz[yy]+=sz[x

6、x];}intmain(){intn=read()Jm=read()ns=0;for(inti=l;i<=n;i++)ff[i]=i^sz[i]=l;intop,x,y;for(inti=l;i<=m;i++){op=read(),x=read(),y=read();switch(op){case0:merge(x,y);break;case1:ans=((ans<<1)+(find(x)==find(y)))%998244353；}}printf(,,%d,ans);return0;}字串查找题目描述这是一道

7、模板题。给定一个字符串A和一个字符串B,求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。A中不同位置出现的B可重叠。输入输出格式输入格式:输入共两行，分别是字符串AAA和字符串BBB。输出格式：输出一个整数，表示BBB在AAA中的出现次数。输入输出样例输入样例#1:复制zyzyzyzzyz输出样例#1：复制3说明1usingnamespacestd;int11,12,ans;intnxt[1000100

8、];chara[1000100],b[1000100];voidparse(){nxt[1]=0;for(inti=2^j=0;i<=12;i++){while(j>0&&(j==12

9、

10、b[i]!=b[j+1]))j=nxt[j];if(b[i]==b[j+l])j++;nxt[i]=j;}}voidkmp(){for(inti=ljj=0;i<=ll;i++){while(j>0&&(j==12

11、

12、a[i]!=b[j+l]))j=nxt[j];if(a[i]==b[j+l])j++;if(j==12)ans++;

13、intmain(){scanfC^sJSs^a+l.b+l);ll=strlen(a+l)12=strlen(b+l);parse();kmp();printf("%d",ans);return0;}单源最短路题目描述给一个n(lwi(l

14、据保证至少存在一条道路。输入输出样例输入样例#止复制71154242143722343575733611634243563721输出样例#1：复制7题解：#include#include#include#definemaxn2500+10#definemaxm6200+10usingnames