Chlience

【题解】POJ 2484 A Funny Game
Problem给定 $n$ 枚硬币围成一圈,每次可以取走一个或者相邻的两个,空位保留,不能操作者败问谁能获胜?Th...
扫描右侧二维码阅读全文
18
2019/02

【题解】POJ 2484 A Funny Game

Problem

给定 $n$ 枚硬币围成一圈,每次可以取走一个或者相邻的两个,空位保留,不能操作者败

问谁能获胜?

Thought

发现只有第一次是个环,后面都是很多的链
然后第一次的环又没有什么用,所以说直接考虑链的情况就好了

设 $sg[i]$ 表示长度为 $i$ 的链的 $SG$ 函数
状态 $x$ 能够进行的转移为:

$$ sg[x]=mex\{sg[i]\oplus sg[x-i-1],sg[i]\oplus sg[x-i-2]\} $$

朴素计算是 $O(n^2)$ 的,显然不能接受啊

打表观察发现, $sg[x]\ge[x=0]$ ,也就是说,一条链的情况永远是先手必胜
换句话说,对于任意长度 $>2$ 的环,后手必胜

但是为什么呢?

考虑在链上的情况,先手总能找到一个位置使得链被分为两段长度相等的链,然后对于后手的每一个操作,其做对称操作即可

此即为对称博弈

Code

#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int main() {
    while(1) {
        int n = read();
        if(!n) break;
        puts(n <= 2 ? "Alice" : "Bob");
    }
    return 0;
}
Last modification:February 20th, 2019 at 08:32 am

Leave a Comment