JZOJ 5777. 【NOIP2008模拟】小x玩游戏

Description

今天，小x因为太无聊，就在玩游戏。这个游戏有两个队伍，然后他们在游戏里面打来打去。
但小x遇到了难题。他不知道自己的队友是谁。他只知道总共有两个队伍，每队有n个人和很多组击杀情况。他想问你，现在他能否知道两个队伍分别有谁。你可以帮助小x吗？由于小x是个游戏狂魔，所以他玩了很多局游戏。

Input

第一行有一个t，表示小y共玩了t局游戏。
接下来有t组数据，每组数据第一行有一个n,m，表示每队有n个人，有m组击杀情况，接下来m行每行两个字符串s1，s2，表示s1杀了s2，其中s1，s2的长度均不超过10（数据保证两个字符串都由小写字母组成）。注意一个人可以被击杀多次、一个人可以被曾经杀死过的人给杀死。

Output

总共有t行，每行一个“YES”或“NO”，YES表示符合题目条件，NO表示不符合。

Sample Input

1
2 3
a b
c d
a d

Sample Output

 YES

样例解释：
a，c是一队，b，d是一队。

Data Constraint

数据范围：
对于30%的数据，n<=1000,m<=10000；
对于100%的数据，t<=10，n<=2000，m<=100000。
数据保证不会有矛盾的关系。

做法：数据保证不矛盾就很好写啦╭(╯^╰)╮，并查集啊dfs啊随便搞搞，然后字符串hash一下就好啦

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <string>
  5 #define MO 10000000009
  6 #define mo 233437
  7 #define LL long long
  8 using namespace std;
  9 LL t, n, m, ls[mo + 20], tot, cnt, A, B;
 10 struct arr
 11 {
 12     int to, next;
 13 }e[mo];
 14 string st;
 15 bool b[mo + 20];
 16 LL h[mo + 1];
 17 LL H[11];
 18 
 19 void Add(int x, int y)
 20 {
 21     e[++cnt].to = y;
 22     e[cnt].next = ls[x];
 23     ls[x] = cnt;
 24 }
 25 
 26 LL Hash(LL p)
 27 {
 28     int g = p % mo;
 29     for (; h[g] != 0 && h[g] != p; g = (g + 1) % mo);
 30     return g;
 31 }
 32 
 33 void Init()
 34 {
 35     scanf("%d%d", &n, &m);
 36     for (int i = 1; i <= m; i++)
 37     {
 38         cin >> st;
 39         LL u = 0, v = 0, t1, t2;
 40         memset(H, 0, sizeof(H));
 41         for (int i = 0; i < st.size(); i++)
 42             H[i + 1] = ((H[i] + st[i] - 'a' + 1) * 61) % MO;
 43         u = H[st.size()];
 44         v = Hash(u);
 45         h[v] = u;
 46         t1 = v;
 47         memset(H, 0, sizeof(H));
 48         cin >> st;
 49         for (int i = 0; i < st.size(); i++)
 50             H[i + 1] = ((H[i] + st[i] - 'a' + 1) * 61) % MO;
 51         u = H[st.size()];
 52         v = Hash(u);
 53         h[v] = u;
 54         t2 = v;
 55         Add(t1, t2);
 56         Add(t2, t1);
 57     }
 58 }
 59 
 60 void Dfs(int x, int D)
 61 {
 62     if (D)    A++;
 63     else B++;
 64     for (int i = ls[x]; i; i = e[i].next)
 65     {
 66         if (b[e[i].to]) continue;
 67         b[e[i].to] = 1;
 68         Dfs(e[i].to, D ^ 1);
 69     }
 70 }
 71 
 72 void Work()
 73 {
 74     A = 0, B = 0;
 75     int j = 0;
 76     while (!h[j]) j++;
 77     b[j] = 1;
 78     Dfs(j, 1);
 79     if ((A & B & n) == n)
 80     {
 81         printf("YES
");
 82         return;
 83     }
 84     printf("NO
");
 85     return;
 86 }
 87 
 88 int main()
 89 {
 90     freopen("game.in", "r", stdin);
 91     freopen("game.out", "w", stdout);
 92     scanf("%d", &t);
 93     for (; t; t--)
 94     {
 95         memset(ls, 0, sizeof(ls));
 96         memset(e, 0, sizeof(e));
 97         memset(b, 0, sizeof(b));
 98         memset(h, 0, sizeof(h));    
 99         cnt = 0;
100         Init();
101         Work();
102     }
103 }

View Code