codeforces 515B. Drazil and His Happy Friends 解题报告

题目链接：http://codeforces.com/problemset/problem/515/B

题目意思：有 n 个 boy 和 m 个 girl，有 b 个 boy 和 g 个 girl （通过给出数组下标）是 happy的，规定每轮 dinner 中，派出编号为 i mod n 个男 和 i mod m 个女去。只要他们其中一个为 happy 时，另一个也会变得 happy，问最终所有男女是否都变得 happy。

　　一步一步模拟就可以了。这个问题有一个难点，就是究竟要进行多少次才能判断有些男女无论如何都不会happy的。由于数据量不大，只有100。最坏的情况就是每一个男女都有机会组合，所以 100 * 100 次来控制次数就可以了。每次配完对都检查下是否每个男女都已经为 happy，以便尽早结束循环，不要再进行无谓的组合。

　　开 virtual 做的，发现，为什么B比C更加少人做出来。。。（C是完全木有思路 - -）

　　

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int boy[maxn], girl[maxn];

 int n, m;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int b, g;

     while (scanf("%d%d", &n, &m) != EOF) {

         memset(boy, , sizeof(boy));

         memset(girl, , sizeof(girl));

         int in;

         scanf("%d", &b);

         for (int i = ; i < b; i++) {

             scanf("%d", &in);

             boy[in] = ;

         }

         scanf("%d", &g);

         for (int i = ; i < g; i++) {

             scanf("%d", &in);

             girl[in] = ;

         }

         bool flag;

         int stb = , stg = ;

         int cnt = maxn*maxn;

         while (cnt) {

             flag = true;

             stb %= n;

             stg %= m;

             if (boy[stb] || girl[stg]) {   // 其中一个是happy的

                 boy[stb] = ;

                 girl[stg] = ;

             }

             // 检查男女两边是否都已经happy

             for (int i = ; i < n; i++) {

                 if (!boy[i]) {

                     flag = false;

                     break;

                 }

             }

             for (int i = ; i < m; i++) {

                 if (!girl[i]) {

                     flag = false;

                     break;

                 }

             }

             if (flag)

                 break;

             stb++;

             stg++;

             cnt--;

         }

         printf("%s\n", flag ? "Yes" : "No");

     }

     return ;

 }