CFEDU112D–SayNotoPalindromes的解题方法

D - Say No to Palindromes

枚举

可观察到只有类似 abcabcabcabc..., bacbacbac... 等 abc 三个字母都循环出现才满足要求

可记录 \(cnt[i][j][k]\)，前 \(i\) 个中 \(a, b, c\) 分别在 模 \(3\) 余 \(0,1,2\) 的个数

因此枚举 abc 的 6 种排列，用前缀和求最小改动次数即可

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
string s;
int cnt[N][3][3];//cnt[i][j][k]为前i个字母中(a, b, c)分别在(0, 1, 2)三个位置的个数
int n, m;
int l, r;
int solve(int a, int b, int c)
{
int cnt_a = cnt[r][a][0] - cnt[l-1][a][0];
int cnt_b = cnt[r][b][1] - cnt[l-1][b][1];
int cnt_c = cnt[r][c][2] - cnt[l-1][c][2];
return r - l + 1 - cnt_a - cnt_b - cnt_c;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
cin >> s;
s = " " + s;
for (int i = 1; i {
for (int j = 0; j <3; j++)
for (int k = 0; k <3; k++)
cnt[i][j][k] = cnt[i-1][j][k];
char ch = s[i];
int t = i % 3;
if (ch == 'a')
cnt[i][0][t]++;
else if (ch == 'b')
cnt[i][1][t]++;
else
cnt[i][2][t]++;
}

while(m--)
{
cin >> l >> r;
int ans = 1e9;
ans = min(ans, solve(0, 1, 2));
ans = min(ans, solve(0, 2, 1));
ans = min(ans, solve(1, 0, 2));
ans = min(ans, solve(1, 2, 0));
ans = min(ans, solve(2, 0, 1));
ans = min(ans, solve(2, 1, 0));
cout < }
return 0;
}