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

题外话

这套题考的模拟赛，三四题都稍显抽象（没考第一题），就二和五题能做一下，但还被背刺了，DFS 直接爆栈了，学校 OJ 翻译不全真是晦气是道好题。

题目大意

给定 n 组人，每组选一人，要求前一组人的姓名必须是后一组的连续子串，求有多少种合法答案。

解题思路

考虑建图。我们可以将问题看作一第一组为起点，走到最后一组，算做一种解，理论可行，开始实践。

代码思路

暴力

首先考虑暴力，强行判断是不是下一组的连续子串，最后简单动态规划统计方案，也可以用记忆化。期望时间复杂度 O(nk^3)，代码如下（有注释）：

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

using namespace std;
const int N=2000,MOD=1e9+7;
string s[51][1500];
int n,k;
bool check(string a,string b){
    int l=a.size();
    int fl=0;
    for(int i=0,j=0;i<l;i++,j++){
        if(a[i]!=b[j]){
            fl++;
            break;  
        }
    }//这里是看看是第一个不同还是最后一个不同
    for(int i=0,j=1;i<l;i++,j++){
        if(a[i]!=b[j]){
            fl++;
            break;  
        }
    }
    if(fl==2)return false;
    return true;
}
vector<int> edge[N*N];
int f[N*N];
void add(int u,int v){
    edge[u].push_back(v);
}
int dfs(int u){
    if(f[u])return f[u];
    for(int v:edge[u]){
        f[u]+=dfs(v);
        f[u]%=MOD;
    }
    f[u]%=MOD;
    return f[u];
}//状态转移方程式太难辣，直接记忆化
signed main(){
    freopen("trener.in","r",stdin);
    freopen("trener.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=k;i++)f[i]=1;
    for(int i=1;i<=k;i++)add(i,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++)
            cin>>s[i][j];
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            string s1=s[i][j];
            for(int p=1;p<=k;p++)
                if(check(s1,s[i+1][p])){
                    add(p+i*k,j+(i-1)*k);
                }//从下向上连边，方便搜索。
        }//这里相当于将二位平铺成一维，方便建图。
    }
//  for(int i=0;i<=n*k;i++){
//      for(int j:edge[i])
//          cout<<i<<" "<<j<<'\n';
//  }
    int ans=0;
    for(int i=k*n;i>k*(n-1);i--)ans+=dfs(i),ans%=MOD;
//  for(int i=1;i<=n*k;i++)
//  cout<<f[i]<<" ";
    cout<<ans;
    return 0;
}

优化

打完之后恭喜你，获得 50 分！仔细观察就能发现大有优化的余地。输入是 O(nk^2)，没有优化空间，枚举也是如此，只有判断相等开销大并且可以优化，回想我们学过的方法，有没有什么能 O(1) 判断字符串相同呢，对啦，就是哈希，想到这点十分开心，直接把代码打出来：

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

#define ull unsigned long long

using namespace std;
const int N=51*1510,mod=1e18+9,MOD=1e9+7,base=131;
string s;
int n,k;
ull Hash[52][1510][3];
int HASH(string a){
    ull pr=base,res=0;
    int l=a.size();
    for(int i=0;i<l;i++){
        res=res+pr*(ull)(a[i]-'a'+1)%mod;
        res%=mod;
        pr*=base;
        pr%=mod;
    }
    return res;
}
bool check(int x,int y,int xx,int yy){
    if(Hash[x][y][2]==Hash[xx][yy][0]||Hash[x][y][2]==Hash[xx][yy][1])
        return true;
    return false;
}
vector<int> edge[N];
int f[N];
void add(int u,int v){
    edge[u].push_back(v);
}
int dfs(int u){
    if(f[u])return f[u];
    for(int v:edge[u]){
        f[u]+=dfs(v);
        f[u]%=MOD;
    }
    f[u]%=MOD;
    return f[u];
}
int in[N];
signed main(){
    freopen("trener.in","r",stdin);
    freopen("trener.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=k;i++)f[i]=1,in[i]=1;
    for(int i=1;i<=k;i++)add(i,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++){
            cin>>s;
            Hash[i][j][2]=HASH(s);
            if(i==1){
                Hash[i][j][0]=base*(ull)(s[0]-'a'+1);
                Hash[i][j][1]=base*(ull)(s[0]-'a'+1);
                continue;
            }
            char c=s.front();
            s.erase(s.begin());
            Hash[i][j][0]=HASH(s);
            s.insert(s.begin(),c);
            s.pop_back();
            Hash[i][j][1]=HASH(s);
        }
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            if(!in[j+(i-1)*k])continue;
            for(int p=1;p<=k;p++)
                if(check(i,j,i+1,p)){
                    add(p+i*k,j+(i-1)*k);
                    in[p+i*k]=1;
                }
        }
    }
//  for(int i=0;i<=n*k;i++){
//      for(int j:edge[i])
//          cout<<i<<" "<<j<<'\n';
//  }
    int ans=0;
    for(int i=k*n;i>k*(n-1);i--)ans+=dfs(i),ans%=MOD;
    cout<<ans;
    return 0;
}