题解：P15088 [UOI 2025 II Stage] Digital Game

· · 题解

曼波~

这是一道非常容易陷入思维误区题目，如果你看到 1 \times 10 ^ 6 的范围就死想 O(n) 做法就会万劫不复。

先说结论：当 n \geq 20 时，Us 必胜（即一定输出 No）。

更一般的说，有定理：

定理

设 cnt(l, r) 表示在区间 [l, r] 内数字种类的个数，len 表示区间 [l, r] 的长度 r - l + 1，当（注意并不是仅当）：

cnt(l, r) \times 2\leq len

时 Us 必胜。

（此 Us 非彼 Us，仅代表题目中人名 感觉很奇怪说一下）

证明

使用数学归纳法。

1.归纳基础

当游戏进入一个短区间时，即 len = 2。若此时满足cnt(l, r) \times 2\leq len，得 cnt(l, r) = 1，即区间内所有数都相等，那么显然定理成立。

2.归纳假设

假设对于所有长度小于 len 的区间，定理成立。

3.归纳推导

我们现在只关注区间 (l, r)。

引入变量：d = len - cnt(l, r) \times 2

显然 Vus 希望 $d$ 变小，Us 策略则相反。 设当前区间满足条件，即 $cnt(l, r) \times 2\leq len$ ，那么 $d \geq 0$。 Vus 先手，他删掉一个数，最优状态下也只能使 $len$ 减 $1$ ，而 $cnt(l, r)$ 保持不变，这样 $d$ 就减少了 $1$。此时 $d \geq -1$ 。 此时轮到 Us，我们分成三种情况： **情况 1**：$d \geq 1$： 无论 Us 如何操作，$d$ 仍然保持 $\geq 0$（因为 Us 操作最多使 $d$ 减少 $1$）。此时区间仍然满足条件，且长度缩短为小于 $len$，由归纳假设，定理成立。 **情况 2**：$d = -1$： 出现 $d = -1$ 意味着区间内必然存在一个只出现一次的数字（否则每个数字至少出现两次，则 $d \geq 0$）。Us 就删除这个数字，删除后： - 长度减少 $1

此时 d' = 0，且长度减小，由归纳假设，定理成立。

情况 3：d = 0： 此时 2 \times cnt(l,r) = len，即数字总数正好是种类数的两倍。有两种子情况：

子情况 3a：存在只出现一次的数字 Us 删除它，则：

但此时区间缩短，且由归纳假设，定理成立。

子情况 3b：所有数字都恰好出现两次 考虑子区间 [l+1, r]（去掉左端点）。该子区间的：

根据情况 2 的分析，在子区间内必然存在一个只出现一次的数字，Us 就删除它。删除后：

终于，我们成功证明了定理：当：

cnt(l, r) \times 2\leq len

时 Us 必胜。

注意到字符串中的数字只有 0 ~ 9，所以 cnt(l,r) 最大为 10。

所以最终我们可以得到：当 n \geq 20 时，Us 必胜。

那么对于 n < 20 呢？

显然我们就可以愉快的使用记忆化搜索，用一个\text{n} 位二进制掩码表示一个状态，初始全为 1 ，第 \text{i} 位为 0 则说明当前位已经删除，暴力枚举所有情况来模拟胜负。 （具体实现见代码）

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int T, n; 
bool r[N];
string s;
int pre(int w, int x){ 
    for(int i = w - 1; i >= 0; i--){
        if(!(x & (1 << i))) continue;
        return s[i] - '0';
    }
    return -1;
}
int nex(int w, int x){
    for(int i = w + 1; i < n; i++){
        if(!(x & (1 << i))) continue;
        return s[i] - '0';
    }
    return -1;
}
int check(int x){ //判断当前状态有没有分出胜负
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!(x & (1 << i))){
            cnt++;
            continue;
        } 
        if(((s[i] - '0') == pre(i, x)) || ((s[i] - '0') == nex(i, x))) return 0; //有相邻的
    }
    if(cnt == n) return 1; //串已空
    return 2;   
}
bool dfs(int py, int x){ //py为0表示Vus，1表示Us
    if(r[x]) return r[x]; //记忆化
    int f = check(x); 
    if(f == 1) return r[x] = (1 ^ py);
    else if(f == 0) return r[x] = (0 ^ py); 
    for(int i = 0; i < n; i++){
        if(!(x & (1 << i))) continue;
        bool flag = dfs((py ^ 1), x ^ (1 << i));
        if(!flag) return r[x] = 1; //有一种情况对方必输，当前状态己方就必赢
    }
    return r[x] = 0; //没有则对方必赢
}
int main(){
    cin >> T;
    while(T--){
        memset(r, 0, sizeof(r));
        cin >> n;
        cin >> s;
        if(n >= 20){
            cout << "No" << '\n';   
            continue;
        } 
        int x = ((1 << n) - 1);
        if(!dfs(0, x)) cout << "No" << '\n';
        else cout << "Yes" << '\n';
    }
    return 0;
}