题解：AT_arc113_e [ARC113E] Rvom and Rsrev
Tmbcan
·
·
题解
看看样例，发现要对 a、b 的位置和数量分讨。
用 A 表示一段极长连续 a，B 表示一段极长连续 b。答案只有三种情况：
-
-
-
-
我们要做的操作是尽量把 b 向前挪动，直到挪不了或者挪了不优的时候才留下 a。
考虑最终答案对应的 S 的情况。
A 或 B
如果 S 里字母相同，什么都不做是最优的，否则会使字母数量变少。
---
### $aB
---
### $BA
此时的答案，当 B 确定时，我们应该让 A 可能长。
S 结尾是 a
先除去最后一段 $A$，设剩下的 $|A|=1$ 的段有 $w_1$ 个，$|A|>1$ 的段有 $w_2$ 个。
我们每次操作，取最后一段 $A$ 和第一段 $A$ 的第一个位置，把第一段 $A$ 拼到最后一段，把最后一段 $B$ 转到前面。
这样会删掉 $2 \times w_2$ 个 $a$，使得 $S$ 中除了最后一段 $A$ 只剩下 $|A|=1$ 的段。
我们为了使剩下末尾的 $A$ 尽量长，就让 $|A|=1$ 的两两删，不够了再从末尾的 $A$ 里拿一个出来，这样操作会减掉 $2 \times \lceil \frac{w_1}{2} \rceil$ 个 $a$。
最后 $S$ 中的 $b$ 个数不变且被挪到了最前面，$a$ 减少了$2 \times (w_2 + \lceil \frac{w_1}{2} \rceil)$ 个。
#### $S$ 结尾是 $b
也就是说我们为了把后面的 $b$ 挪到前面去，一定会删掉两个 $b$。那我们可以先删 $b$，把一段 $a$ 挪到末尾，然后将 $b$ 向前挪并让末尾的 $A$ 尽可能长，这对于先删 $a$ 来说一定不劣。
我们选择操作一段 $A$ 的前后两个 $b$，把这段 $A$ 转到最后，然后就和上面 $S$ 结尾是 $a$ 的情况相同了。
注意如果 $S$ 开头不为 $b$，那么我们无法让第一段 $A$ 转到最后。
如果 $S = \dots B_1aB_2$，且 $|B_2| \le 2$，那么我们不能挪动中间的 $a$。因为如果操作完之后更优，应该满足 $|B_1|-1+|B_2|-1 > |B_1|$。
此时我们把前面的 $a$ 两两删掉，留下最后的一个 $a$ 即可。
对应答案 $BAB$。
## 代码
```cpp
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');
}
```