Time limit : 2sec / Memory limit : 256MB
Score : 300 points
You are given a string S consisting of lowercase English letters. Another string T is initially empty. Determine whether it is possible to obtain S=T by performing the following operation an arbitrary number of times:
Append one of the following at the end of T: dream, dreamer, erase and eraser.The input is given from Standard Input in the following format:
SIf it is possible to obtain S=T, print YES. Otherwise, print NO.
Copy
erasedreamCopy
YESAppend erase and dream at the end of T in this order, to obtain S=T.
Copy
dreameraserCopy
YESAppend dream and eraser at the end of T in this order, to obtain S=T.
Copy
dreamererCopy
NO
这个题一开始想错了，本应该是，每次 只枚举一个单词，每次枚举的时候只判断这一个单词，然后从这个单词的下一个字母枚举新的单词，这样才行。
#include<bits/stdc++.h> using namespace std; char er[]="erase"; char dr[]="dream"; int main() { string str; cin>>str; int len=str.size(); int flag=0; for(int i=0;i<len;i++) { if(str[i]=='d')//dream---,县推理到dreamer { int j=i; for(j=i;j<=i+4;j++) { if(j>=len||dr[j-i]!=str[j]) { flag=1; break;// } } if(j==i+5) { i=j-1; if(str[j]=='e'&&str[j+1]=='r'&&str[j+2]!='a') { i=j+1; } } }else if(str[i]=='e') { int j=i; for(j=i;j<=i+4;j++) { if(j>=len||er[j-i]!=str[j]) { flag=1; break;// } } if(j==i+5) { i=j-1; if(str[j]=='r') { i=j; }else { i=j-1; } } }else { flag=1; } if(flag==1)break; } if(!flag)printf("YES\n"); else printf("NO\n"); return 0; }D - 連結 / Connectivity Time Limit: 2 sec / Memory Limit: 256 MB Score : points Problem Statement There are cities. There are also roads and railways, extending between the cities. The -th road bidirectionally connects the -th and -th cities, and the -th railway bidirectionally connects the -th and -th cities. No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities. We will say city and are c o n n e c t e d b y r o a d s if city is reachable from city by traversing some number of roads. Here, any city is considered to be connected to itself by roads. We will also dene c o n n e c t i v i t y b y r a il w a y s similarly. For each city, nd the number of the cities connected to that city by both roads and railways. Constraints When , When , Input The input is given from Standard Input in the following format: : : Output Print integers. The -th of them should represent the number of the cities connected to the -th city by both roads and railways. Sample Input 1 4 3 1 1 2 2 3 3 4 2 3 Sample Output 1 1 2 2 1 All the four cities are connected to each other by roads. By railways, only the second and third cities are connected. Thus, the answers for the cities are and , respectively. Sample Input 2 400 N K L i pi qi i ri si A B B A 2 ≦ N ≦ 2 ∗ 105 1 ≦ K,L ≦ 105 1 ≦ pi,qi,ri,si ≦ N pi < qi ri < si i ≠ j (pi,qi) ≠ (pj,qj) i ≠ j (ri,si) ≠ (rj,sj) N K L p1 q1 pK qK r1 s1 rL sL N i i 1,2,2 1 2019/5/23 AtCoder Regular Contest 065 https://atcoder.jp/contests/arc065/tasks_print 3/6 Sample Input 2 4 2 2 1 2 2 3 1 4 2 3 Sample Output 2 1 2 2 1 Sample Input 3 7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7 Sample Output 3 1 1 2 1 2 2 2 就是要用两个并查集分别求出和第i个点铁路、公路联通点的个数，然后利用并查集求交集，这个地方要仔细想想才行。
这个地方就是求交集的时候要看他们的父节点，看两者都联通的个数，这个交集真的是要好好体会。
#include<bits/stdc++.h> using namespace std; int fa[500000]; int fb[500000]; int finda(int x) { return x==fa[x]?x:fa[x]=finda(fa[x]); } int findb(int x) { return x==fb[x]?x:fb[x]=findb(fb[x]); } int main() { int n,k,l; scanf("%d%d%d",&n,&k,&l); for(int i=1;i<=n;i++) { fa[i]=i; fb[i]=i; } for(int i=1;i<=k;i++) { int u,v; scanf("%d%d",&u,&v); int fu=finda(u); int fv=finda(v); if(fu!=fv) { fa[fu]=fv; } } for(int i=1;i<=l;i++) { int u,v; scanf("%d%d",&u,&v); int fu=findb(u); int fv=findb(v); if(fu!=fv) { fb[fu]=fv; } } for(int i=1;i<=n;i++) { finda(i); findb(i); } map<pair<int,int>,int>mmp; for(int i=1;i<=n;i++) { mmp[make_pair(fa[i],fb[i])]++;//---//---//---//---// //cout<<fa[i]<<" --"<<fb[i]<<" --"<<mmp[make_pair(fa[i],fb[i])]<<endl; } for(int i=1;i<=n;i++) { printf("%d ", mmp[make_pair(fa[i],fb[i])]); } printf("\n"); }
