【BZOJ-3725】Matryca 乱搞

3725: PA2014 Final Matryca

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 160 Solved: 96
[Submit][Status][Discuss]

Description

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

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

Input

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

Output

输出最小的k。

Sample Input

A*B*B*A

Sample Output

HINT

解释：

刷子的颜色为ABBBBA。

Source

鸣谢Jcvb

Solution

脑洞题，没什么好说的

答案是 len-mindis+1

len为字符串长度，mindis为相邻非*不同颜色的最短距离

不妨这样考虑：

假如，所以有颜色都必须是纯色，且两两不同，那么显然刷子为n，那么假如不同色的相邻最近为2，那么显然刷子刷子为n-2+1

同理.....

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 1000010
char s[MAXN],A;
int l,n,a,dis;
int main()
{
    scanf("%s",s+1); n=strlen(s+1);
    A='&'; dis=n;
    for (int i=1; i<=n; i++)
        if (s[i]!='*')
            {
                if (A=='&') A=s[i],a=i;
                else
                    if (A!=s[i])
                        {
                            dis=min(dis,i-a);
                            a=i,A=s[i];
                        }
                    else a=i;
            }
    printf("%d
",n-dis+1);
    return 0;
}