第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）E Seek the Joker II题解

题目
题意概括一下就是：有n张牌，每个人可以从牌顶或牌底抽若干张（至少抽1张），或从牌顶和牌底抽走同样张数，抽中从上往下第x张的输，问先手是否有必胜策略

首先，我们转化一下，设a=x-1，b=n-x，即a为x上面有几张牌，b为下面有几张
当a=b=0时，先手无必胜策略，因为先手只能抽走这一张牌
当a，b其中一个是0，先手有必胜策略，因为先手可以从一端抽牌，只剩一张，后手便必输
当a=b时，先手有必胜策略，先手可以从两端抽走相同张数的牌，只剩一张
剩下的情况，一开始看的时候，还是没有想法，所以我先列了张表：（“√”“×”代表先手是否有必胜策略）

只列一半是因为a，b交换是一样的情况，a=b的情况也讨论过了
我们来分析每一个格子里的情况
a=2,b=1时，通过列举每种情况得知先手没有必胜策略
a>2,b=1时，先手可以先在a的一段抽走若干，使变成a=2,b=1情况，所以先手有必胜策略
a>2,b=2时，先手可以先在a的一段抽走若干，使变成a=1,b=2也就是a=2,b=1情况，所以先手有必胜策略
a=4,b=3时，先手可以在两端拿走两张，使变成a=2,b=1情况，所以先手有必胜策略
a=5,b=3时，先手没有必胜策略

至此，大家可能没有发现什么规律，但我们翻转一下表格，都到：

至此，我们可以发现一个规律：
每一个格子如果填“√”，当且仅当：

• 此格向左上方走若干个后走到一个“×”（对应的是从两端抽走相同个数牌）
• 或向左走若干个后走到一个“×”
• 或向上走若干个后走到一个“×”（后面两种对应的是从一端收走若干牌）

否则此格为“×”

我们发现，每一行只会有一个“×”，于是用一个数组预处理出所有”ד的位置，此题便完成了
代码（有注释）：

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=3000020;

int a[maxn];

int main() {
    int mx=1;//每一条自左上向右下的链上，行和列编号差值一定，记为mx
    //即当前1~(mx-1)所代表的链都有”ד了
    for(int i=3; i<=3000000; ++i) {
        if(a[i]==0) {//没有填过相当于此行和此列没有出现过”ד，因此向左上找
            a[i]=i+mx; //i+1~i+mx-1都是”√“，i+mx匹配不到”ד，所以为”ד
            if(i+mx<=3000000) a[i+mx]=i; //表格是对称的
            ++mx;//增加一条自左上向右下的链
        }
    }
    int T; scanf("%d", &T);
    while(T--) {
        int n, x; scanf("%d%d", &n, &x);
        if(x-1==0&&n-x==0) printf("ma la se mi no.1!\n");
            else if(x-1==0||n-x==0) printf("yo xi no forever!\n");
                else if(a[x-1]==n-x) printf("ma la se mi no.1!\n");
                    else printf("yo xi no forever!\n");
    }
    return 0;
}