Vegetable Chicken

Vegetable Chicken

我最菜了

题解 P2375 【[NOI2014]动物园】

posted on 2018-01-14 20:30:09 | under 题解 |

神TM阅读理解题

看完题目之后

暴力:每次暴跳 $next$ 数组

太慢啦

优化一下暴力:

搞个倍增数组来跳 $next$

每次倍增跳 $next$

复杂度 $O(Tnlogn)$

算一下,感觉复杂度差不多呀

很果断的交了一发

然后 $80$ 分。。。

暴力代码送上:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MOD 1000000007
char s[1200000];
int nt[1200000];
int jp[1200000][21];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        nt[1]=0;
        int l=strlen(s+1);
        for(int i=2;i<=l;++i)
        {
            int j=nt[i-1];
            while(j&&s[i]!=s[j+1])j=nt[j];
            if(s[i]==s[j+1])nt[i]=j+1;
            else nt[i]=0;
            jp[i][0]=nt[i];
        }
        for(int j=1;j<20;++j)
            for(int i=1;i<=l;++i)
                jp[i][j]=jp[jp[i][j-1]][j-1];
        int ans=1;
        for(int i=2;i<=l;++i)
        {
            int tt=i;
            for(int j=19;j>=0;--j)
                if(jp[tt][j]*2>i)tt=jp[tt][j];
            int gg=0;
            for(int j=19;j>=0;--j)
                if(jp[tt][j])gg+=1<<j,tt=jp[tt][j];
            ans=1ll*ans*(gg+1)%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

然后我很不爽

把倍增数组的两维反了过来,防止反复横跳

然后我就 $AC$ 了???

又一次感受到玄学强大的力量

这个 $O(Tnlogn)$ 的复杂度果然很对呀。。。

暴力能AC???:

(BZOJ上都能AC???)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MOD 1000000007
char s[1200000];
int nt[1200000];
int jp[21][1200000];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        nt[1]=0;
        int l=strlen(s+1);
        for(int i=2;i<=l;++i)
        {
            int j=nt[i-1];
            while(j&&s[i]!=s[j+1])j=nt[j];
            if(s[i]==s[j+1])nt[i]=j+1;
            else nt[i]=0;
            jp[0][i]=nt[i];
        }
        for(int j=1;j<20;++j)
            for(int i=1;i<=l;++i)
                jp[j][i]=jp[j-1][jp[j-1][i]];
        int ans=1;
        for(int i=2;i<=l;++i)
        {
            int tt=i;
            for(int j=19;j>=0;--j)
                if(jp[j][tt]*2>i)tt=jp[j][tt];
            int gg=0;
            for(int j=19;j>=0;--j)
                if(jp[j][tt])gg+=1<<j,tt=jp[j][tt];
            ans=1ll*ans*(gg+1)%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

我的复杂度还是太弱了

这是一篇来自蒟蒻的题解