51NOD 1661 黑板上的游戏（博弈找规律）——算法马拉松17（告别奥运）

116 阅读 0 评论 77 点赞

我是靠谱客的博主懵懂香氛，这篇文章主要介绍51NOD 1661 黑板上的游戏（博弈找规律）——算法马拉松17（告别奥运），现在分享给大家，希望可以做个参考。

传送门

1661 黑板上的游戏

Alice和Bob在黑板上玩一个游戏，黑板上写了n个正整数a1, a2, …, an，游戏的规则是

这样的：

1 . Alice占有先手主动权。

2 . 每个人可以选取一个大于1的数字擦去，并写上一个更小的数字，数字必须是整

数，然后由对方进行下一次操作。

3 . 如果擦去的数字是 x (x > 1) ，则写上的数字不能比 x/k 小，但是要比 x 小。这里的

除法为有理数除法。

4 . 不可以擦去任何一个数字 1 ，如果当前无法找到一个数字进行操作，则当前方输。

假设Alice和Bob都会选择最优的策略，请问Alice是否存在必胜的方案？

Input

第一行两个空格隔开的正整数n和k，其中n表示数字的个数，k表示游戏的参数。

第二行n个空格隔开的正整数，其中第i个表示ai。

1 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^18, 1 ≤ ai ≤ 10^18。

Output

如果存在必胜方案，则输出“Alice i y”，其中i和y表示先手的一种能必胜的操作：将第i

个数修改为y。

如果没有，则输出“Bob”表示后手必胜。（输出不含引号）

Input示例

4 2

2 3 3 3

Output示例

Alice 2 2

解题思路：

官方题解(很详细):

固定 $k$ 后对 $sg(n)$ 进行打表，可以发现每个数字第一次出现的位置很有规律，即每隔

几个数字就出现一个已有的数字。删去每个数字的第一次出现位置之后，将剩下的数字

再排成一列，和原来的表是同构的，可以猜测 $sg(n)$ 的递归解是

$sg(1)=0, sg(a*k+1)=sg(a), sg(a*k+b)=a(k-1)+b-1(1<b<=k,注意b的定义)。$

本题为 $n$ 个游戏的和，所以对应的 $sg$ 值为 $sg(a_1) xor sg(a_2) xor ... xor sg(a_n)。$

如果 $sg$ 值为 $0$ ，则后手必胜。

如果 $sg$ 值不为 $0$ ，则先手必胜，必胜的操作是将下一轮游戏的 $sg$ 值变为 $0$ ，设当前

的 $sg$ 值为 $m$ ，则需要找到一组 $i$ 和 $y$ 使得 $m=sg(a_i) xor sg(y)$ ，

