[ABC255G] Constrained Nim Solution

• [ABC255G] Constrained Nim Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N, M;
ll A[210000];
ll oplus(0);
map < ll, basic_string < ll > > rest;
map < ll, ll > SG, repeat;

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

int main(){
    N = read(), M = read(); SG.insert({0, 0});
    for(int i = 1; i <= N; ++i)A[i] = read < ll >();
    for(int i = 1; i <= M; ++i){
        ll p = read < ll >(), v = read < ll >();
        rest[p] += p - v;
    }
    ll preMx(-1);
    for(auto &mp : rest){
        preMx = max(preMx, CalSG(mp.first - 1));
        map < ll, ll > tmp;
        for(auto val : mp.second)tmp[CalSG(val)]++;
        for(auto cur : tmp){
            if(cur.second >= repeat[cur.first] + 1){
                repeat[cur.first]++;
                SG[mp.first] = cur.first;
                break;
            }
        }preMx = max(preMx, CalSG(mp.first));
        SG[mp.first + 1] = preMx + 1;
    }
    for(int i = 1; i <= N; ++i)oplus ^= CalSG(A[i]);
    printf("%s\n", oplus ? "Takahashi" : "Aoki");
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_07 初稿