AGC-059解题报告

比赛传送门

A. My Last ABC Problem

题意：有一个只含 ABC 字符串 \(s\)，每次询问一段区间 \([l,r]\)，问至少需要多少次操作能将这段区间变得完全相同。每次操作可以选一段区间 \([a,b]\) 和一个 \({A,B,C}\) 的排列，将这段区间内按照排列描述的方式进行替换。

很容易想到考虑连续段，以下描述中一个元素均表示一个连续段。可以发现，每次操作的元素个数要么 \(-1\) 要么 \(-2\)，所以考虑什么时候可以 \(-2\)。我们发现，当某个元素的左右两边相同时，可以直接将这个元素改为和左右两边相同，此时可以 \(-2\)；当与左右两边不同时，可以发现，若段数 \(\ge 5\)，一定可以 \(-2\)，方式为：任选连续五个元素，由于任意元素的左右两边不同，一定形如 ABCAB，此时将中间的三个元素 BCA->ABC 即可满足要求。还发现一个性质，即 \(-2\) 的时候一定不会改变两端。所以考虑反复进行 \(-2\)，直到元素个数为 \(3\) 或 \(4\)。此时，当元素个数为 \(4\) 时答案一定为 \(2\)；元素个数为 \(3\) 时答案取决于两端是否相等。可以统一情况如下：

By cxm1024

#include<bits/stdc++.h>
using namespace std;
int f[100010];
signed main() {
	int n,q;
	string s;
	cin>>n>>q>>s;
	for(int i=0;i<s.size();i++)
		if(i>0) f[i]=f[i-1]+(s[i]!=s[i-1]);
	while(q--) {
		int l,r;
		cin>>l>>r;
		l--,r--;
		if(s[l]==s[r]) cout<<(f[r]-f[l]+1)/2<<endl;
		else cout<<(f[r]-f[l])/2+1<<endl;
	}
	return 0;
}

错解：

By daisybunny

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int q;
vector<int> v;
int sum[3][100005];
int main()
{
	cin>>n>>q>>s;
	v.push_back(0);
	for(int t=1;t<n;t++)
		if(s[t]!=s[t-1])
			v.push_back(t);
	for(int t=0;t<v.size();t++)
	{
		sum[s[v[t]]-'A'][v[t]+1]++;
	}
	for(int t=1;t<=n;t++)
		for(int i=0;i<3;i++)
			sum[i][t]+=sum[i][t-1];/*
	for(int t=0;t<3;t++)
	{
		for(int i=1;i<=n;i++)
			cout<<sum[t][i]<<" ";
		cout<<endl;
	}*/
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		int a=sum[0][r]-sum[0][l-1],b=sum[1][r]-sum[1][l-1],c=sum[2][r]-sum[2][l-1];
		cout<<a+b+c-max(a,max(b,c))<<endl;
	}
	return 0;
}

一组 hack 数据：ABCABCA。这份代码直接选两种较少的颜色累加，但实际上每次操作可以 \(-2\)，所以必然有 \(/2\) 的操作。

By startcpp

//O(NQ) ....
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <random>
#include <cassert>
#include <unordered_map>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

mt19937 mt(2521);

int naive(string s) {
	queue<string> que;
	unordered_map<string, int> dp;
	map<string, string> prevS;
	vector<vector<int>> perms = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};

	que.push(s);
	dp[s] = 0;
	int ret = -1;
	string ret_s;
	while (!que.empty()) {
		string now = que.front(); que.pop();
		int n = now.length();

		bool check = true;
		for (int i = 0; i < n - 1; i++) {
			if (now[i] != now[i + 1]) { check = false; break; }
		}
		if (check) { ret = dp[now]; ret_s = now; break; }

		for (int i = 0; i < 6; i++) {
			for (int l = 0; l < n; l++) {
				string t;
				for (int r = l; r < n; r++) {
					int x = perms[i][now[r] - 'A'];
					t += (char)(x + 'A');
					string nxt;
					for (int k = 0; k < l; k++) nxt += now[k];
					nxt += t;
					for (int k = r + 1; k < n; k++) nxt += now[k];
					if (dp.find(nxt) == dp.end()) {
						dp[nxt] = dp[now] + 1;
						prevS[nxt] = now;
						que.push(nxt);
					}
				}
			}
		}
	}

	/*for (int i = 0; i < ret; i++) {
		cout << ret_s << endl;
		ret_s = prevS[ret_s];
	}
	cout << ret_s << endl;*/
	return ret;
}

int greedy(string s) {
	int i;
	string ss;
	rep(i, s.length()) {
		if (i > 0 && s[i - 1] == s[i]) continue;
		ss += s[i];
	}
	//cout << "ss = " << ss << endl;

	int ret = ss.length();
	int n = ss.length();
	typedef pair<int, char> P;
	for (char c = 'A'; c <= 'C'; c++) {
		vector<P> vec;
		int len = 0; char first_char = '-';

		//cout << "c = " << c << endl;
		rep(i, n) {
			if (ss[i] == c) {
				if (len > 0) vec.push_back(P(len, first_char));
				len = 0;
				continue;
			}
			if (len == 0) first_char = ss[i];
			len++;
		}
		if (len > 0) vec.push_back(P(len, first_char));

		int cst = 0;

		rep(i, vec.size()) {
			cst += vec[i].first / 2 + 1;
		}

		int cnt = 0;
		for (int i = 0; i < vec.size(); i++) {
			if (vec[i].first % 2 == 0) cnt++;
		}
		cst -= cnt / 2;
		//cout << "cst = " << cst << endl;
		ret = min(ret, cst);
	}
	return ret;
}

void solve_input() {
	int n, Q;
	cin >> n >> Q;
	string s;
	cin >> s;
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r; l--; r--;

		string t;
		for (int j = l; j <= r; j++) t += s[j];
		cout << greedy(t) << endl;
	}
}

signed main() {
	solve_input();
	return 0;

	//naive("ABCCACABC");
	//return 0;

	/*int n = 10, i;
	int T = 2000;

	for (int t = 0; t < T; t++) {
		cout << "t = " << t << endl;
		string s;
		rep(i, n) {
			s += (char)(mt() % 3 + 'A');
		}
		int res1 = naive(s);
		int res2 = greedy(s);
		if (res1 != res2) {
			cout << s << " " << res1 << " " << res2 << endl;
			break;
		}
	}

	return 0;*/
}

这份代码每次询问都 \(O(n)\) 计算，总复杂度达到 \(O(qn)\)，必然会超时。正解一定需要预处理再回答询问。

如果要设计测试数据，需要充分考虑边界情况，如只有一个元素、只有一种元素、每个元素段的长度均为 \(1\)、只有两种元素等等。除了边界情况，还要通过随机来保证正常数据的强度。既要有两端相同的询问，也要有两端不同的询问。段数少的情况可以枚举所有情况各处一组询问。例如：

32 17
ABCABCABCAAAAAAABABABCACBABCBACA
1 1
2 2
3 3
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
10 15
16 21
22 32
24 30
25 31
1 32