Codeforces 630R Game

题目链接:http://codeforces.com/problemset/problem/630/R

题意:给一个n\*n的棋盘,两名玩家轮流操作,每次每个人可以在一个上下左右都没有放棋子的地方放上棋子,最后谁不能操作谁输,问最后先手胜负状况。

思路:自己是打了个必胜必败态的表然后发现了结论,即奇数先手必胜,偶数先手必败,考虑证明就是,如果是偶数的棋盘,先手在(i,j)上放了一个棋子的时候,后手可以完全模仿着在对称的地方放上一个棋子,比如先手放(1,1),那么后手放(n,n),只要先手能放那么后手一定能找到其对称的位置,这样最后肯定是以先手不能移动落败,奇数就是相当于先手在中心位置放棋子,剩下来后手怎么放他对称着放就赢了。

打表程序

const int N=100+10;
int i;
bool maze[N][N];
int dir_x[]={0,1,0,-1};
int dir_y[]={1,0,-1,0};
bool check(int x,int y){
    for (int l=0;l<4;l++){
        int tx=x+dir_x[l];
        int ty=y+dir_y[l];
        if (tx<1||tx>i||ty<1||ty>i) continue;
        if (maze[tx][ty]) return 0;
    }
    return 1;
}
bool dfs(){
    for (int j=1;j<=i;j++){
        for (int k=1;k<=i;k++)if(!maze[j][k]&&check(j,k)){
            maze[j][k]=1;
            bool res=dfs();
            if (res==0) return 1;
            maze[j][k]=0;
        }
    }
    return 0;
}
int main(){
    for (i=1;i<=100;i++){
        memset(maze,0,sizeof(maze));
        bool res=dfs();
        printf("%d ",i);
        if (res==1) puts("1");
        else puts("2");
    }
    return 0;
}

答案

int main(){
    ll n;
    cin>>n;
    puts(n&1?"1":"2");
    return 0;
}

发表评论

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