[AGC055A] ABC Identity 題解
題目描述
給定長度為 \(3n (1 \le n \le 2e5)\) 的序列，其中字母 A,B,C 各有 \(n\) 個，
一個合法序列 \(T\) 滿足以下條件：
-
其長度為 \(3k (1 \le k \le n)\)，
-
\(T_1 = T_2 = ... = T_k\)
-
\(T_{k + 1} = T_{k + 2} = ... = T_{2k}\)
-
\(T_{2k + 1} = T_{2k + 2} = ... = T_{3k}\)
-
\(T_1, T_{k + 1}, T_{2k + 1}\) 互不相同，
求一個把這個序列分成不多于 \(6\) 個合法的序列的方案，
可以證明，一定存在一種合法的劃分，
決議
將序列分成等長的 3 段，用桶來記錄每一段 A,B,C 個數，列舉 6 種排列 \(ABC,ACB,BAC,BCA,CAB,CBA\)，
等長的 3 段中，第 \(i\) 段取當前排列的第 \(i\) 個字母，
取盡量多，也就是三個桶取min，
可以證明列舉完以后序列所有字母會被選完，
第 \(k\) 種排列就劃分到第 \(k\) 組，
排列只有 6 種，當然也只有 6 組，
代碼
#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 9;
int n,l,r,mid,ans[N];
char a[N],ck[7][4]={{'0','0','0'},
{'A','B','C'},{'A','C','B'},
{'B','A','C'},{'B','C','A'},
{'C','A','B'},{'C','B','A'}};
int t[4][4];
void input(){
cin>>n>>a + 1;
for(int i = 0; i <= 2; ++i){
for(int j = i * n + 1; j <= (i + 1) * n; ++j){
++t[i][a[j] - 'A'];
}
}
}
void cg(int num, int cd){
for(int i = 0; i <= 2; ++i){
int now = num;
for(int j = i * n + 1; j <= (i + 1) * n && now; ++j){
if(ck[cd][i] == a[j] && (!ans[j]))
ans[j] = cd, --now;
}
}
}
void op(){
for(int i = 1; i <= 6; ++i){
int num = min(t[0][ck[i][0] - 'A'], min(t[1][ck[i][1] - 'A'], t[2][ck[i][2] - 'A']));
cg(num, i);
t[0][ck[i][0] - 'A'] -= num;
t[1][ck[i][1] - 'A'] -= num;
t[2][ck[i][2] - 'A'] -= num;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
input();
op();
for(int i = 1; i <= 3 * n; ++i)
cout<<ans[i];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555204.html
標籤：其他
上一篇：自然語言處理 Paddle NLP - 文本語意相似度計算（ERNIE-Gram）
下一篇：返回列表