codeforces 346A Alice and Bob 简单博弈

题目链接:https://codeforces.com/problemset/problem/346/A
题目大意:给你一个数组,有n个不同的数。然后小A和小B轮流玩游戏,找出两个数的绝对值的差|x-y|,如果数组中不存在这个数的话,就把这个数添加到数组中;如果实在找不出来两个数的差,既|x-y|,总是在数组中存在,那么这个同学就输了。
举个例子。比如,数组元素是1,3。那么第一个同学,只能将|3-1|为2存进去。这个时候数组就是1,2,3。此时,任何两个数的差的绝对值都在数组里,所以第一个同学就赢了。
如果多举几个例子,很容易发现一个规律,如果两个数啊a,b互质的话,那么就可以构造出1~max(a,b)所有的数,先假设这个规律是正确的,暂时还不会证明0.0,但是感觉吧一定是对的0.0。
举个例子:
比如 3,11;
然后是3,8,11;
然后是3,5,8,11;
然后是2,3,5,8,11;
然后是1,2,3,5,8,11。
如果有了1,就可以把1到11所有的数构造出来了。
还能得到一个结论,如果一开始数组中存在任意两组数a,b互质的话,如果数组中还有c>=max(a,b),那么1~c所有的整数都可以构造出来,因为只要有1,那么1到一个数之间所有的数都可以都早出来。
再进一步,就可以推到本题的答案,如果数组中存在一组(a,b)互质,那么之需要判断,(数组中最大的数max-数组个数n)的是奇数还是偶数就可以了。
如果数组中任意一组(a,b)都不互质,那么可以可以求出数组所有的元素的最大公约数,约掉后,数组中就存在互质对了,然后就可以按照上一步做了。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =101;
int num[maxn];
int gcd(int a,int b)
{
   return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,flag;
    while(cin>>n)
    {
        flag=1;
        for(int i=0;i<n;i++)
        {
            cin>>num[i];
        }    
        
        sort(num,num+n);
            
        for(int i=0;i<n-1;i++)        //判断是否有互质对 
        {
            for(int j=i+1;j<n;j++)
            {
                if(gcd(num[i],num[j])==1)
                {
                    flag=0;
                }
            }
        }
        
        int ans=0;
        
        if(!flag){                //有的话,直接判断ans的奇偶性 
            ans=num[n-1]-n;            
        }else                    //没有的话,用res寻找所有的元素的最大公约数 
        {
            int res=gcd(num[0],num[1]);
            for(int i=2;i<n;i++)
            {
                if(res>gcd(res,num[i]))
                {    
                    res=gcd(res,num[i]);
                }
            }
            ans=(num[n-1]/res)-n;    //实际上把最大的数化简就可以了    
        }
        if(ans&1)                
        {
            cout<<"Alice"<<endl;
        }else 
        {
            cout<<"Bob"<<endl;
        }
    }     
    return 0;
}turn 0;
}
Last modification:June 20th, 2020 at 11:02 pm
如果觉得我的文章对你有用,请随意赞赏

3 comments

  1. YGYG
    该评论仅登录用户及评论双方可见
    1. YGYG
      @YGYG
      该评论仅登录用户及评论双方可见
      1. 子不语
        @YGYG

        嗯嗯,有啥问题尽管问,大家一起学习233

Leave a Comment