YCKCOJ清明进阶专题题解

本文主要是介绍YCKCOJ清明进阶专题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

总的来说还是有难度的，这也能二分？？？
本套题需要大家尽量思考

A题 DARLING in the FRANXX
实际上这是一部好看的日漫，本题的背景主要以 $叫龙$ 为主，它是一种生物。。。好了言归正传，抓住核心题意: 02只想一次性清理掉某一级别的叫龙，所以不难发现最终我们环的排列方式一定是所有的A B C分别连成一块，例如AAAABBBBBCCCCC这样子。

对于环的问题，我们要固定一个点，这样子思维才不会被环的特殊性所迷惑(因为是环所以无法区分首尾)，假设我们以1位置作为环的开头。

实际上最终02消灭叫龙的时候无外乎消除顺序是ABC的几种排列:
$A BC$
$A CB$
$B A C$
$BC A$
$C A B$
$CB A$
我们就按六种方式依次枚举，当然需要借助到一个快速统计的工具
以最终排列 $A BC$ 为例子，先统计一开始分别有 $A, B, C$ 种类的叫龙个数，如果以 $A$ 开头，那么由于环的性质，我们可以在开头摆放若干个 $A$ 叫龙，结尾摆放剩余叫龙，假如说 $A$ 叫龙一共有 $a$ 只，那么我们可以摆放0~a只叫龙在首，剩余在尾，这个可以枚举。然后摆放所有的 $B$ 叫龙与 $C$ 叫龙。但是我们需要知道一个数据: $把某种叫龙全部填在某个区间需要的引导次数$
这个东西可以用前缀和实现，定义前缀和 $A [i]$ 为 $1$ – $i$ 位置内非 $A 叫龙$ 的个数，假如说我们现在要把 $a$ 只 $A$ 叫龙全部引导在一个长度为 $a$ 的区间 $[L, R]$ ，那么求法就是 $A [R] - A [L - 1]$ ，直接计算区间内有多少个不是 $A$ 龙，然后引导即可，当然还要一种特殊的情况，那就是环，如果是环的话则是由开头一段+结尾一段来计算引导数，详情请看代码。

前缀和记录好以后，枚举第2个字母摆放位置，然后前缀和计算。
为什么枚举第2个字母的摆放位置呢?
实际上就是在考虑从首位置开始，摆放多少只第1个字母对应的叫龙，例如A叫龙一共a只，那么我可以在首位置开始摆放0~a只，那么第2个字母摆放的位置只能是1 ~ a+1

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int A[maxn], B[maxn], C[maxn];
char s[maxn];
int num[3];
int main()
{std::ios::sync_with_stdio(false);int n;cin >> n;cin >> s + 1;int a = 0, b = 0, c = 0;for(int i = 1;i <= n;i++){if(s[i] != 'A') A[i] = A[i - 1] + 1;else A[i] = A[i - 1], a++;if(s[i] != 'B') B[i] = B[i - 1] + 1;else B[i] = B[i - 1], b++;if(s[i] != 'C') C[i] = C[i - 1] + 1;else C[i] = C[i - 1], c++;}int ans = 1e9;for(int i = 1;i <= c + 1;i++)//AB{int cost = A[i + a - 1] - A[i - 1] + B[i + a + b - 1] - B[i + a - 1];cost += C[i - 1] + C[n] - C[i + a + b - 1];ans = min(cost, ans);}for(int i = 1;i <= c + 1;i++)//BA{int cost = B[i + b - 1] - B[i - 1] + A[i + a + b - 1] - A[i + b - 1];cost += C[i - 1] + C[n] - C[i + a + b - 1];ans = min(cost, ans);}for(int i = 1;i <= b + 1;i++)//AC{int cost = A[i + a - 1] - A[i - 1] + C[i + a + c - 1] - C[i + a - 1];cost += B[i - 1] + B[n] - B[i + c + a - 1];ans = min(cost, ans);}for(int i = 1;i <= b + 1;i++)//CA{int cost = C[i + c - 1] - C[i - 1] + A[i + c + a - 1] - A[i + c - 1];cost += B[i - 1] + B[n] - B[i + c + a - 1];ans = min(cost, ans);}for(int i = 1;i <= a + 1;i++)//BC{int cost = B[i + b - 1] - B[i - 1] + C[i + c + b - 1] - C[i + b - 1];cost += A[i - 1] + A[n] - A[i + c + b - 1];ans = min(cost, ans);}for(int i = 1;i <= a + 1;i++)//CB{int cost = C[i + c - 1] - C[i - 1] + B[i + c + b - 1] - B[i + c - 1];cost += A[i - 1] + A[n] - A[i + c + b - 1];ans = min(cost, ans);}cout << ans << endl;return 0;
}