本文涉及的基础知识点

C++图论

P6709 [CCC 2020] Swapping Seats

题目描述

有N NN个人坐在一张圆桌旁。

共有三个派别，每一个人属于一个派别。

现在，您想使属于同一派别的人坐到一起。

您可以每次将两个人交换位置，输出最小的交换次数。

输入格式

仅一行一个长度为N NN的字符串s ss，为顺时针所有人的派别。

如果s i s_isi​为A，则说明第i ii个人为第一个派别的，以此类推。

输出格式

仅一行一个整数，表示最小的交换次数。

输入输出样例 #1

输入 #1

BABCBCACCA

输出 #1

2

说明/提示

样例解释

BABCBCACCA → AABCBCBCCA → AABBBCCCCA \texttt{BABCBCACCA}\to\texttt{AABCBCBCCA}\to\texttt{AABBBCCCCA}BABCBCACCA→AABCBCBCCA→AABBBCCCCA。

子任务

本题采用捆绑测试，且本题的 Subtask 分数有微调。

• Subtask 1（26 2626分）：s i ∈ { s_i\in\{si​∈{A, ,,B} \}}且N ≤ 5 × 10 3 N\le 5\times 10^3N≤5×103。
• Subtask 2（27 2727分）：s i ∈ { s_i\in\{si​∈{A, ,,B} \}}。
• Subtask 3（27 2727分）：N ≤ 5 × 10 3 N\le 5\times 10^3N≤5×103。
• Subtask 4（20 2020分）：无特殊限制。

对于100 % 100\%100%的数据，保证s i ∈ { s_i\in\{si​∈{A, ,,B, ,,C} \}}，1 ≤ N ≤ 10 6 1\le N\le 10^61≤N≤106。

说明

本题译自 Canadian Computing Competition 2020 Senior T4 Swapping Seats。

环

n1=A派的数量，n2=B派的数量,n3=C派的数量。
如果x派的人，需要去y派坐着的座位，则增加x→ \rightarrow→y。最终有向图一定是若干个环。不失一般性，某路径以A为起点，无环的两条边路径只有ABC和ACB。第四点一定是环。排除自环后，只有两条边的环和三条边的环。2条边的环，只需要一次交换；3条边的环，需要2次交换。
cnt[i][j] 记录(A+i)到(A + j)的边的数量。
统计完2边环，剩余的都是3边环。
f(i)函数：位置i是A，且他的左边没有A，右边依次是BC。
f(0)：一，i∈ \in∈[0,n1-1] cnt[0][s[i]-‘A’]++ 二,i∈ \in∈[n1,n1+n2-1], c n t [ 1 ] [ s [ i ] − ′ A ′ ] + + ，三， i , cnt[1][s[i]-'A']++ ，三，i,cnt[1][s[i]−′A′]++，三，i\in$[n1+n2,N-1]，cnt[2][s[i]-‘A’]++。
f(i)迭代成f(i+1):
i号位由A变成C,i+n1号位由B变成A,i+n1+n2有C变成B。
i号位由A变成C
cnt[0][s[i]-‘A’]–
cnt[2][s[i]-‘A’]++
注意：枚举完ABC，还需要枚举ACB。可以直接原始串的BC互换。

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<bitset>usingnamespacestd;classSolution{public:intAns(conststring&s){string acb=s;;for(auto&ch:acb){if('B'==ch){ch='C';}elseif('C'==ch){ch='B';}}returnmin(Check(s),Check(acb));}intCheck(conststring&s){constintN=s.length();intn1=0,n2=0;for(constauto&ch:s){n1+=('A'==ch);n2+=('B'==ch);}intcnt[3][3]={0};autoNeed=[&](){intremain=0;intring2=0;for(inti=0;i<3;i++){constinti2=(i+1)%3;constintm1=min(cnt[i][i2],cnt[i2][i]);constintm2=max(cnt[i][i2],cnt[i2][i]);ring2+=m1;remain+=m2-m1;}returnring2+remain/3*2;};inti=0;for(;i<n1;i++){cnt[0][s[i]-'A']++;}for(;i<n1+n2;i++){cnt[1][s[i]-'A']++;}for(;i<N;i++){cnt[2][s[i]-'A']++;}intans=Need();for(inti=0;i+1<N;i++){constinti2=(i+n1)%N;constinti3=(i+n1+n2)%N;cnt[0][s[i]-'A']--;cnt[2][s[i]-'A']++;cnt[1][s[i2]-'A']--;cnt[0][s[i2]-'A']++;cnt[2][s[i3]-'A']--;cnt[1][s[i3]-'A']++;ans=min(ans,Need());}returnans;}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGios::sync_with_stdio(0);cin.tie(nullptr);string s;cin>>s;#ifdef_DEBUG//printf("N=%d",n);//cout << ",s=" << s;//Out(edge, ",edge=");//Out(que, ",que=");//Out(que, ",que=");/*Out(que, "que=");*/#endif// DEBUGautores=Solution().Ans(s);cout<<res<<'\n';return0;}

单元测试

vector<int>hs,ws;TEST_METHOD(TestMethod11){Solution slu;autores=slu.Ans("BABCBCACCA");AssertEx(2,res);}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019C++17
或者 操作系统：win10 开发环境： VS2022C++17
如无特殊说明，本算法用**C++**实现。