专栏文章

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

ssintle
P14059题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mint2g3w
此快照首次捕获于
2025/12/02 07:53
3 个月前
此快照最后确认于
2025/12/02 07:53
3 个月前
查看原文

题目链接

题意简述

有一个由 0/10/1 组成的环，每次知更鸟可以删除一个由 11 组成的连续段，星期日可以删除一个由 00 组成的连续段。
最后唯一剩下的颜色对应的一方落败，求双方都选择最优策略的情况下最终哪一方获胜。

解题思路

官 sol 已经给出了结论做法，在此处考虑模拟博弈过程。
发现可以把连续段缩成一个同色点，因为给出的是一个环，所以最终得到的环一定是形如 10⋯1010\cdots10 的。
每一次操作，如果使一个连续段消失了，就会删除一个 1010 段，此处显然两人都想要使 1010 段数量保持在偶数。
我们发现，如果想要不使一个连续段消失，只选一个点一定最优，因此我们可以记录可使所有连续段都不消失的最大可删点数，即 ∑i=1kleni−1\sum_{i=1}^k len_i-1（其中 kk 是连续段个数，lenilen_i 是第 ii 个连续段的长度）。
同时，每次删除连续段的操作都会使对手的可删点数 +1+1，于是我们模拟这个博弈过程，进行决策即可。

参考代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...