美文网首页
HDU3068和while(~scanf("%s",s))

HDU3068和while(~scanf("%s",s))

作者: 单林敏 | 来源:发表于2019-04-17 16:52 被阅读0次

~是按位取反
scanf的返回值是输入值的个数
如果没有输入值就是返回-1
-1按位取反结果是0
while(~scanf("%d", &n))就是当没有输入的时候退出循环

菜鸡自己一般用cin>>a>>b;所以用scanf很不熟练,今天在写HDU3036的时候,就卡在了
while(~scanf("%s",s)) 上面
自己写的while(scanf("%s",s)) 导致题目一直超时

附上Manacher的ACcode

// 2019年4月17日15:57:54开始看题
// 直接裸的Manacher,所以再默写一次
// 2019年4月17日16:10:56 一次过?No,tle了!但是bxbb这个没有出错,疯狂TLE是什么鬼

// 仔细比较了我的代码和别人的代码,2019年4月17日16:36:49发现最终我TLE的原因竟然是while(scanf("%s",s))要在scanf前面加上~!!!
// 果然卡题打铁就是因为自经验不够的原因,所以必须多多刷题,积累各种魔鬼级别的bug
// 40mins,其中30mins在debug...

// #include <bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;
const int M = 110010; // 记得开两倍是真的
char s[M],t[2*M];
int p[2*M];

int Init(){
    // int n = strlen(s);
    t[0] = '$',t[1] = '#';
    int j=2;
    // for(int i=0;i<n;i++){
    for(int i=0;s[i];i++){
        t[j++] = s[i];
        t[j++] = '#';
    }
    t[j] = '\0';
    return j;
}

int Manacher(){
    int n = Init();
    int max_len = -1;
    int mx=0,id=0;
    for(int i=1;i<n;i++){
        if(i<mx) p[i] = min(p[2*id - i],mx - i);
        else p[i] = 1;
        while(t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        if(mx<i+p[i]){
            id = i;
            mx = i + p[i];
        }
        max_len = max(max_len,p[i]-1);
    }
    return max_len;
}

int main(int argc, char const *argv[])
{
    // int kase = 0;
    while(~scanf("%s",s)) {
        // kase++;
        // int m = strlen(s);
        // s[m] = '\0';
        // memset(p,sizeof(p),0);  // 都是由前面生成的,所以不用这样
        // memset(t,sizeof(t),0);
        printf("%d\n",Manacher());
    }
    return 0;
}

相关文章

网友评论

      本文标题:HDU3068和while(~scanf("%s",s))

      本文链接:https://www.haomeiwen.com/subject/qxwnwqtx.html