4504.字符串消除

声明

这道题的题解都写得很好，强烈谴责故意踩题解的人！

你的点赞是我写作的动力，求赞qwq

题目内容

李华和张红正在玩字符串消除游戏。

游戏规则如下：

给定一个由小写字母构成的字符串 $s$。

两人轮流进行消除操作，当轮到一人时，其任务是在当前 $s$ 中找到两个连续且相同的字母，并将它们从 $s$中消除。例如，当 $s$ 为 abba 时，可以消除 bb，使 $s$ 变为 aa。

第一个无法进行消除操作的选手视为失败。

已知，游戏由李华执先手，且两人都采取最优策略。

请问，李华是否可以获胜？

输入格式

一行，一个字符串 $s$。

输出格式

如果李华可以获胜，则输出 Yes，否则输出 No。

数据范围

前 $5$ 个测试点满足 $1 \le |s| \le 10$
所有测试点满足 $1 \le |s| \le 10^5$

思路

很容易根据数据范围看出，贪心是一个很好的思路：

只要我们证明操作顺序与答案无关，就看可以直接模拟来做

$2022/08/08$ $update证明$:

根据 yxc 大佬的思路，我们用数学归纳法来证明：

如果字符串长度为 1：显然先手败，成立

设字符串长度为 $n$

考虑证明：如果对于所有 $<$ $n$ 的序列，操作顺序与答案无关，那长度为 $n$ 的序列 $a$ 操作顺序与答案无关

对于任意两种选择，不妨设第 1 种选择是先消除字符 $x$，第2种选择是先消除字符 $y$

那么序列必然是 $ \cdots xx\cdots x \cdots yy\cdots y \cdots$ 的形式（一共 $a$ 个 $x$，$b$ 个 $y$，$2 \le a,b \le n - 1$）

而如果有多个 $x(y)$，删任意两个

我们将这两种删的操作划到两个集合里：

第一种操作在删去 $x$ 后，剩下 $a - 2$ 个 $x$

然后分类讨论删除 $y$ 的情况即可（肝不动了

详细证明可以去 y总 周赛视频 16 分处看分类讨论

显然，如果直接用数组维护这个序列，每一次删除节点又需要 $O(n)$ 的时间来维护左右下标

所以，我们维护一个链表来存储：

$l$ 数组维护节点的左面一个点下标

$r$ 数组维护节点的右面一个点下标

顺便维护：$v$ 数组维护节点是否被删除

于是每一次删除两个相邻节点就等同于：

//l_son 是左儿子，r_son 是右儿子

r[l[l_son]] = r[r_son];
l[r[r_son]] = l[l_son];

这道题就可以在 $O(n)$ 的时间复杂度解决了

c++ 代码

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

typedef long long ll;

const int N = 200009;
string s;
char c[N];
bool v[N], ans = false;
int l[N], r[N];

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    for(int i = 1;i <= s.size();++ i)
    {
        c[i] = s[i - 1]; v[i] = false;
        l[i] = i - 1; r[i] = i + 1;//左右节点下标
    }
    for(int i = 1, ll, rr;i <= s.size();++ i)
    {
        if(v[i]) continue;
        if(c[i] == c[r[i]])
        //如果相邻两个节点颜色相同
        {
            ll = i, rr = r[i];
            //ll 和 rr 是维护相邻两个节点
            while(c[ll] == c[rr])
            {
                if(ll == 0 || rr == s.size() + 1) break;//如果超过线段长度，退！
                v[ll] = true; v[rr] = true;//假删标记，删除两个节点
                r[l[ll]] = r[rr]; l[r[rr]] = l[ll];更新链表
                ans ^= 1;//答案只跟奇偶性有关，所以用 bool 的奇偶性来确定答案
                ll = l[ll], rr = r[rr];//   
            }
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}