ABC049
ABC049
[ABC049C] 白昼夢
题面翻译
题目大意
输入一个以英文小写字母组成的字符串S,规定一个空的字符串T,现在你可对字符串T进行你喜欢的操作,问是否能让字符串T变为字符串S?
喜欢的操作如下 :
在字符串T的末尾加入 “dream”或“dreamer”或“erase”或“eraser”。
输入格式
一个字符串S
输出格式
若可以输出YES,否则输出NO。
题目描述
英小文字からなる文字列
が与えられます。 が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで とすることができるか判定してください。
の末尾に dream
dreamer
erase
eraser
のいずれかを追加する。输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
とすることができる場合 YES
を、そうでない場合NO
を出力せよ。样例 #1
样例输入 #1
erasedream样例输出 #1
YES样例 #2
样例输入 #2
dreameraser样例输出 #2
YES样例 #3
样例输入 #3
dreamerer样例输出 #3
NO提示
制約
は英小文字からなる。 Sample Explanation 1
erase
dream
の順での末尾に追加することで とすることができます。 Sample Explanation 2
dream
eraser
の順での末尾に追加することで とすることができます。
思路
其实是一道模拟题(doge),只要判断读到
|
[ABC049D] 連結
题面翻译
题目描述
有
个城市, 条道路(指地面上的道路)和 条地铁。道路和地铁都是无向的。对于每个点,请你求出它只通过道路和只通过地铁都能到达的点的个数。道路和地铁之间不能换乘,你只能完全通过地铁到达某个点,或者完全通过道路到达某个点。 输入格式
第一行三个正整数
( )
然后行,每行两个数 ,表示城市 和城市 通过道路连接。
然后行,每行两个数 ,表示城市 和城市 通过地铁连接。 输出格式
一行
个正整数,表示每个点只通过道路和只通过地铁都能到达的点的个数。 题目描述
個の都市があり、 本の道路と 本の鉄道が都市の間に伸びています。 番目の道路は 番目と 番目の都市を双方向に結び、 番目の鉄道は 番目と 番目の都市を双方向に結びます。 異なる道路が同じ つの都市を結ぶことはありません。同様に、異なる鉄道が同じ つの都市を結ぶことはありません。 ある都市から別の都市に何本かの道路を通って到達できるとき、それらの都市は道路で連結しているとします。また、すべての都市はそれ自身と道路で連結しているとみなします。
鉄道についても同様に定めます。全ての都市について、その都市と道路・鉄道のどちらでも連結している都市の数を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
: : 输出格式
個の整数を出力せよ。 番目の数は 番目の都市と道路・鉄道の両方で連結している都市の数である。 样例 #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提示
制約
のとき、 のとき、 Sample Explanation 1
番目の都市は全て互いに道路で連結しています。 鉄道で連結している都市は のみなので、答えは順に となります。
思路
并查集+map,具体也不知道怎么解释,太累了,不想写了qwq
直接看题解吧:题解 AT2159 【連結 / Connectivity】 - 洛谷专栏 (luogu.com.cn)
补思路补思路~~~
可以发现这是一个连通性问题,所以我们不难想到用并查集。
但是答案求的是这两个图的交集的元素个数,所以我们可以开一个数组Fa[fa1.find(i)][fa2.find(i)]
(其中Fa[fa1.find(i)][fa2.find(i)]++
。
但是这样会喜提
用
|