[日常训练]AekdyCoin的跳棋「建议收藏」

全栈程序员-站长 • 2022年7月1日下午11:36 • 未分类 • 阅读 17

大家好，又见面了，我是你们的朋友全栈君。

Description

$AekdyCoin$正在玩一个游戏，该游戏要用到两副牌和一个数轴和一个棋子。

刚开始的时候棋子位于数轴的$0$位置。然后$AekdyCoin$交替的从两副牌中抽取一张牌，然后执行相应的动作。

设这两幅牌为$A,B$。每张牌上面有一个整数$x$，表示$AekdyCoin$可以前进的格数。从$A$中抽牌，则必须向左走$x$个单位；从$B$中抽牌则必须向右走$x$个单位。

现在要求第一次必须从$A$中抽牌，且必须轮流从两幅牌中抽，即抽完$A$后必须抽$B$,抽完$B$后必须抽$A$。

$AekdyCoin$在玩这个游戏的时候想到了一个问题，如果数轴是无限的，那么棋子有无可能到达任意的整数点呢？

Input

第一行有一个整数$T(1\;\leq\;T\;\leq\;5)$代表有$T$组数据。

每组数据的格式如下：

开头给出$A$牌中的牌数量$N$。然后接下去有$N$个数，代表$A$牌中各个牌上面标的整数。

而后给出$B$牌中的牌数量$M$。然后接下去有$M$个数，代表$B$牌中各个牌上面标的整数。

Output

对于每组测试点输出$YES$或者$NO$来代表题目给出的问题。

Sample Input

1 1

1 3

2 1 3

1 2

Sample Output

YES

HINT

$1\;\leq\;N,M\;\leq\;10^5$;牌上面的整数在$[1,10^9]$之间。

Solution

跳的顺序为$ABABAB……$

跳偶数步

构造序列$c=\{x|x=-a_i+b_j\}$,

则一个$AB$可以看成从$c$中选择一个元素来跳.

$c$能到达的任何一个数记为:$k=x_1c_1+x_2c_2+…+x_nc_n$,则$k$所能表示的最小正整数为$gcd(c)$,即所有非负$gcd(c)$的倍数都能到达.

然后$c$中必须有正数和负数才能到达数轴上所有$gcd(c)$的倍数的点.

跳奇数步

因为跳偶数步只能遍历数轴上所有$gcd(c)$的倍数的点,所以$a_i\;mod\;gcd(c)$要满足取遍[1,gcd(c)),这样才能将数轴剩下的点都跳到.

$gcd(c)=gcd(a_i-b_k,a_j-b_k…)$.

$a_i-b_k-(a_j-b_k)=a_i-a_j$,整除$gcd(c)$.

这说明$a$关于模$gcd(c)$同余.

结论

若$c$里面都是非正或者非负,则$NO$;

若$gcd(c)=1$,则$YES$;

若$gcd(c)=2$,且$a_i\;mod\;2=1$,则$YES$,否则$NO$;

若$gcd(c)>2$,则根据$a$关于$gcd(c)$同余可知，$a_i\;mod\;gcd(c)$不可能取遍[1,gcd(c)),所以$NO$.

计算$gcd(c)$

$c_{i,j}=-a_i+b_j=(b_j-b_1)+(b_1-a_1)+(a_1-a_i)$.

只需计算$gcd(b_j-b_1,b_1-a_1,a_1-a_i)$.

#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
using namespace std;
typedef long long ll;
int a[N],b[N],n,m,k,t;
bool flag;
inline int gcd(int x,int y){
    if(x<0) x=-x;
    if(y<0) y=-y;
    int r=x%y;
    while(r){
        x=y;y=r;r=x%y;
    }
    return y;
}
inline void Aireen(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        a[1]=0;
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;++i)
            scanf("%d",&b[i]);
        sort(a+1,a+1+n);
        sort(b+1,b+1+m);
        if((ll)(b[1]-a[n])*(ll)(b[m]-a[1])>=0ll){
            puts("NO");continue;
        }
        if(b[1]!=a[1]) k=gcd(b[1]-a[n],b[1]-a[1]);
        else k=b[1]-a[n];
        for(int i=1;i<=n;++i)
            if(a[i]!=a[1]) k=gcd(k,a[i]-a[1]);
        for(int i=1;i<=m;++i)
            if(b[i]!=b[1]) k=gcd(k,b[i]-b[1]);
        if(k==1||(k==2&&(a[1]&1))){
            puts("YES");continue;
        }
        puts("NO");
    }
}
int main(){
    freopen("draughts.in","r",stdin);
    freopen("draughts.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155010.html原文链接：https://javaforall.net