题解：P6221 [COCI2019-2020#6] Trener

一道水题（我真是太弱了啊啊啊啊。

众所周知，看到这个题立刻知道他是要选名字长度为 1 到 N 的，而我们知道他每一个名字，所以可以直接用字符哈希去做，因为他每一个名字的字符数是上一层名字的字符数加一，所以对于哈希每个字符串只需要跑三次，分别是自己的这个序列的哈希，以及去头，去尾的两个哈希值，目的是为了与上一个字符比较。

然后我想的是用加法原理一层层去跑出答案（其实和图论的思想差不多）。

易看出时间复杂度为三次方级别的，在两秒的时限下可以过掉此题。

然后模拟赛时我全部 MLE 到飞起。

50 昏

#include<bits/stdc++.h>
#define int long long

#define pb push_back

#define P 1145141

#define ULL unsigned long long

using namespace std;

const int N=51,K=2000,mod=1e9+7;

int n,k;
vector<int> G[N][K];
int sum;
int ans[N][K];

ULL dt[N][K][3];
ULL Hash(char s[],int i,int len)
{
    ULL res=0;
    for(;i<len;i++)
        res=res*P+s[i]-'a'+1;
    return res;
}

signed main()
{
    freopen("trener.in","r",stdin);
    freopen("trener.out","w",stdout);

    char a[K];
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a;
        dt[1][i][2]=Hash(a,0,strlen(a));
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            cin>>a;
            dt[i][j][0]=Hash(a,0,strlen(a)-1);
            dt[i][j][1]=Hash(a,1,strlen(a));
            dt[i][j][2]=Hash(a,0,strlen(a));
            for(int t=1;t<=k;t++)
            {
                if(dt[i-1][t][2]==dt[i][j][0] || dt[i-1][t][2]==dt[i][j][1])
                    G[i][j].pb(t);
            }
        }
    }

    for(int i=1;i<=k;i++)   ans[1][i]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=k;j++)
            for(auto t:G[i][j]) 
                ans[i][j]+=ans[i-1][t],ans[i][j]%=mod;

    for(int i=1;i<=k;i++)   sum+=ans[n][i],sum%=mod;

    cout<<sum<<endl;
    return 0;
}

赛后 5 分钟,我发现了我存图的动态数组的空间复杂度也是三次方级别的，直接炸掉。

然后我才看见我原来是可以把这个问题做成一个几乎在线的做法，就是把我向上递推的过程与输入合并在一起，这样就可以使我的数组减少一维。

CODE

#include<bits/stdc++.h>
#define int long long

#define pb push_back

#define P 1145141

#define ULL unsigned long long

using namespace std;

const int N=51,K=1600,mod=1e9+7;

int n,k;
int sum;
int ans[N][K];
vector<int> G[K];
ULL dt[N][K][3];
ULL Hash(char s[],int i,int len)
{
    ULL res=0;
    for(;i<len;i++)
        res=res*P+s[i]-'a'+1;
    return res;
}

signed main()
{
    freopen("trener.in","r",stdin);
    freopen("trener.out","w",stdout);
//  
    char a[K];
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a;
        dt[1][i][2]=Hash(a,0,strlen(a));
    }

    for(int i=1;i<=k;i++)   ans[1][i]=1;

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            cin>>a;
            dt[i][j][0]=Hash(a,0,strlen(a)-1);
            dt[i][j][1]=Hash(a,1,strlen(a));
            dt[i][j][2]=Hash(a,0,strlen(a));
            for(int t=1;t<=k;t++)
                if(dt[i-1][t][2]==dt[i][j][0] || dt[i-1][t][2]==dt[i][j][1])
                    G[j].pb(t);
        }
        for(int j=1;j<=k;j++)
            for(auto t:G[j])    
                ans[i][j]+=ans[i-1][t],ans[i][j]%=mod;
        for(int j=1;j<=k;j++) G[j].clear();
    }

    for(int i=1;i<=k;i++)   sum+=ans[n][i],sum%=mod;

    cout<<sum<<endl;
    return 0;
}