看看样例，发现要对 、 的位置和数量分讨。
用 表示一段极长连续 ， 表示一段极长连续 。答案只有三种情况：
-
或者 ；
-
；
-
；
-
。
我们要做的操作是尽量把 向前挪动，直到挪不了或者挪了不优的时候才留下 。
考虑最终答案对应的 的情况。
或
如果 里字母相同，什么都不做是最优的，否则会使字母数量变少。
不满足前面的所有条件。如果 且 有偶数个，我们要让 尽量向前挪动，直接把 删完即可。
不满足前面的所有条件。如果 ，且 为奇数时， 删不完，让 尽量向前挪动，那就剩下一个 最优。
此时的答案，当 确定时，我们应该让 可能长。
结尾是
不满足前面的所有条件。如果 结尾是 ，那么我们操作会是一直删 使 向前挪，并且末尾留下 尽量长。
先除去最后一段 ，设剩下的 的段有 个， 的段有 个。
我们每次操作，取最后一段 和第一段 的第一个位置，把第一段 拼到最后一段，把最后一段 转到前面。
这样会删掉 个 ，使得 中除了最后一段 只剩下 的段。
我们为了使剩下末尾的 尽量长，就让 的两两删，不够了再从末尾的 里拿一个出来，这样操作会减掉 个 。
最后 中的 个数不变且被挪到了最前面， 减少了 个。
结尾是
不满足前面的所有条件。如果 结尾是 且有奇数个 ，假如我们直接先删 使 ，那么我们再删两个 把 挪到后面更优。
也就是说我们为了把后面的 挪到前面去，一定会删掉两个 。那我们可以先删 ，把一段 挪到末尾，然后将 向前挪并让末尾的 尽可能长，这对于先删 来说一定不劣。
我们选择操作一段 的前后两个 ，把这段 转到最后，然后就和上面 结尾是 的情况相同了。
注意如果 开头不为 ，那么我们无法让第一段 转到最后。
如果 ，且 ，那么我们不能挪动中间的 。因为如果操作完之后更优，应该满足 。
此时我们把前面的 两两删掉，留下最后的一个 即可。
对应答案 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| inline int w(int w1,int w2){
return 2*w2+w1+(w1&1);
}
inline void solve(){
int len = strlen(s+1);
for(int i=1;i<=len;++i){
cnta[i] = cnta[i-1]+(s[i]=='a');
cntb[i] = cntb[i-1]+(s[i]=='b');
}
if(!cnta[len] || !cntb[len]){
for(int i=1;i<=len;++i) putchar(s[i]);
return ;
}
if(s[len]=='b' && !(cnta[len]&1)){
for(int i=1;i<=cntb[len];++i) putchar('b');
return ;
}
if(cnta[len-cntb[len]]==cnta[len] && (cnta[len]&1)){
putchar('a');
for(int i=1;i<=cntb[len];++i) putchar('b');
return ;
}
if(s[len]=='b'){
int lasa = len;
for(int i=len;i;--i){
if(s[i]^'b'){
lasa = i;
break;
}
}
if(len-lasa<=2){
for(int i=1;i<=cntb[lasa];++i) putchar('b');
putchar('a');
for(int i=cntb[lasa]+1;i<=cntb[len];++i) putchar('b');
return ;
}
}
int las = 0,w1 = 0,w2 = 0;
for(int i=1;i<=len;++i){
if(s[i]=='b'){
if(i-1-(las+1)+1==1) ++w1;
else if(i-1-(las+1)+1>1) ++w2;
las = i;
}
}
if(s[len]=='a'){
for(int i=1;i<=cntb[len];++i) putchar('b');
for(int i=1;i<=cnta[len]-w(w1,w2);++i) putchar('a');
return ;
}
int tw = 0;
if(s[1]=='b')tw = Min(w(w1-1,w2),w(w1,w2-1));
else{
int f = -1;
for(int i=1;i<=len;++i){
if(s[i]=='b'){
f = (i>3);
break;
}
}
if(f){
if(w2==1) tw = w(w1-1,w2);
else tw = Min(w(w1-1,w2),w(w1,w2-1));
}
else{
if(w1==1) tw = w(w1,w2-1);
else tw = Min(w(w1-1,w2),w(w1,w2-1));
}
}
for(int i=1;i<=cntb[len]-2;++i) putchar('b');
for(int i=1;i<=cnta[len]-tw;++i) putchar('a');
}
|