agc048 A,B,C题解

体验极差

被A卡了1h+6WA,B玩着玩着搞出来了,发现C是水题结果没时间写了

A - atcoder < S

看反了以为修改的是目标串

简单分类讨论,先判掉0的情况,那么答案一定>=1,即存在一个位置使得前面都相等并且不同的位要更小

不可能是第一位,如果是第二位并且不是a的话那么交换12位,否则在后面找换到头的字母

如果某个字母>t那么即可换到第二位,>a即可换到第一位,简单判断取min

B - Bracket Score

灵光一闪

结论:一个合法的串把偶数位AB反转后AB个数相等

感性证明:按照ABAB分成若干交替串,反转后变成一段A一段B交替,每次消掉两个相邻的AB,并且消掉之后剩下的AB不会变,因此只和一开始的个数有关

排序取前n/2个即可

C - Penguin Skating

水题

直接考虑两个企鹅的间隔,把间隔当成滑块,每次把一个滑块左右移动,如果两个滑块相碰则合并

贪心考虑即可,构出在位置i的块的移动的次数大概是max(i+1,右端点)-min(i,左端点)-1

原文地址:https://www.cnblogs.com/gmh77/p/13843675.html