[SDOI2007]游戏

哈希 字符串 最长路

---

题面

题意简单，但不太好概括。
戳我

解析

不成熟想法

据题意可知，字符串字符的顺序无影响。
并且判断两个字符串能否接龙可以通过字符串哈希$O(1)$判断。
然后作为一个不会最长路算法的***，我自动进入了***流程。

• 把所有字符串按长度排序
• 按顺序一一判断长度相差为$1$的字符串是否可以形成接龙关系，并建边
• 注意到全图不一定联通且有环
• 全图建正边跑$SPFA$（以下边权均为负）
• 找出全图$dis$值最大的点，建反边继续跑$SPFA$
• 输出最长路长度，建正边回溯最长路输出方案

接着因为$n$这么统计会多$1$,于是发生了代码$3k$、能过样例却爆$0$的惨案。。。

 while(scanf("%s",a[++n].s+1)!=EOF) a[n].len=strlen(a[n].s+1);

改完后有$40pts$。
代码太长太丑，就别看了

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=3e4+100;
int n,p[30],tot,cnt,h[N],in[N],dis[N],sta[N],top,tp;
bool vis[N];
struct Edge{int to,nxt;}e[N*100];
struct dat
{
  int len;ll Hash;char s[111];
  bool operator < (const dat &o) const {return len<o.len;}
}a[N];
struct node
{
  int u,dis;
  bool operator < (const node &o) const {return dis>o.dis;}
};
struct ysn{int u,v;}b[N*100];
priority_queue<node>Q;
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il void Pre()
{
  memset(h,-1,sizeof(h));
  fp(i,41,1000)
    {
      re int flag=1;
      fp(j,2,sqrt(i))
        if(i%j==0) {flag=0;break;}
      if(flag) p[++tot]=i;
      if(tot>26) break;
    }
  while(scanf("%s",a[++n].s+1)!=EOF) a[n].len=strlen(a[n].s+1);--n;
}
il void SPFA(re int st)
{
  dis[st]=-1;vis[st]=1;Q.push((node){st,0});
  while(!Q.empty())
    {
      re int u=Q.top().u;Q.pop();
      for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(dis[v]>dis[u]-1)
        {
          dis[v]=dis[u]-1;
          if(!vis[v]) vis[v]=1,Q.push((node){v,dis[v]});
        }
    }
      vis[u]=0;
    }
}
il void dfs(re int u)
{
  sta[++tp]=u;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(dis[v]==dis[u]+1)
    dfs(v);
    }
}
int main()
{
  //freopen("2.in","r",stdin);
  Pre();
  fp(i,1,n)
    {
      a[i].Hash=1;
      fp(j,1,a[i].len)
    a[i].Hash*=(a[i].s[j]*p[a[i].s[j]-96]);
    }
  sort(a+1,a+1+n);
  /*fp(i,1,n)
    {
      fp(j,1,a[i].len) putchar(a[i].s[j]);
      printf(" %d %lld %d\n",a[i].len,a[i].Hash,i);
      }*/
  re int l=1,r1,r2;
  while(l<=n)
    {
      r1=r2=l;
      while(a[r1].len==a[l].len&&r1<=n) ++r1;
      r2=r1;r1--;
      while(a[r2].len==a[l].len+1&&r2<=n) ++r2;--r2;
      //printf("%d %d %d\n",l,r1,r2);
      fp(i,l,r1)
    fp(j,r1+1,r2)
    fp(k,1,26)
    if(a[i].Hash*(k+96)*p[k]==a[j].Hash) add(i,j),in[i]++,in[j]++,b[++top]=(ysn){i,j};//printf("%d %d\n",i,j);
      l=r1+1;
    }
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  fp(i,1,n) if(dis[i]==1e9&&in[i]) SPFA(i);
  re int ans=0;
  //fp(i,1,n) printf("%d ",-dis[i]);puts("");
  fp(i,1,n) if(-dis[ans]<-dis[i]) ans=i;
  memset(h,-1,sizeof(h));cnt=0;
  fp(i,1,top) add(b[i].v,b[i].u);
  fp(i,1,n) dis[i]=1e9,vis[i]=0;
  SPFA(ans);re int pos;
  ans=0;
  fp(i,1,n) if(ans<-dis[i]) ans=-dis[i],pos=i;
  memset(h,-1,sizeof(h));cnt=0;
  fp(i,1,top) add(b[i].u,b[i].v);
  dfs(pos);
  printf("%d\n",ans);
  fp(i,1,tp)
    {
      fp(j,1,a[sta[i]].len) putchar(a[sta[i]].s[j]);
      puts("");
    }
  return 0;
}

