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