信息学奥赛题目.doc

信息学奥赛题目.doc:..并查集题目描述这是一道模板题。维护一个n点的无向图,支持:加入一条连接u和v的无向边查询U和V的连通性由于本题数据较大,因此输出的吋候采用特殊的输出方式:用0或1代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数mod998244353的值。输入输出格式输入格式:第一行包含两个整数n,m,表示点的个数和操作的数目。接下来m行每行包括三个整数opuv。如果op二0,则表示加入一条连接u和v的无向边;如果op二1,则表示查询u和v的连通性。输出格式:一行包括一个整数表示答案。输入输岀样例输入样例#1:复制36110001101112021121输出样例#1:复制5说明样例解释答案串为101o数据范圉与提示0<4000000^<8000000题解:#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>usingnamespacestd;intread(){intx=0;charch=getchar();while(ch<*0'||ch>'9*)ch=getchar();while(ch>=,0'&&ch<=,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[xx];}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\n,\ans);return0;}字串查找题目描述这是一道模板题。给定一个字符串A和一个字符串B,求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。A中不同位置出现的B可重叠。输入输出格式输入格式:输入共两行,分别是字符串AAA和字符串BBB。输出格式:输出一个整数,表示BBB在AAA中的出现次数。输入输出样例输入样例#1:复制zyzyzyzzyz输出样例#1:复制3说明1<A,B的长度<106,A、B仅包含大小写字母。题解:#inelude<bits/stdc++・h>usingnamespacestd;int11,12,ans;intnxt[1000100];chara[1000100],b[1000100];voidparse(){nxt[1]=0;for(inti=2^j=0;i<=12;i++){while(j>0&&(j==12||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||a[i]!=b[j+l]))j=nxt[j];if(a[i]==b[j+l])j++;if(j==12)ans++;intmain(){scanfC^sJSs^a++l);ll=strlen(a+l)12=strlen(b+l);parse();kmp();printf("%d\n",ans);return0;}单源最短路题目描述给一个n(l<n<2500)个点m(l<m<6200)条边的无向图,求s到t的最短路。输入输岀格式输入格式:第一行四个由空格隔开的整数n、m、s、to之后的mmm行,每行三个止整数si、ti>wi(l<wi<109),表示一条从si到ti长度为wi的边。输出格式:一个整数表示从s到t的最短路长度。数据保证至少存在一条道路。输入输出样例输入样例#止复制71154242143722343575733611634243563721输出样例#1:复制7题解:#include<iostream>#include<queue>#include<cstr