J. Deck Shuffling
Time Limit: 2
Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/gym/100187/problem/J
Description
The world famous scientist Innokentiy continues his innovative experiments with decks of cards. Now he has a deck of n cards and k shuffle machines to shuffle this deck. As we know, i-th shuffle machine is characterized by its own numbers pi, 1, pi, 2, ..., pi, n such that if one puts n cards numbered in the order 1, 2, ..., n into the machine and presses the button on it, cards will be shuffled forming the deck pi, 1, pi, 2, ..., pi, n where numbers pi, 1, pi, 2, ..., pi, n are the same numbers of cards but rearranged in some order.
At the beginning of the experiment the cards in the deck are ordered as a1, a2, ..., an, i.e. the first position is occupied by the card with number a1, the second position — by the card with number a2, and so on. The scientist wants to transfer the card with number x to the first position. He can use all his shuffle machines as many times as he wants. You should determine if he can reach it.
Input
In the first line the only positive integer n is written — the number of cards in the Innokentiy's deck.
The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n) — the initial order of cards in the deck.
The third line contains the only positive integer k — the number of shuffle machines Innokentiy has.
Each of the next k lines contains n distinct integers pi, 1, pi, 2, ..., pi, n (1 ≤ pi, j ≤ n) characterizing the corresponding shuffle machine.
The last line contains the only integer x (1 ≤ x ≤ n) — the number of card Innokentiy wants to transfer to the first position in the deck.
Numbers n and k satisfy the condition 1 ≤ n·k ≤ 200000.
Output
Output «YES» if the scientist can transfer the card with number x to the first position in the deck, and «NO» otherwise.
Sample Input
4
4 3 2 1
2
1 2 4 3
2 3 1 4
1
Sample Output
YES
HINT
题意
给你一堆牌的原始顺序，给你k个洗牌机，给你每次使用完洗牌机之后的顺序，问能否洗到第一张牌是x的情况
题解：
dfs无脑
代码
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <ctime> 5 #include <iostream> 6 #include <algorithm> 7 #include <set> 8 #include <vector> 9 #include <queue> 10 #include <map> 11 #include <stack> 12 #define MOD 1000000007 13 #define maxn 32001 14 using namespace std; 15 typedef __int64 ll; 16 inline ll read() 17 { 18 ll x=0,f=1; 19 char ch=getchar(); 20 while(ch<'0'||ch>'9') 21 { 22 if(ch=='-')f=-1; 23 ch=getchar(); 24 } 25 while(ch>='0'&&ch<='9') 26 { 27 x=x*10+ch-'0'; 28 ch=getchar(); 29 } 30 return x*f; 31 } 32 //******************************************************************* 33 struct ss 34 { 35 36 int to,next; 37 } edg[500000]; 38 int st; 39 bool flag; 40 int t=0; 41 int visit[200005]; 42 int head[200005]; 43 int n; 44 void init() 45 { 46 t=1; 47 memset(head,0,sizeof(head)); 48 } 49 void add(int u,int v) 50 { 51 edg[t].to=v; 52 edg[t].next=head[u]; 53 head[u]=t++; 54 } 55 bool NO; 56 void dfs(int x) 57 { 58 if(flag)return ; 59 if(x == 1) 60 { 61 flag=true; 62 return; 63 } 64 if(visit[x])return ; 65 visit[x]=true; 66 for(int i=head[x]; i; i=edg[i].next) 67 { 68 if(visit[edg[i].to])continue; 69 dfs(edg[i].to); 70 } 71 } 72 int main() 73 { 74 int a[200005]; 75 n=read(); 76 init(); 77 for(int i=1; i<=n; i++) 78 { 79 a[i]=read(); 80 } 81 int m,x; 82 m=read(); 83 for(int i=1; i<=m; i++) 84 { 85 for(int j=1; j<=n; j++) 86 { 87 x=read(); 88 if(x!=j) 89 { 90 add(x,j); 91 } 92 } 93 } 94 st=read(); 95 for(int i=1; i<=n; i++) 96 { 97 if(a[i]==st) 98 { 99 st=i; 100 break; 101 } 102 } 103 flag=false; 104 dfs(st); 105 if(flag)printf("YES "); 106 else printf("NO "); 107 return 0; 108 }