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

浏览数：22 / 时间：2015年06月11日

题目链接：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是完全木有思路 - -）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 5;
 8 int boy[maxn], girl[maxn];
 9 int n, m;
10 
11 int main()
12 {
13     #ifndef ONLINE_JUDGE
14         freopen("in.txt", "r", stdin);
15     #endif // ONLINE_JUDGE
16 
17     int b, g;
18     while (scanf("%d%d", &n, &m) != EOF) {
19         memset(boy, 0, sizeof(boy));
20         memset(girl, 0, sizeof(girl));
21 
22         int in;
23         scanf("%d", &b);
24         for (int i = 0; i < b; i++) {
25             scanf("%d", &in);
26             boy[in] = 1;
27         }
28         scanf("%d", &g);
29         for (int i = 0; i < g; i++) {
30             scanf("%d", &in);
31             girl[in] = 1;
32         }
33         bool flag;
34         int stb = 0, stg = 0;
35         int cnt = maxn*maxn;
36         while (cnt) {
37             flag = true;
38             stb %= n;
39             stg %= m;
40             if (boy[stb] || girl[stg]) {   // 其中一个是happy的
41                 boy[stb] = 1;
42                 girl[stg] = 1;
43             }
44             // 检查男女两边是否都已经happy
45             for (int i = 0; i < n; i++) {
46                 if (!boy[i]) {
47                     flag = false;
48                     break;
49                 }
50             }
51             for (int i = 0; i < m; i++) {
52                 if (!girl[i]) {
53                     flag = false;
54                     break;
55                 }
56             }
57             if (flag)
58                 break;
59             stb++;
60             stg++;
61             cnt--;
62         }
63         printf("%s\n", flag ? "Yes" : "No");
64     }
65     return 0;
66 }