SDUT4541-小志志和小峰峰的日常(博弈)

题目链接

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2956/pid/4541

解题思路

我们需要分类讨论:
x == y 的时候:经典的 sg
x != y 的时候:
任意的 a[i] <= min(x, y):Nim 博弈
否则至少存在一堆 a[i] > min(x, y):
如果 x > y:
我们把先手能拿的石子个数看成 y 的话,就是经典的 sg,如果亦或和不是 0 那么先手必
胜。
如果亦或和是 0,那么先手可以选择石子个数大于 y 的堆,拿掉 y+1 的石子个数。这样对
于对方而言亦或和还是 0。所以先手必胜。
所以无论如何:先手必胜
如果 x < y:
如果石子堆个数 > min(x, y) 的堆数大于等于 2:后手必胜,先手无论如何处理都会变成上述的
情况。
如果石子堆个数 > min(x, y) 的堆数 == 1:
先手肯定会选择 > min(x, y) 的石子堆进行操作,不然先手必败。
设这堆石子个数为 t,除去这堆石子的亦或和为 ans,你只有将这堆石子个数变成 ans &&
ans <= x 才能赢。
所以 t­x <= ans && ans <= x 先手必胜。
否则先手必败。

参考题解:华为杯山东理工大学校赛官方题解

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
void show(int ans){
    if(ans)cout<<"xzz"<<endl;
    else cout<<"xff"<<endl;
}
int a[maxn];
int main()
{
    int n,x,y,t,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        cin>>x>>y;
        if(x==y){
            ans=0;
            for(int i=0;i<n;i++){
                ans^=a[i]%(x+1);
            }
            show(ans);
        }
        else{
            int flag=0,ans=0;
            for(int i=0;i<n;i++){
                ans^=a[i];
                if(a[i]>min(x,y)){
                    flag++;
                }
            }
            if(!flag)show(ans);
            else{
                if(x>y)cout<<"xzz"<<endl;
                else{
                    if(flag>1)cout<<"xff"<<endl;
                    else{
                        int t;
                        for(int i=0;i<n;i++){
                            if(a[i]>min(x,y)){
                                t=a[i];
                                ans^=a[i];
                                break;
                            }
                        }
                        if(t-ans<=x&&ans<=x){
                            cout<<"xzz"<<endl;
                        }
                        else cout<<"xff"<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注