codeforces gym 100463I Yawner

//这题挂得让我怀疑我最近是不是做了什么坏事

题意:一个人有两个集合,先在其中一个集合选一个数x,然后向右走x布,然后再在另一个集合里选一个数y,向左走y步,问是否能走完数轴上所有点。

解:显然是求gcd(ai-bj)的值是不是1,然后有gcd(ai-bj)=gcd(ai-b1,ai-b2,ai-b3,........)=gcd(ai-b1,b2-b1,b3-b1,b4-b1.....)=gcd(gcd(ai-b1),gcd(bj-b1)),然后就可以把a,b分开求了。另外假如求出来gcd值是2,那么要特殊讨论a中是否有奇数,即 即我们先前的假设是步数一样,但实际上a可以比b多走一步。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string>
#define LL long long const int MAXN=;
const int MAXM=;
const int INF=; using namespace std; int a[MAXN],b[MAXN];
int n,m,cas=; int gcd(int a,int b){
if (b==) return a;
return gcd(b,a%b);
} bool check(int x){
if (x>) return ;
bool flag=;
for (int i=;i<n;i++){
if (a[i]&) flag=true;
}
if (x== && !flag) return ;
return ;
} int main(){
while (scanf("%d%d",&n,&m)==){
if (n== && m==) break;
cas++;
for (int i=;i<n;i++) scanf("%d",&a[i]);
for (int i=;i<m;i++) scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+m);
if (a[n-]<b[] || a[]>b[m-]){
printf("Case %d: YES\n",cas);
continue;
}
int ans=a[]-b[];
for (int i=;i<n;i++) ans=gcd(ans,a[i]-b[]);
for (int i=;i<m;i++) ans=gcd(ans,b[i]-b[]);
if (!check(abs(ans))){
printf("Case %d: YES\n",cas);
}
else{
printf("Case %d: NO\n",cas);
}
}
return ;
}
/*
2 2
1
3
1
3 2 5
10
20
1
2
3
4
5
3 3
3
6
9
3
6
9
2 2
1
2
1
2
0 0
*/
上一篇:Android 音视频深入 四 录视频MP4(附源码下载)


下一篇:如何将代码托管到GitHub上