P4236 【扑克】题解

· · 题解

本题属于一打表就太容易发现规律的题目。

首先上结论：

当a是奇数时，n为奇数则先手胜，反之则后手胜。

当a是偶数时，求n 对 a+1取模的值，这个值如果是奇数或等于a,则先手胜，否则后手胜。

可以很容易想到要把n转化为一个a进制的数。此时，两个操作转化成这样：

①选择非0的一位，使之-1

②选择0的一位，使之变为a-1,而对于这一位前面的所有位，如果也是0那么也变为a-1，直到遇到一个非0位使之-1.

所以，当a是奇数时，可以注意到无论原数是如何，选择了什么操作，每一次行动都会让原数二进制表达上每一位的和的奇偶性变化。而这一切的终点则是“1”的那个时候->先胜点，和为奇数。因此，初始局面的每一位的和如果是奇数那么先胜，否则后手胜。

而又不难发现，a为奇数时，a进制表达上的每一位(1,a,a^2,a^3,a^4...)也全都是奇数。所以奇数个奇数相加得到一定是得到奇数->因此只要判断n是否是奇数即可。

而a是偶数的时候则稍微复杂一些。

首先，想到a+1，你是需要发现它除了n < a且n为偶数的情况n = a+1应该算是一个显然的必败点了。在它以后的情况都是比较好分析的。

当局面变化到n < a+1的时候，由于只有-1或者-a的操作，可以显然得到如果n为偶数且n \neq a那么后手胜，否则先手胜。

由于a^2 = (a-1)(a+1) + 1,所以a^2 \equiv1 (mod (a+1)). 所以考虑a^k mod (a+1)，可以发现2 | k的时候a^k mod (a+1)=1,反之=a

所以，对于任意的一个偶数k和一个奇数l，一定有a^k+a^l \equiv 0(mod(a+1))

于是，如果是后手胜局，它可以容易在先手行动以后选择拿走a^0或a^1来使得 两人取掉数的和是a+1的倍数，除非数是形如a^{2k}+l(l < a)形式（有人取了a^{2k}以后无法再取a）。不过仔细思考可以把这种形态等价成a^{2k} + l - (a^{2k}-1)（一个整除a+1的数） =l + 1.，依然可以发现他是符合上面的规律的。

代码很简单：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20010;
bool a[maxn];
int n,m,p,q,mi[20],ans[20];
char ch[510];
inline int read()
{
    int x = 0, f = 1;
    char ch = 0;
    for (;!isdigit(ch);ch = getchar()) if (ch == '-') f = -1;
    for (;isdigit(ch);ch = getchar()) x = x *10 + ch - 48;
    return x * f;
}

int main()
{
    q = read();
    while (q--)
    {
        n = read(); scanf("%s",ch);
        int len = strlen(ch);
        if (n&1)
        {
            if (ch[len - 1]&1) puts("lsq Win"); else puts("wzt Win");
        }
        else
        {
            n++;
            int now = 0;
            for (int i = 0; i < len; ++i)
            {
                now = now * 10 + ch[i] - 48;
                now %= n;
            }
            if ((now) & 1 || now == n - 1) puts("lsq Win"); else puts("wzt Win");
        }
    }
}

话说比赛的时候，这个题我首先是早上起来看了一下然后就被拉去走亲戚了，但是整个过程中都没想到啥觉得很肯定的结论，然后回到家试着一打表看看就发现....