[AGC055A] ABC Identity 题解

这篇具有很好参考价值的文章主要介绍了[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 组。文章来源地址https://www.toymoban.com/news/detail-482080.html

代码

#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 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ABC330 A-E 题解

    枚举一遍,当前数大于 (L) 使 (ans+1) 即可. 枚举一遍,当前数在 (L,R) 之间,结果就是它本身,小于 (L) 为 (L) ,大于 (R) 为 (R) . 枚举 (i:0simsqrt{d}) 为第一个数,以 (1) 为左边界, (sqrt{d-i^2}+1) 为右边界,判定条件为 (mid^{2}) 与 (d-i^2) 之间的大小关系,每次更新边界后 (ans=

    2024年02月05日
    浏览(41)
  • ABC341A-D题解

    这个没什么好说的,就先输出一个 1 ,再输出 n n n 个 01 就大功告成了。 要获取更多 x x x 国货币,只能用 x − 1 x - 1 x − 1 国货币换。 所以我们可以从 1 1 1 国一直换到 n n n 国,输出,结束。 你会发现, 50 0 3 2 ⋅ 1 0 8 500^32cdot10^8 50 0 3 2 ⋅ 1 0 8 ,所以可以暴力枚举高桥所在

    2024年02月19日
    浏览(32)
  • 题解:ABC320B - Longest Palindrome

    链接:Atcoder。 链接:洛谷。 算法难度:C。 思维难度:C。 调码难度:C。 综合评价:入门。 字符串处理。 通过双层循环分别枚举第一个字符和最后一个字符遍历每个子串,在分别判断是否为回文串,在所有是回文串的里面取长度最大值。 O(|s|2)。 字符串截取用substr函数。

    2024年02月07日
    浏览(41)
  • [ABC347C] Ideal Holidays题解

    原题传送门 原题传送门(洛谷) ​题意翻译: ​在 (AtCoder) 王国中,一个周有 (A+B) 天。其中在一周中, ([1,A]) 天是假日, ([A+1,B]) 天是工作日。 ​高桥有 (N) 个计划,第 (i) 个计划安排在 (i) 天后。他不知道今天是周几,但他想知道是否能将计划都安排在假期中;

    2024年04月08日
    浏览(41)
  • [ABC319E] Bus Stops 题解

      给定 (n) 个公交站。对于第 (i) 个公交站,在时刻 (p_i times k,k in mathbb{N}) 有一辆公交车出发,在经过 (t_i) 的时间后,到达第 (i+1) 个公交站。   在走到第一个公交车之前需要走 (X) 时刻,做到最后一个公交站之后下车以后还需要走 (Y) 时刻。   约束: (1

    2024年02月09日
    浏览(34)
  • [ABC318C] Blue Spring 题解

      主人公出去旅游要买票,共有若干天,每天要花不同钱。现在有“通行证”出售,通过购买通行证,可以在某一天直接用通行证,以此来省去当天原本需要花费的票价。通行证只能一套一套买,每套中有 (D) 个,买一套要花费 (P) 元。可以购买任意套数的通行证,求怎

    2024年02月10日
    浏览(40)
  • AtCoder abc336 A~D题解

    题目翻译: 对于正整数 X X X 级别的龙串, X X X 是长度为 ( X + 3 ) (X+3) ( X + 3 ) 的字符串,由按此顺序排列的 o 、 n 和 g 的一次 L 、 X X X 次出现形成。 你得到一个正整数 N N N 。打印 N N N 级的龙串。 分析 按题目要求做即可……,输出一个 L ,循环 X X X 次输出 o ,再输出 ng 。

    2024年01月15日
    浏览(37)
  • AT_abc344_e 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 赛时各种【数据删除】原因导致没做出来。 给你一个长度为 (N) 的序列 (A=(A_1,ldots,A_N)) 。保证 (A) 中的元素是不同的。 你要处理 (Q) 个操作。每个操作是以下两种类型之一: 1 x y :在 (A) 中元素 (x) 后面紧接着插入 (y) 。

    2024年03月13日
    浏览(42)
  • AT_abc344_d 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 你最开始有一个空字符串 (S) 。 你还有编号为 (1, 2, dots, N) 的袋子,每个袋子都包含一些字符串。 袋子 (i) 包含 (A_i) 个字符串 (S_{i,1}, S_{i,2}, dots, S_{i,A_i}) 。 对 (i = 1, 2, dots, N) 重复以下步骤 仅一次 (这里原题没有讲清楚

    2024年03月10日
    浏览(48)
  • AT_abc345_d 题解

    本文同步发表于洛谷。 是个逆天搜索。 最开始:爆搜,启动! 然后 TLE 到飞起。 赛后:我【数据删除】这么简单的吗?! dfs 每个位置,试着把没放过的块放到以这个位置为左上角的区域里面。 好了没了,就是这么简单! 对了记得这个块可以旋转!

    2024年03月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包