[ABC255G] Constrained Nim Solution

更好的阅读体验戳此进入

题面

一般 Nim 游戏基础上增加 $m$$m$ 条限制，限制当石子数为 $x_i$$x_i$ 时不能拿走其中的 $y_i$$y_i$ 个。

Solution

显然博弈论，考虑 SG函数。Nim 游戏标准套路，对于多个石子堆求出每个石子堆石子数 $a_i$$a_i$ 的 $SG(a_i)$$SG(a_i)$，若 $\underset{i=1}{\overset{n}{⨁}}SG(a_i)=0$$\bigoplus_{i = 1}^n SG(a_i) = 0$ 则先手必输，反之必胜。关于 SG函数 的详解：SG函数学习笔记。

本题的区别即为 $m$$m$ 条限制，考虑如何处理。显然一般 Nim 游戏的 SG 函数有转移 $SG(i)=\mathrm{mex}\{SG(j)\mid j\in [1,i-1]\}$$SG(i) = \operatorname{mex}\{SG(j) \mid j \in [1, i - 1]\}$，本题的区别不难想到就是在一般的 SG函数 基础上，在求 $\mathrm{mex}$$\operatorname{mex}$ 的时候需要从中去掉一些值，也就是去掉 $SG(x_i)$$SG(x_i)$ 转移中的 $SG(x_i-y_i)$$SG(x_i - y_i)$。严谨点叙述就是 $SG(i)=\mathrm{mex}\{SG(j)\mid j\in [1,i-1]\wedge (i,j)\ne (x_k,x_k-y_k),k\in [1,m]\}$$SG(i) = \operatorname{mex}\{SG(j) \mid j \in [1, i - 1] \land (i, j) \neq (x_k, x_k - y_k), k \in[1, m] \}$。考虑维护，显然值域过大无法硬做。发现每次从中去掉一些值后，$\mathrm{mex}$$\operatorname{mex}$ 的值就会变为最小的被全部删除的元素。然后在这个位置以后，下一条限制以前，每次的 $SG(i)=SG(i-1)+1$$SG(i) = SG(i - 1) + 1$。发现整个值的分布实际上就是一些特殊点和很多条斜率为 $1$$1$ 的线段。所以我们对于答案，考虑开个 map 记录转折点，每次查询对应的所在位置然后增加对应数量的 $1$$1$ 即可。

具体实现过程也不难理解，开个 map 里套 basic_string 维护对应 $x_i$$x_i$ 的所有 $x_i-y_i$$x_i - y_i$，然后遍历，显然升序遍历过程中 $x_i$$x_i$ 以内的 $SG$$SG$ 均已确定。然后考虑如何确定当前的 $SG(i)$$SG(i)$，不难发现对于没有限制的 $SG$$SG$ 值即为其之前的所有 $SG$$SG$ 的最大值，也就是前缀最大值 $+1$$+1$。对于有限制的，我们枚举其所有限制，找到最小的一个被删没的值（注意这里比较的时候要 $+1$$+1$，原因是遍历到此时的时候一般情况下会有一个 $SG(i)=i$$SG(i) = i$），将其设为这个。此为特殊点，然后在其之后的点依然按照一般的斜率为 $1$$1$ 地增长，用前缀最大值更新，记录一下即可。

Code

xxxxxxxxxx
77
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
ll A[210000];
27
ll oplus(0);
28
map < ll, basic_string < ll > > rest;
29
map < ll, ll > SG, repeat;
30

31
ll CalSG(ll x){
32
    auto sp = *prev(SG.upper_bound(x));
33
    return sp.second + (x - sp.first);
34
}
35

36
int main(){
37
    N = read(), M = read(); SG.insert({0, 0});
38
    for(int i = 1; i <= N; ++i)A[i] = read < ll >();
39
    for(int i = 1; i <= M; ++i){
40
        ll p = read < ll >(), v = read < ll >();
41
        rest[p] += p - v;
42
    }
43
    ll preMx(-1);
44
    for(auto &mp : rest){
45
        preMx = max(preMx, CalSG(mp.first - 1));
46
        map < ll, ll > tmp;
47
        for(auto val : mp.second)tmp[CalSG(val)]++;
48
        for(auto cur : tmp){
49
            if(cur.second >= repeat[cur.first] + 1){
50
                repeat[cur.first]++;
51
                SG[mp.first] = cur.first;
52
                break;
53
            }
54
        }preMx = max(preMx, CalSG(mp.first));
55
        SG[mp.first + 1] = preMx + 1;
56
    }
57
    for(int i = 1; i <= N; ++i)oplus ^= CalSG(A[i]);
58
    printf("%s\n", oplus ? "Takahashi" : "Aoki");
59
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
60
    return 0;
61
}
62

63
template < typename T >
64
inline T read(void){
65
    T ret(0);
66
    int flag(1);
67
    char c = getchar();
68
    while(c != '-' && !isdigit(c))c = getchar();
69
    if(c == '-')flag = -1, c = getchar();
70
    while(isdigit(c)){
71
        ret *= 10;
72
        ret += int(c - '0');
73
        c = getchar();
74
    }
75
    ret *= flag;
76
    return ret;
77
}

UPD

update-2022_12_07 初稿