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;
}
。。。看不懂
。。。QWQ
可能栈的解法更易懂,这只是我考场时的解法