题解 P2462 【[SDOI2007]游戏】

· · 题解

题意:接龙,对于一个串i,如果串j所有中字符的出现次数比i有且只有一个位置大1,那么就能接上

算法一:暴力DP

因为每次长度都会多1

所以考虑按照长度DP

输出方案就记录一下转移点 复杂度$O(26*\sum_{len}sum_{len}*sum_{len-1}) 可以知道极限复杂度是$O(26*\frac{n^2}4)

不知道这种DP能不能优化

由于是暴力,所以代码就随便写了一下

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char sr[1<<21];int C=-1;
const int N=1e4+5,M=105,inf=1e9;
typedef int arr[N];
struct da{int l,c[26];}a[N];
int n,m,k,ans,pos,L=inf,R;arr pr,f;
char s[N][M];vector<int>len[M];
inline bool cmp(const da&a,const da&b){return a.l<b.l;}
void dfs(int u){
    if(!u)return;
    dfs(pr[u]);
    puts(s[u]+1);
}
inline bool chk(int u,int v){
    int p=0;
    fp(i,0,25){
        if(a[u].c[i]==a[v].c[i])continue;
        if(a[u].c[i]<a[v].c[i])return 0;
        if(a[u].c[i]>a[v].c[i]+1)return 0;
        p^=1;
    }return p;
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    while(~scanf("%s",s[++n]+1)){
        a[n].l=strlen(s[n]+1);
        fp(i,1,a[n].l)++a[n].c[s[n][i]-'a'];
    }--n;
    fp(i,1,n)len[a[i].l].push_back(i),cmin(L,a[i].l),cmax(R,a[i].l);
    fp(l,L,R){
        for(int i:len[l])f[i]=1;
        if(!len[l-1].size())continue;
        for(int i:len[l]){
            for(int j:len[l-1]){
                if(chk(i,j)){
                    if(f[i]<f[j]+1)
                        f[i]=f[j]+1,pr[i]=j;
                }
            }
            if(f[i]>ans)ans=f[i],pos=i;
        }
    }
    printf("%d\n",ans);
    dfs(pos);
return 0;
}

算法二:字符串hash+DAG最长路

对于每个字符串,你增加他的某一个字符,看看得到的新字符串是不是存在

存在就连边,得到的一定是一个DAG,然后跑最长路就好了

至于怎么判断是不是存在,你把cnt[26]这个数组hash一下就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char sr[1<<21];int C=-1;
const int N=1e4+5,M=1e7;
typedef int arr[N];
struct eg{int nx,to;}e[N];
struct da{int l,c[26];}a[N];
int n,m,ce,ans,pos,ha[M];arr pr,f,fi,in,S,d;
char s[N][105];queue<int>q;
inline void add(int u,int v){e[++ce]={fi[u],v},fi[u]=ce,++in[v];}
inline int get(int*s){
    int tp=0;
    fp(i,0,25)tp=(233ll*tp%M+s[i])%M;
    return tp;
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    while(~scanf("%s",s[++n]+1));--n;
    fp(i,1,n){
        a[i].l=strlen(s[i]+1);
        fp(j,1,a[i].l)++a[i].c[s[i][j]-'a'];
        ha[get(a[i].c)]=i;
    }
    fp(i,1,n){
        fp(j,0,25){
            ++a[i].c[j];
            int v=get(a[i].c);
            if(ha[v])add(i,ha[v]);
            --a[i].c[j];
        }
    }
    fp(i,1,n)if(!in[i])q.push(i),d[i]=1;
    while(!q.empty()){int u=q.front();q.pop();go(u)d[v]=d[u]+1,--in[v],pr[v]=u,!in[v]?q.push(v):void();}
    fp(i,1,n)if(d[i]>ans)ans=d[pos=i];
    while(pos)S[++S[0]]=pos,pos=pr[pos];
    printf("%d\n",ans);
    fd(i,S[0],1)puts(s[S[i]]+1);
return 0;
}

算法三:虚树

我不知道是哪位大佬的在这题贴了虚树

求大佬指教