Drazil and His Happy Friends
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,否则输出NoSample Input
输入样例1: 2 3 0 1 0 输入样例2: 2 4 1 0 1 2 输入样例3: 2 3 1 0 1 1Sample Output
输出样例1: Yes 输出样例2: No 输出样例3: Yes sol:暴力枚举就可以,显然枚举到max(n,m)*n*m是可以的,但没必要这么大,只要到2*n*m就可以了(应该十分显然吧)#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