$那么 sg(y)=m xor sg(a_i，不妨设p=m xor sg(a_i)$ ， $q=(p-1)/(k-1)*k+(p-1)%(k-1)+2$ $（p=0时特判成q=1）$ ，

可能的 $y$ 只有 $q, qk+1, (qk+1)k+1, ...，$ 其中小于 $a_i$ 的只有 $O(log_k(a_i))$ 个，

在其中找一个不小于 $a_i/k$ 的即可，枚举 $i$ ，总能找到一个 $i$ 对应的可行的 $y$

注意向上取整和判断整数溢出。

这里补一个简要证明，基于 $sg$ 函数的定义，一个局面的 $sg$ 值等于其后继局面的 $sg$ 值

里没出现的最小非负整数，比如本题就是:
$sg(n) = mex(sg(n-1), sg(n-2), ..., sg((n-1)/k+1))$ ，

其中 $mex(S)$ 表示集合 $S$ 中没有出现的最小非负整数，除法是下取整的整数除法。

考虑 $n$ 和 $n-1$ ，它们所对应后继集合最多有两个元素不同，尝试利用数学归纳法来分

析，分析 $sg(n)$ 时，假设已经得到 $sg(1), sg(2), ..., sg(n-1)$ 满足上述结论。

由于后继局面可以写成一个区间的形式，所以下面的分析用 $[L, R]$ 来简化表示

$(sg(L), sg(L+1), ..., sg(R))$

当 $n=ak+1$ 时， $ak+1$ 对应的后继是 $[a + 1, ak]$ ， $ak$ 对应的后继是 $[a, ak-1]$

假设 $sg(ak+1)≠sg(a)$ ，则 $sg(ak+1)<sg(a)$ ，这是因为 $a$ 不是 $ak+1$ 的后

继，如果 $sg(a)$ 不是最小没出现的，那么最小没出现的只能是更小的数。

由于 $sg(ak+1)$ 是一个比 $sg(a)$ 小的数，说明 $[a + 1, ak]$ 里没有这个数，那么

$[a, ak-1]$ 里更不会有这个数，因此 $sg(ak)<=sg(ak+1)$ ，从而 $sg(ak) < sg(a)$

但是 $sg(ak)$ 根据归纳假设是 $[1, ak]$ 里最大的值，因此有 $sg(a) <= sg(ak)$ ，与上

述产生矛盾，所以 $sg(ak+1) = sg(a)$

当 $n=ak+b(1<b<=k)$ 时， $n$ 对应的后继是 $[a + 1, n - 1]$ ， $n-1$ 对应的

后继是 $[a + 1, n - 2]$ 。

由上述可以知道 $sg(n-1)<sg(n)$ ，这是因为 $sg(n-1)$ 没有在 $n-1$ 的后继里

出现，所以 $sg(n)$ 只会变大不会变小。

如果 $b=2$ ，那么 $sg(n-1)=sg(a)$ ，则 $n$ 的后继相当于 $[a, ak]$ ，根据归纳假设

这里面的值都是在 $0$ 到 $sg(ak)$ 之间的，因此 $sg(n)=sg(n-2)+1$ 。

如果 $b>2$ ，那么同理可得 $sg(n)=sg(n-1)+1$ 。

然后找一下具体的式子即可，有了具体的式子就方便找逆映射了。

需要注意很多的细节问题。。。
$My Code：$

复制代码

/**
2016 - 08 - 29 下午
Author: ITAK

Motto:

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1e18+5;
const int MAXN = 1e6+5;
const LL MOD = 1e9+7;
const double eps = 1e-7;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///输入外挂
{
    LL res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
int Scan_Int()///输入外挂
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(LL a)///输出外挂
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
LL a[MAXN], sg[MAXN];
int main()
{
    int n;
    LL k;
    while(~scanf("%d%lld",&n,&k))
    {
        LL ans = 0, tmp, ret, x;
        int j = -1;
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++)
        {
            x = Scan_LL();
            a[i] = x;
            if(x == 1)
                continue;
            tmp = x;
            LL tp1 = x/k;
            LL tp2 = x%k;
            while(tmp)
            {
                if(tp2 == 0)
                {
                    tp1--;
                    tp2 = k;
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ///cout<<"a["<<i<<"] ="<<a[i]<<endl;
                    ans ^= sg[i];
                    break;
                }
                else if(tp2 > 1)
                {
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ans ^= sg[i];
                    break;
                }
                else
                {
                    tmp = (tmp-1)/k;
                    tp1 = tmp/k;
                    tp2 = tmp%k;
                }
            }
        }
        if(ans)
        {
            tmp = ans;
            for(int i=1; i<=n; i++)
            {
                if(a[i] == 1)
                    continue;
                LL p = (tmp ^ sg[i]);
                LL q = (p-1)/(k-1)*k+(p-1)%(k-1)+2;
                if(p == 0)
                    q = 1;
                ret = q;
                while(1)
                {
                    if(ret>=a[i] || ret<0)
                        break;
                    LL tp = a[i]/k;
                    if(a[i] % k)
                        tp++;
                    if(ret >= tp)
                    {
                        j = i;
                        goto endW;
                    }
                    ret = ret*k+1;
                }
            }
            endW:;
            printf("Alice %d %lldn",j, ret);
        }
        else
            puts("Bob");
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**
2016 - 08 - 29 下午
Author: ITAK

Motto:

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1e18+5;
const int MAXN = 1e6+5;
const LL MOD = 1e9+7;
const double eps = 1e-7;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///输入外挂
{
    LL res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
int Scan_Int()///输入外挂
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(LL a)///输出外挂
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
LL a[MAXN], sg[MAXN];
int main()
{
    int n;
    LL k;
    while(~scanf("%d%lld",&n,&k))
    {
        LL ans = 0, tmp, ret, x;
        int j = -1;
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++)
        {
            x = Scan_LL();
            a[i] = x;
            if(x == 1)
                continue;
            tmp = x;
            LL tp1 = x/k;
            LL tp2 = x%k;
            while(tmp)
            {
                if(tp2 == 0)
                {
                    tp1--;
                    tp2 = k;
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ///cout<<"a["<<i<<"] ="<<a[i]<<endl;
                    ans ^= sg[i];
                    break;
                }
                else if(tp2 > 1)
                {
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ans ^= sg[i];
                    break;
                }
                else
                {
                    tmp = (tmp-1)/k;
                    tp1 = tmp/k;
                    tp2 = tmp%k;
                }
            }
        }
        if(ans)
        {
            tmp = ans;
            for(int i=1; i<=n; i++)
            {
                if(a[i] == 1)
                    continue;
                LL p = (tmp ^ sg[i]);
                LL q = (p-1)/(k-1)*k+(p-1)%(k-1)+2;
                if(p == 0)
                    q = 1;
                ret = q;
                while(1)
                {
                    if(ret>=a[i] || ret<0)
                        break;
                    LL tp = a[i]/k;
                    if(a[i] % k)
                        tp++;
                    if(ret >= tp)
                    {
                        j = i;
                        goto endW;
                    }
                    ret = ret*k+1;
                }
            }
            endW:;
            printf("Alice %d %lldn",j, ret);
        }
        else
            puts("Bob");
    }
    return 0;
}