Step_1 题目简述

对于一个有 $ABC$ 组成的序列 $S$ 可执行如下操作：

1. 选择一个区间 $\left[l, r \right]$ 。

2. 对于选择的区间而言可以将其中所有 $A$ 变为 $A, B, C$ 中的任意一个。 $B$ 和 $C$ 同理。

我们需要通过以上两个操作是的序列 $S$ 相邻两个字符不相等， 求最小步骤和方案。

题目传送门

Step_2 题目分析

不难发现， 此题是一道标准的构造体。
根据题目描述，可以发现序列 $S$ 的如下性质。

1. 假设我将一个区间中的所有 $A$ 变成 $B$ ， 所有 $B$ 变成 $C$ ， 所有 $C$ 变成 $A$ ，那么区间内（除两端）原本与相邻字符不同的依然不同， 原本相同的依然相同，也就是说区间（除两端）的本质不变。

2. 我们一次性最多只能使两个原本与相邻字符相同的字符变的与相邻字符不同。

对于第二点而言， 需要同学们好好领悟一下（也许不用）。

Step_3 正解思路

通过 Step_2 的两点性质，我们不难想出如下方法：

1. 我们指定两个指针 $l, r$ ， 一个指向 $1$ 一个指向 $n$ 。

2. 当当前指针所指与两侧的字符不相等， 那么指针向中间靠拢，否则我将指针所指区间内（不包括两端）的所有字符 $A$ 变成 $B$ ， $B$ 变成 $C$ ， $C$ 变成 $A$ 。

注意，在移动指针时不要其中一个找到目标字符就马上变换区间，因为我们要使步数最小， 所以每次尽量两个一起变。
(PS. 特别注意指针最后一刻的状态， 极为容易出错）

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e3 + 5;

char s[N];
bool map[N];

int tot;
int p1[N], p2[N];
char pr[N][4];

int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		char ch;
		cin >> ch;
		s[i] = ch;
		if (s[i] == s[i - 1] && i != 1) {
			map[i - 1] = 1;
			map[i] = 1;
		}
	}
	int l = 1, r = n;
	while(l < r)
	{
		if (s[l] != s[l + 1]) 
		{
			l++;
			continue;
		}
		if (s[r] != s[r - 1]){
			r--;
			continue;
		} 
		if (l == r - 1){
			if (s[l] != 'A' && s[r + 1] != 'A')
			{
				p1[++tot] = r;
				p2[tot] = r;
				pr[tot][0] = 'A';
				pr[tot][1] = 'A';
				pr[tot][2] = 'A';
				break;
			}
			if (s[l] != 'B' && s[r + 1] != 'B')
			{
				p1[++tot] = r;
				p2[tot] = r;
				pr[tot][0] = 'B';
				pr[tot][1] = 'B';
				pr[tot][2] = 'B';
				break;
			}
			if (s[l] != 'C' && s[r + 1] != 'C')
			{
				p1[++tot] = r;
				p2[tot] = r;
				pr[tot][0] = 'C';
				pr[tot][1] = 'C';
				pr[tot][2] = 'C';
				break;
			}
		}
		
		p1[++tot] = l + 1;
		p2[tot] = r - 1;
		pr[tot]['A' - 65] = 'B';
		pr[tot]['B' - 65] = 'C';
		pr[tot]['C' - 65] = 'A';
		for (int i = l + 1; i <= r - 1; i++) s[i] = pr[tot][s[i] - 65];
	}
	printf("%d\n", tot);
	for (int i = 1; i <= tot; i++)
	{
		printf("%d %d ", p1[i], p2[i]);
		for (int j = 0; j < 3; j++) printf("%c", pr[i][j]);
		puts("");
	}
	return 0;
}

后记

月赛唯一一道作对的题