BZOJ3725: PA2014 Final Matryca题解

Description
有一堵长度为n的墙需要刷漆，你有一把长度为k的刷子。墙和刷子都被均匀划分成单位长度的小格，刷子的每一格中都沾有某种颜色（纯色）的漆。你需要用这把刷子在墙上每一个可能的位置（只要刷子不超出墙，且对准格子；共有n-k+1个位置）都刷一遍。如果墙上的某一格被不同颜色的漆刷过，那么它会呈现混合色。

现在墙上某些格子需要刷成给定的颜色。求出能够完成任务的最短的刷子长度k。

Input
输入为一个长度为n(1<=n<=1000000)的字符串，由大写字母和星号组成。大写字母表示某种纯色，星号表示此位置颜色不作要求。

Output
输出最小的k。

Sample Input
ABB*A
Sample Output
6
HINT
解释：

刷子的颜色为ABBBBA。

solution：

这道题还主要是一个大胆猜测题。

发现

于是就 $O (n)$ 找出 $x$ 就行了。

这里还要注意：

刚开始的tmp不能直接给成 $s [0]$ ，因为 $s [0]$ 不一定有颜色要求，要先给成一个不可能出现的字符。
不要习惯了把last和tmp都开始char（笑哭，也就只有我会犯这种zz错误）
ans要给成n，因为n就是刷子最长可能的数了

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
char s[1000005];
int main()
{
	scanf("%s",s);
	int n=strlen(s);
	char tmp='$';
        int last=0;
	int ans=n;
	for(int i=0;i<n;i++) 
	{
		if(s[i]!='*')
		{
			if(tmp=='$')
			{
				tmp=s[i];
				last=i;
			}
			else
			{
				if(s[i]!=tmp)
				{
					ans=min(ans,i-last);
					tmp=s[i];
					last=i;
				}
				else
				{
					last=i;
				}
			}
		}
	}
	printf("%d\n",n-ans+1);
	return 0;
}