题解：P14059 【MX-X21-T4】[IAMOI R5] 使一颗心免于哀伤

· · 题解

题目链接

题意简述

有一个由 0/1 组成的环，每次知更鸟可以删除一个由 1 组成的连续段，星期日可以删除一个由 0 组成的连续段。

最后唯一剩下的颜色对应的一方落败，求双方都选择最优策略的情况下最终哪一方获胜。

解题思路

官 sol 已经给出了结论做法，在此处考虑模拟博弈过程。

发现可以把连续段缩成一个同色点，因为给出的是一个环，所以最终得到的环一定是形如 10\cdots10 的。

每一次操作，如果使一个连续段消失了，就会删除一个 10 段，此处显然两人都想要使 10 段数量保持在偶数。

我们发现，如果想要不使一个连续段消失，只选一个点一定最优，因此我们可以记录可使所有连续段都不消失的最大可删点数，即 \sum_{i=1}^k len_i-1（其中 k 是连续段个数，len_i 是第 i 个连续段的长度）。

同时，每次删除连续段的操作都会使对手的可删点数 +1，于是我们模拟这个博弈过程，进行决策即可。

参考代码

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

const int N = 100005;
int T , n;
char s[N];

signed main()
{
    cin >> T;
    while(T--)
    {
        cin >> n >> s + 1; int cnt = 0 , R = 0 , S = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            if(s[i] != s[i - 1] || i == 1) cnt++;
            else (s[i] == '1' ? R++ : S++);
        }
        if(s[n] == s[1]) (s[1] == '1' ? R++ : S++);
        int now = cnt >> 1;
        if(cnt == 1) {cout << (s[1] == '1' ? "Sunday" : "Robin") << '\n'; continue;}
        while(now)
        {
            if(now == 1) {cout << "Robin" << '\n'; break;}
            if(now & 1) now-- , S++;
            else if(R) R--;
            else now-- , S++;
            if(now == 1) {cout << "Sunday" << '\n'; break;}
            if(now & 1) now-- , R++;
            else if(S) S--;
            else now-- , R++;
        }
    }
    return 0;
}