美文网首页
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