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

[日常训练]AekdyCoin的跳棋「建议收藏」AekdyCoin正在玩一个游戏,该游戏要用到两副牌和一个数轴和一个棋子。刚开始的时候棋子位于数轴的0位置。然后AekdyCoin交替的从两副牌中抽取一张牌,然后执行相应的动作。设这两幅牌为A

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

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

2

1 1

1 3

2 1 3

1 2

Sample Output

NO

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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155010.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【Qt】Qt的线程(两种QThread类的详细使用方式)「建议收藏」

    【Qt】Qt的线程(两种QThread类的详细使用方式)「建议收藏」Qt提供QThread类以进行多任务处理。与多任务处理一样,Qt提供的线程可以做到单个线程做不到的事情。例如,网络应用程序中,可以使用线程处理多种连接器。QThread继承自QObject类,且提供QMutex类以实现同步。线程和进程共享全局变量,可以使用互斥体对改变后的全局变量值实现同步。因此,必须编辑全局数据时,使用互斥体实现同步,其它进程则不能改变或浏览全局变量值。什么是互斥体?…

  • 使用ES6+工厂模式模拟jquery代码「建议收藏」

    使用ES6+工厂模式模拟jquery代码「建议收藏」使用ES6+工厂模式模拟jquery代码

  • 什么是QT?「建议收藏」

    什么是QT?「建议收藏」为学习QT首先必须搞明白的一个问题是,什么是QT,查找资料,对于QT有如下的认识:1.Qt是一个跨平台的C++图形用户界面应用程序框架Qt是面向对象的框架,提供了一种称为signals/slots的安全类型来实现各个元件之间的协同工作。2.Qt是一个跨平台的应用程序开发类库Qt包括多达250个以上的C++类,还替供基于模板的collections,serialization,file,I/Odevice,directorymanagement,date/t

  • 时间协议ntp服务器,时间服务器NTP搭建及NTP协议简介

    NTP协议简介目前在计算机上同步时间采用的NTP协议,我们可以在局域网中搭建NTP服务器来同步时间。NTP(NetworkTimeProtocol)是用来是计算机时间同步化的一种协议,他可以使计算机对其服务器或时钟源(如石英钟、GPS)做同步化,可以提供高精准度的时间校正。NTP可以通过原子钟、天文台、卫星等渠道获得精准时间,然后再按照NTP服务器等级进行传播。NTP的网络结构是分层管理的类树…

  • 如何彻底的卸载anaconda(包括配置文件)

    如何彻底的卸载anaconda(包括配置文件)如果你想测地卸载anaconda,请看SolutionB。[官方参考链接]。1.SolutionA通常卸载软件,直接运行uninstall就可以了,对于anaconda也一样,可以直接运行安装目录下的Uninstall-Anaconda3.exe即可,但是这样卸载并没有完全卸载。如果需要完全卸载请参考SolutionB2.SolutionB通过B方式卸载,请确保还没有通…

  • hadoop技术论坛日志分析—mapredu最后一步_睿派克技术论坛

    hadoop技术论坛日志分析—mapredu最后一步_睿派克技术论坛http://bbs.hadoopor.comhttp://www.hadoopor.comhttp://forum.hadoopor.comhttp://hadoop.hadoopor.comhtt

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号