Solution. CF1329D Dreamoon Likes Strings
Description
我们称相邻字符不同的字符串是美丽的。
给定字符串 $s_{1\dots n}$，每次操作可以删除 $s$ 的一个美丽子串，剩下的字符会按照原来的顺序拼接起来。
求将 $s$ 变成空串的最小步数。
$n\le2\times10^5$
Solution
容易发现的是，我们并不关心美丽子串的具体构成，所以可以将美丽子串压缩起来。
最直观的一种构造方式是，将原串转化为若干个相同字符的连续段，删去段间的部分，比如：
$$
\texttt{aaaa}{\color{red}\texttt{bcd}}\texttt{eee}{\color{red}\texttt{fg}}\texttt{hhh}{\color{red}\texttt{ijk}}
$$
但是这样的转化不够优美，留下的这些连续段还可能在删除过程中动态的拼接成更长的美丽子串，这不利于我们的代码实现，同时也难以进行贪心。
注意到难点在于如何处理美丽子串的拼接，我们考虑一种新的构造，让每个字符代表一个美丽子串。
构造字符串 $t$，若 $s_i=s_{i+1}$，则将 $s_i$ 加到 $t$ 的末尾，效果如下：
$$
\begin{aligned}
\texttt{s: }&\texttt{aaaabcdeeefghh}{\color{red}\texttt{hijk}}\\
\texttt{t: }&\texttt{aaa ee hh}
\end{aligned}
$$
$t$ 中的每个字符都是一个美丽子串的末尾，当然我们发现原串中最后的一个美丽子串被抛弃了，这个最后单独删去即可。
对于 $t$，我们有两种操作：
-
直接删去一个字符，也就意味着删去了其代表的美丽子串。
-
删去两个相邻且不同的字符。
注意，删去两个字符并不意味着删去两个美丽子串，假设 $t$ 中有三个字符 abc，我们希望删去 ab，实际上意味着删去了 b 对应的美丽子串，并使 a 与 c 合并。
考虑为什么可以这样做，a 和 b 不同也就意味着 a（对应美丽子串）的末尾与 b 的末尾不同，假如在对 ab 操作时后面的部分还没有操作过，由于 $t$ 中任意字符对应到原串中去都有 $s_i=s_{i+1}$，则必然有 a 的末尾与 c 的开头不同，可以合并。
另外，有些时候 a 会与原串最后被抛弃的美丽子串合并。
我们只需要保证按照从前到后的顺序进行删除即可。
显然我们会尽量使用 2 操作。
类似括号匹配，我们可以用栈来维护这一过程。
此外，我们还需要进行贪心，为与代码统一，令 $t$ 中出现次数最多的字符为 $amx$，出现次数为 $mx$，$t$ 的长度为 $sum$。
-
$mx>\lceil sum/2\rceil$
这意味着无论怎么删都一定会剩下若干个 $amx$，为使操作数最少，我们需要保证每次 2 操作都是删去 $amx$ 与某个其他字符。
-
$mx\le\lceil sum/2\rceil$
我们需要保证每次删除后，如果更新 $amx,mx,sum$，仍然有 $mx\le\lceil sum/2\rceil$，这样最后不会剩下任何字符，$sum$ 为奇数的话则会剩下一个字符，直接删去即可。
题目要求输出每一次操作删去的子串下标，由于我们是从前往后删除，我们可以记录当前已经删除了几个数，精细实现就不需要线段树了。
复杂度 $O(n\Sigma)$。
Code
namespace Main{
const int N = 200005;
const int S = 30;
int t, n, c, cnt[S], sum, mx, amx;
char s[N];
pair<int, int> a[N];
vector<pair<int, int>> ans;
void update(){
mx = -1, sum = 0;
for(int i = 0; i < S; i++){
if(cnt[i] > mx){
mx = cnt[i];
amx = i;
}
sum += cnt[i];
}
}
void Main(){
input(t);
while(t--){
memset(cnt, 0, sizeof(cnt));
ans.clear();
scanf("%s", s + 1);
n = strlen(s + 1);
c = 0;
for(int i = 1; i < n; i++){
if(s[i] == s[i + 1]){
a[++c] = {i, s[i] - 'a'};
cnt[a[c].second]++;
}
}
update();
int del = 0;
stack<pair<int, int>> stk;
if(mx * 2 > sum){
for(int i = 1; i <= c; i++){
if(stk.empty()) stk.emplace(a[i].first - del, a[i].second);
else{
if((stk.top().second == amx ^ a[i].second == amx) == 1){
ans.emplace_back(stk.top().first + 1, a[i].first - del);
del += a[i].first - del - stk.top().first;
stk.pop();
}
else stk.emplace(a[i].first - del, a[i].second);
}
}
}
else{
for(int i = 1; i <= c; i++){
if(stk.empty() || stk.top().second == a[i].second){
stk.emplace(a[i].first - del, a[i].second);
}
else{
cnt[stk.top().second]--, cnt[a[i].second]--;
update();
if(mx * 2 <= sum + 1){
ans.emplace_back(stk.top().first + 1, a[i].first - del);
del += a[i].first - del - stk.top().first;
stk.pop();
}
else{
cnt[stk.top().second]++, cnt[a[i].second]++;
update();
stk.emplace(a[i].first - del, a[i].second);
}
}
}
}
while(!stk.empty()){
pair<int, int> tmp = stk.top(); stk.pop();
if(stk.empty()) ans.emplace_back(1, tmp.first), del += tmp.first;
else{
ans.emplace_back(stk.top().first + 1, tmp.first);
del += tmp.first - stk.top().first;
}
}
if(del != n) ans.emplace_back(1, n - del);
write(ans.size()); puts("");
for(pair<int, int> op: ans) write(op.first), putchar(' '), write(op.second), puts("");
}
return;
}
} // namespace本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
