【题解】[COCI 2025/2026 #1] 松鼠 / Zagi

P14470 [COCI 2025/2026 #1] 松鼠 / Zagi - 洛谷

谁点的博弈论？补充了下之前写博弈论缺的对 SG 和 mex 的解释。

---

0.分析

完全没接触过博弈论的去看这个博客，看完 2.6 就回来：

【博弈论和 SG 函数 | 那忘算 10】巴什博奕 & 尼姆博弈及其变种 & 威佐夫博弈（附例题）-CSDN博客

1.流程

当你删掉某个数  后：

被夹在两个  中间的区间，就完全由“两个相邻的  的位置”决定，这样的区间总数是 。

• 所以只有靠近原始询问区间左右边界的那些段，才可能和询问边界有关。

• 每个询问、每种数，最多贡献左右两段，所以是 。

所以用记忆化搜索，把算过的区间存下来，状态数是可接受的。

我们可以先求出两个数组，来确定夹查询段两个相同值的位置。

ne[x][i]：位置 i 及之后第一个值为 x 的位置
last[x][i]：位置 i 及之前最后一个值为 x 的位置

接着求所有相邻相同值之间段的 SG 值。

对于求区间  的 SG 值的递归函数，枚举每个数值 ，

用 ne 和 last 判断  有无在区间出现过一对（即两个及以上）。 

如果出现过，用区间内最靠近端点的两个  将区间分成三段，分别递归。 

递归出来的值就是上述的 “删掉某个值后，所有小段异或的 SG 值”，我们用数组记存。

然后就可以枚举所有值看哪个没出现求 mex 了，

如果值  是没出现过的最小整数，

而且这段查询区间  刚刚好被两个值  夹在中间，

这个区间就是相邻两个值之间的区间，求出的 SG 值需要记存。

2.算法

好了，现在最大的问题来了，以上说的 SG 值要用什么数据结构存储查询？

对于每个数值都要记录特定的  的异或值，可以转为前缀异或和维护。

数据范围 ，考虑使用分块，我们定义 w1,w2 分别为块间前缀和、块内前缀和。

我们只有是刚刚好被两个值  夹着的区间  才记存异或值，可以将  作为记存位置：

先更新块内部分：从  到当前块末尾，每个位置的 w2 都异或。

更新块间部分：从  所在块到末尾块，每个块的 w1 异或。

这样每次查询只有右端点大于等于  的时候，才会用到  的异或值。

查询的时候计算  的前缀异或和，以及 的前缀异或和，两个一异或就是答案。

别忘了记忆化搜索。

3.代码

数据 1e5，考虑使用 pbds 里面的哈希数组，不然被卡常：
 

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

const int N = 1e5 + 10;
const int B = 320;    

int n;
int a[N];                

// 记忆化：f[l][r] 存储区间 [l, r] 的 SG 值（空区间为0）
gp_hash_table<int, int> f[N];

struct block {
    int w1[N], w2[N];

    int get(int x) {
        return (x - 1) / B + 1;
    }

    void modify(int x, int d) {
        if (d == 0) return;      
        int bid = get(x);
        int r = min(bid * B, n); 
        for (int i = x; i <= r; ++i) {
            w2[i] ^= d;
        }
        for (int i = bid; i <= get(n); ++i) {
            w1[i] ^= d;
        }
    }

    int prefix(int pos) {
        if (pos == 0) return 0;
        int b = get(pos);
        return w1[b - 1] ^ w2[pos];
    }

    int query(int l, int r) {
        if (l > r) return 0;
        return prefix(r) ^ prefix(l - 1);
    }
} t[34];  // 为每个数字 x（1~32）维护一个数据结构，存储相邻两个 x 之间的区间的 SG 值

vector<int> g[34];         
int ne[34][N], last[34][N]; 
// ne[x][i]：位置 i 及之后第一个值为 x 的位
// last[x][i]：位置i及之前最后一个值为 x 的位置

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second - a.first < b.second - b.first;
}

int dfs(int l, int r) {  // 计算区间 [l, r] 的 SG 值
    if (l > r) {
        return 0;    
    }      
    if (f[l].find(r) != f[l].end()) {
        return f[l][r]; // 记忆化
    }
    
    bool st[34] = {0};   // st[k] 标记数字k是否在 [l,r] 中出现
    bool vis[34] = {0};  // vis[x] 标记后继 SG 值x是否可达
    
    for (int k = 1; k <= 32; k ++ ) {
        int posl = ne[k][l];      // [l,r] 中第一个k的位置
        int posr = last[k][r];    // [l,r] 中最后一个k的位置
        if (posl > r) continue;   // 该数字不在区间中
        
        st[k] = true;

        int suma = dfs(l, posl - 1);
        int sumb = dfs(posr + 1, r);
        int sumc = t[k].query(posl + 1, posr - 1);
        int sum = suma ^ sumb ^ sumc;
        vis[sum] = true;   // 标记后继SG值
    }
    
    // 求 mex（未出现的最小非负整数）
    for (int i = 0; ; i ++ ) if (!vis[i]) {
        if (l != 1 && r != n && a[l - 1] == a[r + 1] && !st[a[l - 1]]) {
            t[a[l - 1]].modify(r, i);   // 以区间的右端点 r 作为存储位置，存入 SG 值
        }
        return f[l][r] = i;  
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        g[a[i]].push_back(i);   // 记录每个值出现的位置
    }
    
    memset(ne, 0, sizeof(ne));
    memset(last, 0, sizeof(last));
    for (int i = 1; i <= 32; i ++) {
        ne[i][n + 1] = n + 1; 
        for (int j : g[i]) {
            ne[i][j] = last[i][j] = j; 
        }
        for (int j = 1; j <= n; j ++) {
            if (!last[i][j]) last[i][j] = last[i][j - 1];
        }
        for (int j = n; j; j --) {
            if (!ne[i][j]) ne[i][j] = ne[i][j + 1];
        }
    }
    
    vector<pair<int, int> > query;
    for (int i = 1; i <= 32; i ++ )
        for (int j = 1; j < g[i].size(); j ++ )
            query.push_back({g[i][j - 1] + 1, g[i][j] - 1}); 
    
    sort(query.begin(), query.end(), cmp);
    for (auto t : query) {
        dfs(t.first, t.second);   // 先计算出这些区间的 SG 值并存入分块
    }
    
    while (Q -- ) {
        int l, r;
        cin >> l >> r;
        cout << (dfs(l, r) ? "Toni" : "Jakov") << "\n";   // SG != 0 先手胜
    }
    
    return 0;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/tenkuo/article/details/163771877