题解：CF1555D Say No to Palindromes

· · 题解

一道水题。

思路

首先，可以猜出一个结论，就是一定要把 s_{l\sim r} 变成形如 abcabc...，acbacb... 等由 a, b, c 组成的全排列的循环组成。

::::success[证明] 由于我数学不太好，将就着看吧。

首先，若 3 个字符内并非 a, b, c 组成的全排列，显然不行，于是证明了每三个字符，肯定就是一个以 a, b, c 组成的全排列，这非常重要。

我们假设前 3 个为 \texttt{abc}，那依据每三个字符，肯定就是一个以 a, b, c 组成的全排列，可以得出第四个字符能且仅能填 a，以此类推，那就一定是 \texttt{abcabc...}。

其余 5 种情况同理，于是证毕。 ::::

与处理一下每一种情况所需要修改的数量，对于每一个询问枚举状态取最小值即可。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define ppc(x) __builtin_pop_count(x)
#define SZ(x) (x).size()
#define pb(x) push_back(x)
#define Cst constexpr
Cst int N = 2e5 + 5;
Cst int ch[][3] = {
    {0, 1, 2},
    {0, 2, 1},
    {1, 0, 2},
    {1, 2, 0},
    {2, 0, 1},
    {2, 1, 0}
};
int fIO = []() {
    return cin.tie(0)->sync_with_stdio(0), 0;
}();
string s;
int n, m, sum[6][N];
auto Init = []() -> void {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 6; ++j) {
            sum[j][i] = sum[j][i - 1] + (s[i - 1] - 'a' != ch[j][(i - 1) % 3]);
        }
    }
};
int main() {
    cin >> n >> m >> s;
    Init();
    while (m--) {
        int l, r, Ans = INT_MAX; cin >> l >> r;
        for (int i = 0; i < 6; ++i) 
            Ans = min(Ans, sum[i][r] - sum[i][l - 1]);
        cout << Ans << '\n';
    }
}

::::