題面

傳送門

題解

我們把字符的出現次數哈希起來，然后把每個點向能在它之后的點連邊。那么這顯然是一個\(DAG\)，直接求最長路就行了

//minamoto #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(char *s){R int len=0;R char ch;while(((ch=getc())>'z'||ch<'a'))if(ch==EOF)return EOF;for(s[++len]=ch;(ch=getc())>='a'&&ch<='z';s[++len]=ch);return s[len+1]='\0',len; } char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(char *s){if(C>(1<<20))Ot();for(R int i=1;s[i];++i)sr[++C]=s[i];sr[++C]='\n'; } const int N=10005,P=1e7,Base=233; struct eg{int v,nx;}e[N<<1];int head[N],deg[N],tot; inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot,++deg[v];} char s[N][105];int q[N],len[N],ch[N][26],p[P],st[N],dis[N],Pre[N]; int n,m,ans,pos,t,h,u,top; inline int get(int *s){int res=0;fp(i,0,25)res=(233ll*res+s[i])%P;return res; } int main(){ // freopen("testdata.in","r",stdin);while(~(++n,len[n]=read(s[n])));--n;fp(i,1,n){fp(j,1,len[i])++ch[i][s[i][j]-'a'];p[get(ch[i])]=i;}fp(i,1,n)for(R int j=0,v;j<26;++j){++ch[i][j];p[v=get(ch[i])]?(add(i,p[v]),0):0;--ch[i][j];}h=1,t=0;fp(i,1,n)!deg[i]?q[++t]=i,dis[i]=1:0;while(h<=t){u=q[h++];go(u)(dis[v]=dis[u]+1,Pre[v]=u,!--deg[v])?q[++t]=v:0;}fp(i,1,n)dis[i]>ans?ans=dis[pos=i]:0;while(pos)st[++top]=pos,pos=Pre[pos];printf("%d\n",ans);fd(i,top,1)print(s[st[i]]);return Ot(),0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10554934.html

總結

以上是生活随笔為你收集整理的洛谷P2462 [SDOI2007]游戏（哈希+最长路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。