[AGC055A] ABC Identity 题解
2023/6/14 18:22:17
本文主要是介绍[AGC055A] ABC Identity 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[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]; }
这篇关于[AGC055A] ABC Identity 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升