快乐传递政治正确版

Posted on Edited on In

题目大意:David 的朋友中有 n 个男生和 m 个女生, 还有 k 个跨性别者，方便起见，将他们分别编号为 0,...,n−1 和 0,...,m−1, 0,...,k−1.在第i 天，David会邀请编号为 (i mod n) 的男生和编号为 (i mod m) 的女生还有 (i mod k)的跨性别者共进晚餐（因为 David 同时是程序员，所以从这个计划从第 0天开始）。共进晚餐的三个人只要至少有有一个是快乐的人，另外的人也会变得快乐起来。否则大家的状态不会改变（一旦一个人是快乐的，他就会永 远快乐下去）。现在问题来了，David 想知道他是否能通过这个计划使得所有人都快乐起来呢？

先不考虑三个,考虑两个,然后打表就可以发现这么一个结论:编号之差为\(\gcd(n,m)\)的倍数的男/女生吃饭对象是一样的

得出性质:同一个等价类里面,只要有一个人是快乐的,那么其他人一定快乐

得出算法:先求出来d=gcd,然后根据每个人的id模以d的余数分成d个等价类,保证所有的等价类都快乐,也就可以保证所有的人们都快乐

所以只需要检查快乐的人们的编号是否覆盖了0~gcd-1里面的每一个数字

当发现gcd大于300000(快乐的人们最多就是三千个)的时候,就直接no因为即使300000内的每个数字都是一个等价类,也没法满足比300000多,比gcd少的部分

拓展到三个人类似.

代码如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 3e5 + 33;

int T, n, m, k;
int vis[N];

inline void yhm_clear()
{
    memset(vis, 0, sizeof vis);
    return;
}

inline void yhm_func()
{
    int i, b, g, t, gcd, pd(1);
    n = read(), m = read(), k = read();
    gcd = __gcd(n, m), gcd = __gcd(gcd, k);
    if (gcd > 300000) pd = 0, gcd = 1;

    b = read(); for (i = 1; i <= b; ++ i) vis[read() % gcd] = 1;
    g = read(); for (i = 1; i <= g; ++ i) vis[read() % gcd] = 1;
    t = read(); for (i = 1; i <= t; ++ i) vis[read() % gcd] = 1;
    for (i = 0; i < gcd; ++ i) if (! vis[i]) pd = 0;

    puts(pd ? "Yes" : "No");
    return;
}

signed main()
{
    T = read();
    while (T --)
    {
        yhm_clear();
        yhm_func();
    }
    return 0;
}

后记:

考场后来有时间,也犯懒了,心态不端正.需要改善.

其实是个思维好题,打个表看看就出来了,也不难