T4 午枫的01串翻转
题目大意
给定一个 010101 串,可以进行指定操作,求出所有可能的 010101 串中距离最远的两个 000 的距离是多少。
题解思路
我们其实最多只需要操作一次即可得到答案。
一共分三种情况:
* 没有 000 ,直接输出 000 。
* 只有一个 000 ,此时很容易发现不操作的话距离一定是 000 ,所以我们尽量考虑操作。
* 如果这个 000 在最后两个位置,要么无法操作,要么操作了一次也还是只能有一个 000 , 此时答案为 000 .
* 如果不在最后两个位置,考虑到其余位置都为 111 ,我们尽量操作更长的区间,能使两个 000 的距离最大,那么以这个 000 为区间左端点,最后一个 111 为区间右端点,对这段区间进行一次操作,就会将区间内所有的 111 都变为 000 ,此时答案为 翻转区间长度−1翻转区间长度-1翻转区间长度−1 .
* 有两个及以上个 000 ,此时我们可以让最左端的 000 不动,记这个 000 的位置为 pospospos ,用后面的任意 000 最为操作区间的左端点,最后一个 111 最为区间右端点,不难发现,操作后距离最左端的 000 最远的 000 一定是最后一个字符,此时答案为 n−posn-posn−pos .
综上所述,此题只需找到第一个 000 的位置,按照上述情况分类讨论即可。
参考代码