ABC049

[ABC049C] 白昼夢

题面翻译

题目大意

输入一个以英文小写字母组成的字符串S,规定一个空的字符串T,现在你可对字符串T进行你喜欢的操作,问是否能让字符串T变为字符串S?

喜欢的操作如下 :

在字符串T的末尾加入 “dream”或“dreamer”或“erase”或“eraser”。


输入格式

一个字符串S

输出格式

若可以输出YES,否则输出NO

题目描述

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

  • T の末尾に dream dreamer erase eraser のいずれかを追加する。

输入格式

入力は以下の形式で標準入力から与えられる。

S

输出格式

S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

样例 #1

样例输入 #1

erasedream

样例输出 #1

YES

样例 #2

样例输入 #2

dreameraser

样例输出 #2

YES

样例 #3

样例输入 #3

dreamerer

样例输出 #3

NO

提示

制約

  • 1|S|105
  • S は英小文字からなる。

Sample Explanation 1

erase dream の順で T の末尾に追加することで S=T とすることができます。

Sample Explanation 2

dream eraser の順で T の末尾に追加することで S=T とすることができます。

思路

其实是一道模拟题(doge),只要判断读到de时,判断是不是dreamdreamereraseeraser中的一个即可,注意dreamereraseeraser会首尾重叠,所以还需进一步分类。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
char a[110][110];
int main(){
ios::sync_with_stdio(false);
string s;cin>>s;
for(int i=0;i<s.length();i++){
//读到e,判断是不是eraser或erase
if(s[i]=='e'){
if(s[i+1]=='r'&&s[i+2]=='a'&&s[i+3]=='s'&&s[i+4]=='e'){
if(s[i+5]=='r'){
i+=5;
}
else i+=4;
}
}
//读到d,判断是不是dream、dreamer、dreamerase、dreameraser即可
else if(s[i]=='d'){
if(s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m') {
if (s[i + 5] == 'e' && s[i + 6] == 'r' && s[i + 7] == 'a' && s[i + 8] == 's' && s[i + 9] == 'e') {
i += 4;
}
else {
if (s[i + 5] == 'e' && s[i + 6] == 'r') {
i += 6;
}
else {
i += 4;
}
}
}
}
else{
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}

[ABC049D] 連結

题面翻译

题目描述

N个城市,K条道路(指地面上的道路)和L条地铁。道路和地铁都是无向的。对于每个点,请你求出它只通过道路只通过地铁都能到达的点的个数。道路和地铁之间不能换乘,你只能完全通过地铁到达某个点,或者完全通过道路到达某个点。

输入格式

第一行三个正整数N,K,L (N2×105,K,L105)
然后K行,每行两个数p,q,表示城市p和城市q通过道路连接。
然后L行,每行两个数r,s,表示城市r和城市s通过地铁连接。

输出格式

一行N个正整数,表示每个点只通过道路和只通过地铁都能到达的点的个数。

题目描述

N 個の都市があり、K 本の道路と L 本の鉄道が都市の間に伸びています。 i 番目の道路は pi 番目と qi 番目の都市を双方向に結び、 i 番目の鉄道は ri 番目と si 番目の都市を双方向に結びます。 異なる道路が同じ 2 つの都市を結ぶことはありません。同様に、異なる鉄道が同じ 2 つの都市を結ぶことはありません。

ある都市から別の都市に何本かの道路を通って到達できるとき、それらの都市は道路で連結しているとします。また、すべての都市はそれ自身と道路で連結しているとみなします。
鉄道についても同様に定めます。

全ての都市について、その都市と道路・鉄道のどちらでも連結している都市の数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N K L p1 q1 : pK qK r1 s1 : rL sL

输出格式

N 個の整数を出力せよ。i 番目の数は i 番目の都市と道路・鉄道の両方で連結している都市の数である。

样例 #1

样例输入 #1

4 3 1
1 2
2 3
3 4
2 3

样例输出 #1

1 2 2 1

样例 #2

样例输入 #2

4 2 2
1 2
2 3
1 4
2 3

样例输出 #2

1 2 2 1

样例 #3

样例输入 #3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

样例输出 #3

1 1 2 1 2 2 2

提示

制約

  • 2N2105
  • 1K,L105
  • 1pi,qi,ri,siN
  • pi<qi
  • ri<si
  • ij のとき、(pi,qi)(pj,qj)
  • ij のとき、(ri,si)(rj,sj)

Sample Explanation 1

1,2,3,4 番目の都市は全て互いに道路で連結しています。 鉄道で連結している都市は 2,3 のみなので、答えは順に 1,2,2,1 となります。

思路

并查集+map,具体也不知道怎么解释,太累了,不想写了qwq

直接看题解吧:题解 AT2159 【連結 / Connectivity】 - 洛谷专栏 (luogu.com.cn)


补思路补思路~~~

可以发现这是一个连通性问题,所以我们不难想到用并查集

但是答案求的是这两个图的交集的元素个数,所以我们可以开一个数组Fa[i][j],表示有多少个点满足在fa1中的祖先是i,有多少个点在fa2中的祖先是j。那么,对于一个点u,它走两条线路都能到的点数量就是Fa[fa1.find(i)][fa2.find(i)](其中find是查找祖先的函数)。记录这个数组的方法也很简单,就是对于每个点,Fa[fa1.find(i)][fa2.find(i)]++

但是这样会喜提MLE,所以我们可以拿出神器:map+pair

map<pair<int,int>,int>就可以省下很多空间,而我们其实只需要遍历这n个点即可,所以绰绰有余,我们只需要遍历每个点时加一即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const int mod=1e9+7;
int fa1[MAXN],fa2[MAXN];
map<pair<int,int>,int> m;
//思路:并查集+stl
int find(int x,int *fa){
if(x==fa[x])return x;
return fa[x]=find(fa[x],fa);
}
void join(int x,int y,int *fa){
int fx=find(x,fa),fy=find(y,fa);
if(fx!=fy){
fa[fx]=fy;
}
}
int main(){
ios::sync_with_stdio(false);
ll n,k,l;cin>>n>>k>>l;
for(int i=1;i<=n;i++)fa1[i]=i,fa2[i]=i;
for(int i=1;i<=k;i++){
ll x,y;cin>>x>>y;
join(x,y,fa1);
}
for(int i=1;i<=l;i++){
ll x,y;cin>>x>>y;
join(x,y,fa2);
}
for(int i=1;i<=n;i++){
m[make_pair(find(i,fa1),find(i,fa2))]++;
}
for(int i=1;i<=n;i++){
cout<<m[make_pair(find(i,fa1),find(i,fa2))]<<" ";
}
return 0;
}