[日常训练]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)


相关推荐

  • android一键换机功能实现,不同品牌手机一键换机教程「建议收藏」

    android一键换机功能实现,不同品牌手机一键换机教程「建议收藏」我们正处于一个数码产品更新换代非常快速的时代,很多消费者会紧跟时代潮流,经常更换新手机,但是更换手机之后我们通常需要将旧手机里的数据进行转移,不同品牌之间的手机怎么进行一键换机呢?以安卓手机更换苹果手机转移数据为例:1、首先我们需要在安卓手机上安装“转移到iOS”APP,通过该应用我们可以将安卓手机的数据转移到新的苹果手机上2、确保安卓设备处于WiFi状态3、将安卓设备以及苹果设备连接电源4、设置…

  • 常用图像算法汇总_图像修复算法

    常用图像算法汇总_图像修复算法图12020年中国计算机视觉在职人员研究领域兴趣变化2021年中国计算机视觉在学术界和产业界各领域热度排名1.目标检测常用算法:yolov3、v4、v5。2.底层视觉与图像处理潜在应用:由于外界环境影响,导致图像成像效果不尽人意,从而影响后续对视频图像的处理。2.1图像超分辨率超分辨率(SuperResolution,SR)是从给定的低分辨率(LR)图像中恢复高分辨率(HR)图像的过程,是计算机视觉的一个经典应…

  • termux安装ssh服务_python ssh连接

    termux安装ssh服务_python ssh连接pycharm下载、使用与远程连接服务器下载安装pycharm配置Deployment同步设置配置远程python解释器其他设置*环境变量*cannotconnecttoXserver*Pycharm运行程序给argparse指定参数*Pycharm打开连接服务器的终端下载安装pycharm如果要远程连接服务器,需要安装pycharmprofessional版本,从官网上下载并安装https://www.jetbrains.com/pycharm/download/#section=

  • Java Eclipse自动补全设置[通俗易懂]

    Java Eclipse自动补全设置[通俗易懂]Eclipse代码自动补全功能默认只包括点”.” ,即只有输入”.”后才出现自动补全的提示框。想要自动补全总是去按“Alt+/”也很麻烦。其实只需简单在Eclipse中进行设置即可实现输入任意及符合自动出现自动补全提示框。具体设置步骤如下:   选择Eclipse菜单条中的Windows菜单下的Preferences项。在左侧找到“Java”=》“Editor”=》

  • 十分钟搞懂Pytorch如何读取MNIST数据集

    前言本文用于记录使用pytorch读取minist数据集的过程,以及一些思考和疑惑吧…正文在阅读教程书籍《深度学习入门之Pytorch》时,文中是如此加载MNIST手写数字训练集的:train_dataset=datasets.MNIST(root=’./MNIST’,train=True,transform=data_tf,download=True)解释一下参数datasets.MNIST是Pytorch的内置函数torchvision.datasets.MNIST,通过这个可以导入数

  • 移动硬盘写入数据报错“MS-DOS功能无效”,或移动硬盘内新建文件夹报错0x8000FFFF灾难性错误

    移动硬盘写入数据报错“MS-DOS功能无效”,或移动硬盘内新建文件夹报错0x8000FFFF灾难性错误问题已解决,文章有点长,请耐心观看,包含遇到的问题和解决问题地过程。楼主近来新买了机械个硬盘,闲鱼出品,必属精品,主要是用来存储一些很有纪念意义的文件和平时用不到的文件,估计以后用到这些文件的机会应该很少了,一般来说机械硬盘虽然比固态硬盘不禁摔,但是存储数据的时间更长,很适合我的需求。晚上一股脑把数据存进去的时候,2T的硬盘大概存了150G之后开始报错。先是放入文件夹时显示【MS-DOS功能无效】,无法写入,我把文件夹内单个文件写入硬盘,可行,但不可能把各种类型的文件直接放进硬盘。我尝试新建文

发表回复

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

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