AGC059 A - My Last ABC Problem

传送门:ATcoder

题目描述:

暂略
输入:
6 4
ABCCCA
3 5
2 3
1 3
1 6
输出:
0
1
2
2
1
2
3
4
5
6
7
8
9
10
11
12
13

emmm,同样是AGC第一题,这一次的我和上一次一样都没写出来…绝了,不愧是ATcoder

看了官方的英文题解理解了大半个小时,决定自己写一篇题解

首先对于这道题,我们考虑一下使我们的字符串的首尾相连(为了方便以后的操作),然后我们的区间操作应该可以照样的对这个环进行.为什么呢,因为对于一个区间,我们对这个区间进行换数操作,其实可以等价于对这个区间外的其他字符进行反向的换数操作.可以想一下,假如我们的区间里有A,我们将其变成B,我们改变之后,然后其实对于我们的所有字符A,B,因为我们最后需要求出的答案是所有字符相同,所以当我们将整段序列中的所有A改为B,所有B改为A,对我们的最终答案没有影响,然后经过这个操作之后,我们的序列就变成了只有区间外的字符进行了改变.

然后我们还需要发现,对于一个区间,我们先将这个区间内的所有相邻字符的不同的个数求出来,也就是不同的字符区间.个数记为K,对于这些字符区间,我们有以下结论:那就是当我们进行一次改变操作之后,我们的不同区间的个数将会减2,接下来我们来证明一下这个结论

首先对于一个操作,显然我们是进行整个区间的所有数字进行操作是最优的,也就是我们可以简单的将每一个相同的字符区间视为一个字符集合.然后我们接下来就需要讨论这个字符集和即可

那么对于我们的字符集合有一个显然的特性:也就是相邻的两个字符集和肯定是不同的

那么对于我们的选择情况应该有以下几种:

首先是当我们的K(不同的字符个数)$>=4$时(注意此时是一个环,首尾也算),那么此时对于我们选择的三个字符:
可能13相同,不妨设为ABA类型,那么此时只要将B改成A即可,显然消除了2个不同区间

要么就是13不同,记为CBA,那么对于我们的C的左边,显然是和C不同的,也就是A或者B,对于A的右边,可能为C或者B,那么此时我们只需要将C改为我们的A,B中的一个,同时A改为B,C中的一个即可,B的改变无所谓,因为只要对三个不同的字符进行操作,那么无论如何都不会减少不同区间.但是我们会发现当我们的C改为B的时候,A不能改为B怎么办,没关系,因为对于我们的C改为B的情况,此时我们的C已经消除了两个不同区间了,也就满足我们需要证明的情况

所以证毕;

所以当我们一次减少2,那么最终的答案显然是$(K/2)$

对于K=2或3的情况,我们随便讨论一下即可解决,发现肯定为2

对于不同字符的个数,我们可以使用前缀和的形式进行解决

希望下一次能写出AGC第一题…