AtCoder Grand Contest 055题解
2024-10-10 08:52:05
我太菜啦!!!md,第一题就把我卡死了...感觉对构造题不会再爱了...
A - ABC Identity
先来看这个题吧,题意就是给定你一个字符串,让你将这个字符串最多分成6个子串,使得每个字符都在某个子串当中,使得每个子串都满足以下条件,每个子串的长度为3的倍数,且前1/3和中间的1/3和最后的1/3内部必须字母一样,且这三部分互不相等。...
构造题我也不是没做过,看到最多6种,我就知道肯定有一种方法是6中且满足所有的情况。可怎么向也想不到....呜呜呜呜。3和6的关系...,最后看看题解,不就是排列吗?6是3的全排列啊,我们先将整个字符串分成三部分,每次从每部分各拿出一个,然后按照格子的排列合并不就行了....吐了...
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
int n,b[N],vis[N];
char c[N];
inline void work(char A,char B,char C,int id)
{
int tot1=0,tot2=0,tot3=0;
for(int i=1;i<=n;++i)
{
if(!vis[i]&&c[i]==A) tot1++;
if(!vis[n+i]&&c[n+i]==B) tot2++;
if(!vis[2*n+i]&&c[2*n+i]==C) tot3++;
}
tot1=tot2=tot3=min(min(tot1,tot2),tot3);
for(int i=1;i<=n;++i)
{
if(!vis[i]&&c[i]==A&&(tot1--)>0) b[i]=id,vis[i]=1;
if(!vis[n+i]&&c[n+i]==B&&(tot2--)>0) b[n+i]=id,vis[n+i]=1;
if(!vis[2*n+i]&&c[2*n+i]==C&&(tot3--)>0) b[2*n+i]=id,vis[2*n+i]=1;
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
scanf("%s",c+1);
work('A','B','C',1);
work('A','C','B',2);
work('B','A','C',3);
work('B','C','A',4);
work('C','A','B',5);
work('C','B','A',6);
for(int i=1;i<=3*n;++i) printf("%d",b[i]);
return 0;
}
最新文章
- storyboard简单认识
- windows设置开机启动项
- 用js实现QQ自定义在线图片
- Js图片切换
- Android,visibility属性
- Unity小厨房之-----背后视角摄像机
- CSS3技巧:利用css3径向渐变做一张优惠券(转)
- 二分法 (UVA10668 Expanding Rods)(二分+几何)
- JDK_Proxy_InvocationHandler_动态代理
- windows下和linux下 Redis 安装
- 9.21 investments - chapter 4 - Summary
- WC2016自测
- OC基础之可循环滚动并突出中间图片,并且可点击
- HDU 6108(整除判断 数学)
- python之连接oracle模块(cx_Oracle)
- Java读取.properties配置文件
- poj3481 splaytree模板题
- 【转帖】oracle数据类型和对应的java类型
- 4 jmeter badboy脚本开发技术详解
- SEO:关键词布局
热门文章
- HiveServer2的负载均衡高可用与ActicePassive高可用浅析
- 使用SQL SERVER存储过程实现历史数据迁移
- 双非Java的学习之旅以及秋招路程
- 洛谷P1060——开心的金明
- Java基础系列(30)- 命令行传参
- Jmeter系列(14)- Setup与tearDown线程组
- SpringBoot 整合 Elastic Stack 最新版本(7.14.1)分布式日志解决方案,开源微服务全栈项目【有来商城】的日志落地实践
- P6222-「P6156 简单题」加强版【莫比乌斯反演】
- P3293-[SCOI2016]美味【主席树】
- Winform 窗体自适应