专栏文章

题解：AT_arc113_e [ARC113E] Rvom and Rsrev

TTmbcan
AT_arc113_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minqzobd
此快照首次捕获于
2025/12/02 06:55
3 个月前
此快照最后确认于
2025/12/02 06:55
3 个月前
查看原文
看看样例，发现要对 aa、bb 的位置和数量分讨。
用 AA 表示一段极长连续 aa，BB 表示一段极长连续 bb。答案只有三种情况：
  1. AA 或者 BB；
  2. aBaB；
  3. BABA；
  4. BaBBaB。
我们要做的操作是尽量把 bb 向前挪动，直到挪不了或者挪了不优的时候才留下 aa。
考虑最终答案对应的 SS 的情况。

AA 或 BB

如果 SS 里字母相同，什么都不做是最优的，否则会使字母数量变少。
SS 不满足前面的所有条件。如果 S=…bS=\dots b 且 aa 有偶数个，我们要让 bb 尽量向前挪动，直接把 aa 删完即可。

aBaB

SS 不满足前面的所有条件。如果 S=ABS = AB，且 aa 为奇数时，aa 删不完，让 bb 尽量向前挪动，那就剩下一个 aa 最优。

BABA

此时的答案，当 BB 确定时，我们应该让 AA 可能长。

SS 结尾是 aa

SS 不满足前面的所有条件。如果 SS 结尾是 aa，那么我们操作会是一直删 aa 使 bb 向前挪，并且末尾留下 AA 尽量长。
先除去最后一段 AA，设剩下的 ∣A∣=1|A|=1 的段有 w1w_1 个，∣A∣>1|A|>1 的段有 w2w_2 个。
我们每次操作，取最后一段 AA 和第一段 AA 的第一个位置，把第一段 AA 拼到最后一段，把最后一段 BB 转到前面。
这样会删掉 2×w22 \times w_2 个 aa，使得 SS 中除了最后一段 AA 只剩下 ∣A∣=1|A|=1 的段。
我们为了使剩下末尾的 AA 尽量长，就让 ∣A∣=1|A|=1 的两两删，不够了再从末尾的 AA 里拿一个出来，这样操作会减掉 2×⌈w12⌉2 \times \lceil \frac{w_1}{2} \rceil 个 aa。
最后 SS 中的 bb 个数不变且被挪到了最前面，aa 减少了2×(w2+⌈w12⌉)2 \times (w_2 + \lceil \frac{w_1}{2} \rceil) 个。

SS 结尾是 bb

SS 不满足前面的所有条件。如果 SS 结尾是 bb 且有奇数个 aa，假如我们直接先删 aa 使 S=BaBS=BaB，那么我们再删两个 bb 把 aa 挪到后面更优。
也就是说我们为了把后面的 bb 挪到前面去，一定会删掉两个 bb。那我们可以先删 bb，把一段 aa 挪到末尾，然后将 bb 向前挪并让末尾的 AA 尽可能长，这对于先删 aa 来说一定不劣。
我们选择操作一段 AA 的前后两个 bb，把这段 AA 转到最后，然后就和上面 SS 结尾是 aa 的情况相同了。
注意如果 SS 开头不为 bb，那么我们无法让第一段 AA 转到最后。
如果 S=…B1aB2S = \dots B_1aB_2，且 ∣B2∣≤2|B_2| \le 2，那么我们不能挪动中间的 aa。因为如果操作完之后更优，应该满足 ∣B1∣−1+∣B2∣−1>∣B1∣|B_1|-1+|B_2|-1 > |B_1|。
此时我们把前面的 aa 两两删掉，留下最后的一个 aa 即可。
对应答案 BABBAB。

代码

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');
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...