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|≦10^5 $

$ S $ は英小文字からなる。

Sample Explanation 1

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

Sample Explanation 2

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

思路

其实是一道模拟题（doge），只要判断读到$d$或$e$时，判断是不是$dream、dreamer、erase、eraser$中的一个即可，注意$dreamer$与$erase、eraser$会首尾重叠，所以还需进一步分类。

#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$ ($N\le2\times 10^5,K,L\le10^5$)
然后$K$行，每行两个数$p,q$，表示城市$p$和城市$q$通过道路连接。
然后$L$行，每行两个数$r,s$，表示城市$r$和城市$s$通过地铁连接。

输出格式

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

题目描述

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

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

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

输入格式

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

$ N $ $ K $ $ L $ $ p_1 $ $ q_1 $ : $ p_K $ $ q_K $ $ r_1 $ $ s_1 $ : $ r_L $ $ s_L $

输出格式

$ 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
提示

制約

$ 2 ≦ N ≦ 2*10^5 $

$ 1 ≦ K, L≦ 10^5 $

$ 1 ≦ p_i, q_i, r_i, s_i ≦ N $

$ p_i < q_i $

$ r_i < s_i $

$ i ≠ j $ のとき、$ (p_i, q_i) ≠ (p_j, q_j) $

$ i ≠ j $ のとき、$ (r_i, s_i) ≠ (r_j, s_j) $

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;
}