建边判断

• 把所有字符串按长度排序
• 按顺序一一判断长度相差为$1$的字符串是否可以形成接龙关系，并建边

最坏复杂度可以达到$O(n^2)$
。。。
脑子短路了，直接在每个字符串枚举加$26$字符，看形成的字符串是否存在不就成了吗？
复杂度降为$O(26n)$

最长路算法

对于求最长路，我一开始的思路是建负边跑$SPFA$。这种思路固然正确，但不适用于图不联通（或有负环）的情况。
在图无环（由题目性质决定）时，可用拓扑排序来求最长路：

• 找出无入度的点入栈
• 修改$dis$距离值，删去其出度边
• 若有点因此入度减少为$0$,入栈

此题要输出方案，用$pr$数组记一下前驱（随便哪次修改的前驱都可以）即可。

$Hash$策略的修改

我一开始的$Hash$策略是（$s$为当前枚举到的字符串，$p$为自己选的$26$个不同素数）

$$Hash=\prod_{i=1}^{len}(s[i]*p[s[i]-96])$$
发现这样很容易重复（因为字符串可以很长，乘的结果很大，取模后冲突概率大）。
观察发现字符串之间每个字符的出现次数出现不同的概率大得多。
于是策略改为($tong[i]$为第$i$个小写字母在该字符串中的出现次数）
$$Hash=\prod_{i=1}^{26}(tong[i]+i+Base)$$
判重用$unordered\_map$又准又快。

// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<tr1/unordered_map>
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=3e4+100;
int n,cnt,h[N],in[N],dis[N],ans,pos,pr[N],sta[N],tp;
std::tr1::unordered_map<ll,int>vis;
queue<int>Q;
struct Edge{int to,nxt;}e[N*500];
struct dat
{
    int len,tong[27];ll Hash;char s[111];
}a[N];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;++in[v];}
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Pre()
{
  memset(h,-1,sizeof(h));
  while(scanf("%s",a[++n].s+1)!=EOF) a[n].len=strlen(a[n].s+1);--n;
}
il ll mHash(re int *tong)
{
    re ll sum=1;
    fp(i,1,26) sum*=(233+i+tong[i]);
    return sum;
}
int main()
{
  //freopen("1.in","r",stdin);
  Pre();
  fp(i,1,n)
    {
      a[i].Hash=1;
      fp(j,1,a[i].len) ++a[i].tong[a[i].s[j]-96];
      a[i].Hash=mHash(a[i].tong);
      vis[a[i].Hash]=i;
    //printf("%d %llu\n",i,a[i].Hash);
    }
  fp(i,1,n)
    fp(j,1,26)
    {
        ++a[i].tong[j];
        re int now=vis[mHash(a[i].tong)];
      if(now) add(i,now);//printf("!!!%d %d\n",i,now);
      --a[i].tong[j];
    }
  fp(i,1,n) if(!in[i]) Q.push(i),dis[i]=1;
  while(!Q.empty())
  {
    re int u=Q.front();Q.pop();
    for(re int i=h[u];i+1;i=e[i].nxt)
    {
        re int v=e[i].to;
        dis[v]=dis[u]+1;pr[v]=u;
        if(!(--in[v])) Q.push(v);
    }
  }
  fp(i,1,n) if(dis[i]>ans) ans=dis[pos=i];
  while(pos) sta[++tp]=pos,pos=pr[pos];
  printf("%d\n",ans);
  fq(i,tp,1)
  {
      fp(j,1,a[sta[i]].len) putchar(a[sta[i]].s[j]);puts("");
  }
  return 0;
}