【noip模拟赛10】数字游戏

描述

大家列队后,都觉得累了,于是一起坐到院子中的草地上休息。这时Anna突然想跟她的最大竞争对手Cici玩一个数字游戏,她要你编写程序帮助她取得胜利。

第i次游戏初始时有一个整数N_i(1 <= N_i <= 1,000,000),,游戏以Anna先开始,然后是Cici,这样两人轮流进行。在每一轮中,一个游戏者可以把当前整数中减去原整数中最大的数字或最小的非零数字,形成一个新的整数。例如从3014开始,我们可以减去1或4,分别形成整数3013或3010.直到这个整数变为0时游戏结束。游戏结束时最后轮到那人就是胜利者。

Anna和Cici总共进行G(1 <= G <= 100)次游戏。请你帮助确定每次游戏到底是Anna还是Cici获得胜利。Anna和Cici两人都是足够聪明的,如果轮到某人时,对方留给她的数是必胜的,她将毫不犹豫按最优策略取得胜利。

假如某次游戏N_i=13。Anna先走并从中减去3,剩下10,然后Cici只能减去1,剩下9,Anna减去9,剩下0游戏结束,Anna取得这次游戏的胜利。

输入

*第1行:一个整数G

*第2..G+1行:第i+1行包含一个整数: N_i

输出

*第1..G行:第i行包含”YES”,表示Anna取得第i次游戏的胜利,否则为”NO”。

输入样例 1 

2
9
10

输出样例 1

YES
NO

博弈论,可以用sg函数解决。
首先对于1-9,可以一次拿完,因此设sg[1]-sg[9]为1;即先手必胜,考虑10的情况,此时10可以转换为9,而9的sg为1,因此对于10的mex操作(从0,1,2,3···)中选出最小的没出现过的数,此时为0,那么sg[10]=0,即先手必输。

那么对于之后的每个数我们都可以通过他转换出的两个数利用mex求出sg值,预处理出所有的sg后o(1)输出就可以了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e6)+100
#define mod int(1e9)+7
using namespace std;
int mx(int x){
    int ans=0;
    while(x){
        if(x%10!=0){
            ans=max(ans,x%10);
        }
        x/=10;
    }
    return ans;
}
int mix(int x){
    int ans=11;
    while(x){
        if(x%10!=0){
            ans=min(ans,x%10);
        }
        x/=10;
    }
    return ans;
}
int main(){
    int T;sc(T);
    int sg[maxn];
    rep(i,1,9) sg[i]=1;
    rep(i,10,maxn){
        int maxx=mx(i);
        int minx=mix(i);
        rep(k,0,2){
            if(sg[i-maxx]!=k&&sg[i-minx]!=k){
                sg[i]=k;
                break;
            }
        }
    }
    while(T--){
        int x;sc(x);
        if(sg[x]) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 

发表评论,支持MarkDown语法