AtCoder Regular Contest 065_综合

C - 白昼夢 / Daydream

Time Limit: 2 sec / Memory Limit: 256 MB

Score : 300300 points

Problem Statement

You are given a string SS consisting of lowercase English letters. Another string TT is initially empty. Determine whether it is possible to obtain S=TS=T by performing the following operation an arbitrary number of times:

Append one of the following at the end of TT: dream, dreamer, erase and eraser.

Constraints

1≦|S|≦1051≦|S|≦105
SS consists of lowercase English letters.

Input

The input is given from Standard Input in the following format:

SS

Output

If it is possible to obtain S=TS=T, print YES. Otherwise, print NO.

Sample Input 1 Copy

Copy

erasedream

Sample Output 1 Copy

Copy

YES

Append erase and dream at the end of TT in this order, to obtain S=TS=T.

Sample Input 2 Copy

Copy

dreameraser

Sample Output 2 Copy

Copy

YES

Append dream and eraser at the end of TT in this order, to obtain S=TS=T.

Sample Input 3 Copy

Copy

dreamerer

Sample Output 3 Copy

Copy

NO

题意：

输入一个以英文小写字母组成的字符串S，规定一个空的字符串T，现在你可字符串T的末尾加入 “dream”或“dreamer”或“erase”或“eraser”，问是否能让字符串T变为字符串S？

分析：

暴力模拟即可

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;public class Main {static int N=1010;static int n;static Double []x=new Double[N];static Double []y=new Double[N];static Double []r=new Double[N];static Double []dist=new Double[N];static Double [][]map1=new Double[N][N];static int[] vis=new int[N];public static void main(String[] args) {Scanner input=new Scanner( System.in);String string =input.next();int len=string.length();string+="       ";String s1="dream",s2="erase";int flag=1;for(int i=0;i<len;i++){if(flag==0) break;if(string.charAt(i)=='d') {int j;for(j=i+1;j<=i+4;j++){if(string.charAt(j)!=s1.charAt(j-i)){flag=0;break;}}if(flag==0) break;i=j;if(string.charAt(i)=='e'&&string.charAt(i+1)=='r'){if(string.charAt(i+2)=='e'||string.charAt(i+2)=='d'||i+2==len){i=i+1;}else i=j-1;}elsei=j-1;}else if(string.charAt(i)=='e'){int j;for(j=i+1;j<=i+4;j++){if(string.charAt(j)!=s2.charAt(j-i)){flag=0;break;}}if(flag==0) break;i=j;//System.out.println(i);if(string.charAt(i)=='r'){if(string.charAt(i+1)=='e'||string.charAt(i+1)=='d'||i+1==len){i=i;}else i=j-1;}else i=j-1;}else {flag=0;break;}//System.out.println(i);if(flag==0) break;}if(flag==0)System.out.println("NO");elseSystem.out.println("YES");//  System.out.printf("%.10f",dist[2]);}}

D連結 / Connectivity

There are N cities. There are also K roads and L railways, extending between the cities. The i-th road bidirectionally connects the pi-th and qi-th cities, and the i-th railway bidirectionally connects the ri-th and si-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 A and B are connected by roads if city B is reachable from city Aby traversing some number of roads. Here, any city is considered to be connected to itself by roads. We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2≦N≦2*105
1≦K,L≦105
1≦pi,qi,ri,si≦N
pi<qi
ri<si
When i≠j, (pi,qi)≠(pj,qj)
When i≠j, (ri,si)≠(rj,sj)

Input

The input is given from Standard Input in the following format:

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

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

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 1,2,2 and 1, respectively.

Sample Input 2

Sample Output 2

1 2 2 1

Sample Input 3

Sample Output 3

1 1 2 1 2 2 2

题意：

给你n个点，K条铁路，L条公路。让求对于1~n中每一个节点i，有多少个节点和它是铁路和公路都联通的（算本身）。

分析：

两个并查集，一个维护K条铁路，一个维护L条公路，对于满足（i，j）公路铁路均连通的个数用map来统计，对于第i个点来说，（find1(i),find2(i))的个数就是答案，因为每一个连通块的父亲节点（find(i)）是相同的，所以只要跟i连通，父亲节点一定是find(i),所以同时满足两个路的父亲节点与i的父亲节点相同的，则就是其两个路都连通的点个数。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;public class Main {static int N=200010;static int[] fa1=new int[N];static int[] fa2=new int[N];public static void main(String[] args) {Scanner input=new Scanner( System.in);int n=input.nextInt();for(int i=1;i<=n;i++){fa1[i]=i;fa2[i]=i;}int k=input.nextInt();int l=input.nextInt();for(int i=1;i<=k;i++){int u=input.nextInt(),v=input.nextInt();merge1(u,v);}for(int i=1;i<=l;i++){int u=input.nextInt(),v=input.nextInt();merge2(u,v);}HashMap<Node, Integer> map=new HashMap<Node, Integer>();for(int i=1;i<=n;i++){Node temp=new Node(find1(i), find2(i));if(map.containsKey(temp)){map.put(temp, map.get(temp)+1); }else{map.put(temp, 1); }}for(int i=1;i<=n;i++){Node temp=new Node(find1(i), find2(i));System.out.print(map.get(temp)+" ");}}private static void merge1(int u, int v) {int fu=find1(u);int fv=find1(v);if(fu!=fv){fa1[fv]=fu;}// TODO 自动生成的方法存根}private static int find1(int x) {// TODO 自动生成的方法存根if(x==fa1[x])return x;else return fa1[x]=find1(fa1[x]);}private static void merge2(int u, int v) {int fu=find2(u);int fv=find2(v);if(fu!=fv){fa2[fv]=fu;}// TODO 自动生成的方法存根}private static int find2(int x) {// TODO 自动生成的方法存根if(x==fa2[x])return x;else return fa2[x]=find2(fa2[x]);}}
class Node
{int x,y;public Node(int x, int y) {super();this.x = x;this.y = y;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + x;result = prime * result + y;return result;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Node other = (Node) obj;if (x != other.x)return false;if (y != other.y)return false;return true;}}