[BZOJ 3725]Matryca

danihao123 posted @ 2016年8月03日 18:09 in 题解 with tags bzoj PA 神奇题 , 162 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很有意思的思考题。

这道题通过特殊情况我们可以猜想,假设最近两个不同色块距离为[tex]x[/tex](这是半闭半开序列长度),则答案为[tex]n-x+1[/tex]。然而事实就是如此。

代码:

/**************************************************************
    Problem: 3725
    User: danihao123
    Language: C++
    Result: Accepted
    Time:216 ms
    Memory:1796 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
char buf[maxn];
int main(){
    int n;
    register int i,now;
    char last_s=0;
    scanf("%s",buf);
    n=strlen(buf);
    register int ans=n;
    for(i=0;i<n;i++){
        if(buf[i]!='*'){
            if(last_s){
                if(buf[i]!=last_s){
                    ans=min(ans,i-now);
                    last_s=buf[i];
                    now=i;
                }else{
                    now=i;
                }
            }else{
                last_s=buf[i];
                now=i;
            }
        }
    }
    printf("%d\n",n-ans+1);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter