信息学奥赛题目.doc

并查集题目描述这是一道模板题。维护一个 n 点的无向图，支持： 加入一条连接 u 和 v 的无向边 查询 u 和 v 的连通性由于本题数据较大，因此输出的时候采用特殊的输出方式：用 0 或 1 代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353 的值。输入输出格式输入格式：第一行包含两个整数 n,m，表示点的个数和操作的数目。接下来 m 行每行包括三个整数 op,u,v。如果 op=0，则表示加入一条连接 u 和 v 的无向边； 如果 op=1，则表示查询 u 和 v 的连通性。输出格式：一行包括一个整数表示答案。输入输出样例输入样例#1：复制3 61 1 00 0 11 0 11 1 20 2 11 2 1输出样例#1：复制5说明样例解释 答案串为 101。数据范围与提示 n4000000,m8000000题解：#include#include#include#includeusing namespace std;int read()int x=0;char ch=getchar();while(ch9) ch=getchar();while(ch=0&chszyy) ffyy=xx,szxx+=szyy;else ffxx=yy,szyy+=szxx;int main()int n=read(),m=read(),ans=0;for(int i=1;i=n;i+) ffi=i,szi=1;int op,x,y;for(int i=1;i=m;i+)op=read(),x=read(),y=read();switch(op)case 0:merge(x,y);break;case 1:ans=(ans1)+(find(x)=find(y)%998244353;printf(%dn,ans);return 0;字串查找题目描述这是一道模板题。给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数。A 和 B 中的字符均为英语大写字母或小写字母。A 中不同位置出现的 B 可重叠。输入输出格式输入格式：输入共两行，分别是字符串 A A A 和字符串 B B B。输出格式：输出一个整数，表示 B B B 在 A A A 中的出现次数。输入输出样例输入样例#1：复制zyzyzyzzyz输出样例#1：复制3说明1A,B 的长度 106，A 、B 仅包含大小写字母。题解：#include using namespace std;int l1,l2,ans;int nxt1000100;char a1000100,b1000100;void parse() nxt1=0; for(int i=2,j=0;i0&(j=l2|bi!=bj+1) j=nxtj; if(bi=bj+1) j+; nxti=j; void kmp() for(int i=1,j=0;i0&(j=l2|ai!=bj+1) j=nxtj; if(ai=bj+1) j+; if(j=l2) ans+; int main() scanf(%s%s,a+1,b+1); l1=strlen(a+1),l2=strlen(b+1); parse(); kmp(); printf(%dn,ans); return 0;单源最短路题目描述给一个 n(1n2500) 个点 m(1m6200) 条边的无向图，求 s 到 t 的最短路。输入输出格式输入格式：第一行四个由空格隔开的整数 n、m、s、t。 之后的 m m m 行，每行三个正整数 si、ti、wi(1wi109) ，表示一条从 si 到 ti 长度为 wi 的边。输出格式：一个整数表示从 s 到 t 的最短路长度。数据保证至少存在一条道路。输入输出样例输入样例#1：复制7 11 5 42 4 21 4 37 2 23 4 35 7 57 3 36 1 16 3 42 4 35 6 37 2 1输出样例#1：复制7题解：#include#include#include#define maxn 2500+10#define maxm 6200+10using namespace std;const int inf = 2147483647;/Grapeint n, m, s, t;struct Edgeint v, w, next;emaxm2;int tot, headmaxn;void AddEdge(int u, int v, int w) tot+; etot.v=v; etot.w=w; etot.next=headu; headu=tot;/SPFAint distmaxn, bookmaxn;queueq;void spfa() for(int i = 1; i distu+w) distv = distu+w; if(!bookv) bookv = 1; q.push(v); int main() memset(head,-1,sizeof(head); cinnmst; for(int i = 1; i xyz; AddEdge(x,y,z); AddEdge(y,x,z); spfa(); coutdistt; return 0;引水入城在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个NN行times MM列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第11行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第NN行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。输入输出格式输入格式：每行两个数，之间用一个空格隔开。输入的第一行是两个正整数N,MN,M，表示矩形的规模。接下来NN行，每行MM个正整数，依次代表每座城市的海拔高度。输出格式：两行。如果能满足要求，输出的第一行是整数11，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数00，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。输入输出样例输入样例#1：复制2 59 1 5 4 38 7 6 1 2输出样例#1：复制11输入样例#2：复制3 68 4 5 6 4 47 3 4 3 3 33 2 2 1 1 2输出样例#2：复制13首先我们可以使用DFS将第一排每一个点都用DFS搜索一遍，然后找出它能到达的点，先判定是否能覆盖完。之后就是最重要的一个结论，你很明显可以知道，如果一个点无法被覆盖掉的话，那么它上左右的点都比他小，那么这个点将绝对无法覆盖到，反之则如果能覆盖全部点，上方的每一个点所对应覆盖的将会是一个区间，于是我们将问题转化为区间覆盖问题。#include#include#include#include#includeusing namespace std;int n,m;int map505505,vis505505=0,ans505,f505;struct nodeint l,r;cover505;/每个点对应的区间void DFS(int x,int y,int place)/x横坐标,y纵坐标，place是对应那个点。visxy=1;/记住搜过的点if(x=n)ansy=1;/到最后一排更新coverplace.l=min(coverplace.l,y);coverplace.r=max(coverplace.r,y);/深搜if(x!=n&!visx+1y&mapx+1ymapxy)DFS(x+1,y,place);if(x!=1&!visx-1y&mapx-1ymapxy)DFS(x-1,y,place);if(y!=m&!visxy+1&mapxy+1mapxy)DFS(x,y+1,place);if(y!=1&!visxy-1&mapxy-1mapxy)DFS(x,y-1,place);int main()scanf(%d %d,&n,&m);for(int i=1;i=m;i+)coveri.l=fi=30000;f0=0;for(int i=1;i=n;i+)for(int j=1;j=m;j+)scanf(%d,&mapij);for(int i=1;i=m;i+)DFS(1,i,i);memset(vis,0,sizeof(vis);/每次搜索归零int cnt=0;for(int i=1;i=m;i+)if(!ansi)cnt+;if(cnt) printf(0n%d,cnt);elsecout1endl;/找最少的点for(int i=1;i=m;+i)for(int j=1;j=coverj.l&i=coverj.r)fi=min(fi,fcoverj.l-1+1);coutfmendl;图的遍历题目描述给出NN个点，MM条边的有向图，对于每个点vv，求A(v)A(v)表示从点vv出发，能到达的编号最大的点。输入输出格式输入格式：第1 行，2 个整数N,MN,M。接下来MM行，每行2个整数U_i,V_iUi,Vi，表示边(U_i,V_i)(Ui,Vi)。点用1, 2,cdots,N1,2,N编号。输出格式：N 个整数A(1),A(2),cdots,A(N)A(1),A(2),A(N)。输入输出样例输入样例#1：复制4 31 22 44 3输出样例#1：复制4 4 3 4#include#include#define BIG 233333using namespace std;int n,m,x,y,tot;int maxxBIG,lasBIG,toBIG,nxtBIG;inline void add() scanf(%d%d,&y,&x); nxt+tot=lasx; lasx=tot; totot=y;inline void dfs(int now,int st) if(maxxnow) return; maxxnow=st;