ARC113E Rvom and Rsrev

ARC113E Rvom and Rsrev

显然，最优是 b 尽量靠前且尽量多，而在满足 b 尽量多的时候，让 a 也尽量多。

考虑分类讨论。

以 $a$ 结尾

显然，不管怎样都不会删除 b，考虑怎样让 a 尽量多。

显然，最后的 b 全在开头且连在一起，所以删 a 的本质就是使 b 连起来。

那么我们一次删除 a 至少连接一次 b，至多连接两次 b：

• 选取一个 bAb 和 b(a+)b 中的 a 进行删除能连接一次 b。（其中 A 表示两个及以上个 a 连起来，a+ 表示任意个 a 连起来）
• 选取两个 bab 中的 a 进行删除能连接两次 b。

所以先操作情况二，最后处理剩余 a ，这样能做到总的操作次数最少（不包括最后的 a 串）。

具体地，记录长度为 $1$ 的 a 串和长度大于 $1$ 的 $a$ 串的个数，分别记为 $a1$ 和 $a2$，不包括最后的 a 串。

最少 a 删除操作次数即为 $\lfloor \frac{a1}{2}\rfloor +(a_1\mathrm{mod}2)+a2$。

以 $b$ 结尾

$a$ 有偶数个

显然，最后全删 a 的字典序最大。

$a$ 有奇数个

以 $ab$ 结尾

奇数个 a​，显然 a 删不完，那么这个 ab 结尾的 b 肯定无法移动到前面。

显然，把 ab 前面的 a 全删完更优，前缀 b 的个数减一个连续。

以 $abb$ 结尾

同上，把 abb 前面的 a 全删完更优，前缀 b 的个数减二个连续。

以 $bbb$ 结尾

(a+)(b+)

结果只有 $a(b+)$。

(a+)(…)(b+)

其中一定有 ba，一定要操作且仅操作一次 b。

答案一定是 (b+)(a+) 其中 b 的个数少两个。

首先，操作 b 的时候一定选的是 ba 的 b，因为其余情况，都无法让结尾变成 a，而结尾不是 a 的情况得不到更长的 b 的前缀。

把它的 b 和末尾的 b 交换，一定能 b 少两个且以 a 结尾，将后面两个 b 提前。

交换完后又是以 a 结尾的情况，计算最后交换后长度为 $1$ 的 a 串和长度大于 $1$ 的 $a$ 串的变化量即可。

---

结束讨论，时间复杂度 $\mathcal{O}(\sum |S|)$。

#include 

using namespace std;

typedef long long ll;
#define he putchar('\n')
#define ha putchar(' ')

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

const int _ = 2e5 + 10;

int T, n, cnt[2];

char s[_];

signed main() {
	T = read();
	while (T--) {
		scanf("%s", s);
		n = strlen(s);
		cnt[0] = cnt[1] = 0;
		for (int i = 0; i < n; ++i) cnt[s[i] - 'a']++;
		if (cnt[0] == 0 || cnt[1] == 0) {
			printf("%s\n", s);
			continue;
		}
		int a1 = 0, a2 = 0, nw = 0;
		for (int i = n - 1; i >= 0; --i)
			if (s[i] == 'b') {
				for (int j = i - 1; j >= 0; --j)
					if (s[j] == 'a') nw++;
					else if (nw) {
						if (nw == 1) a1++;
						else a2++;
						nw = 0;
					}
				if (nw) {
					if (nw == 1) a1++;
					else a2++;
					nw = 0;
				}
				break;
			}
		//		cout << a1 << " " << a2 << "!!!!\n";
		if (s[n - 1] == 'a') {
			for (int i = 1; i <= cnt[1]; ++i) printf("b");
			for (int i = 1; i <= cnt[0] - 2 * (a1 / 2 + a1 % 2 + a2); ++i) printf("a");
			printf("\n");
		} else if (cnt[0] % 2 == 0) {
			for (int i = 1; i <= cnt[1]; ++i) printf("b");
			printf("\n");
		} else if (s[n - 2] == 'a') {
			// ab
			for (int i = 1; i <= cnt[1] - 1; ++i) printf("b");
			printf("ab\n");
		} else if (s[n - 3] == 'a') {
			// abb
			for (int i = 1; i <= cnt[1] - 2; ++i) printf("b");
			printf("abb\n");
		} else {
			// bbb
			int la = 0, lb = n;
			for (int i = 0; i < n; ++i)
				if (s[i] == 'a') la = max(la, i);
				else lb = min(lb, i);
			if (la < lb) {
				// aaabbb
				printf("a");
				for (int i = 1; i <= cnt[1]; ++i) printf("b");
				printf("\n");
			} else {
				// aaa...bbb
				bool flg = 0;
				for (int i = 0; i <= n - 3; ++i)
					if (s[i] == 'b' && s[i + 1] == 'a' && s[i + 2] == 'a') flg = 1;
				if (flg) {
					// aaa...baa...bbb
					for (int i = 1; i <= cnt[1] - 2; ++i) printf("b");
					for (int i = 1; i <= cnt[0] - 2 * (a1 / 2 + a1 % 2 + a2 - 1); ++i) printf("a");
					printf("\n");
				} else {
					// aaa...ba...bbb
					for (int i = 1; i <= cnt[1] - 2; ++i) printf("b");
					for (int i = 1; i <= cnt[0] - 2 * ((a1 - 1) / 2 + (a1 - 1) % 2 + a2); ++i) printf("a");
					printf("\n");
				}
			}
		}
	}
	return 0;
}

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114