codeforces515B

Drazil and His Happy Friends

 CodeForces - 515B 

Drazil有很多朋友,他们中有些人是快乐的,有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是,他发明了以下的计划。   在他的朋友中,有n个男孩和m个女孩。我们把男孩从0到n-1编号,女孩从0到m-1编号。在第i天,Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭(注意i从0开始)。如果两个人之中有一个是快乐的,那么另外一个也会变得快乐,否则,这两个人的心情状态不会改变。一个人一旦成为快乐的人(或者他原本就是快乐的),他能保持永远快乐。   Drazil想知道他是否可以使用该计划,使得他所有的朋友都变得快乐。

Input

  第一行包含两个整数n和m(1≤n,m≤100)。   第二行包含整数b(0≤b≤n),表示Drazil的男生朋友中目前是快乐男生的数量,然后有b个不同的整数X1,X2,...,Xb(0≤Xi<n),表示这些快乐男生的编号。   第三行包含整数g(0≤g≤m),表示Drazil的女生朋友中目前是快乐女生的数量,然后有g个不同的整数Y1,Y2,...,Yg(0≤Yj<m),表示这些快乐女生的编号。   题目保证输入数据中至少有一个人不快乐。

Output

  如果 Drazil能使得所有的朋友都变得快乐,就输出Yes,否则输出No

Sample Input

输入样例1: 2 3 0 1 0   输入样例2: 2 4 1 0 1 2   输入样例3: 2 3 1 0 1 1

Sample Output

输出样例1: Yes   输出样例2: No   输出样例3: Yes   sol:暴力枚举就可以,显然枚举到max(n,m)*n*m是可以的,但没必要这么大,只要到2*n*m就可以了(应该十分显然吧) codeforces515B
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=105;
int n,m;
bool Boy[N],Girl[N];
int main()
{
    int i,cnt;
    R(n); R(m);
    R(cnt); for(i=1;i<=cnt;i++) Boy[read()]=1;
    R(cnt); for(i=1;i<=cnt;i++) Girl[read()]=1;
    for(i=1;i<=((n*m)<<1);i++) if(Boy[i%n]||Girl[i%m])
    {
        Boy[i%n]=Girl[i%m]=1;
    }
    for(i=0;i<n;i++) if(!Boy[i]) return 0*puts("NO");
    for(i=0;i<m;i++) if(!Girl[i]) return 0*puts("NO");
    puts("YES");
    return 0;
}
View Code

 

上一篇:vector容器


下一篇:Drazil and Tiles CodeForces - 516B (类拓扑)