[关闭]
@ysner 2018-06-16T17:37:32.000000Z 字数 4748 阅读 1610

[SDOI2007]游戏

哈希 字符串 最长路


题面

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

解析

不成熟想法

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

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

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

改完后有
代码太长太丑,就别看了

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll unsigned long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=3e4+100;
  15. int n,p[30],tot,cnt,h[N],in[N],dis[N],sta[N],top,tp;
  16. bool vis[N];
  17. struct Edge{int to,nxt;}e[N*100];
  18. struct dat
  19. {
  20. int len;ll Hash;char s[111];
  21. bool operator < (const dat &o) const {return len<o.len;}
  22. }a[N];
  23. struct node
  24. {
  25. int u,dis;
  26. bool operator < (const node &o) const {return dis>o.dis;}
  27. };
  28. struct ysn{int u,v;}b[N*100];
  29. priority_queue<node>Q;
  30. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  31. il void wri(re int x)
  32. {
  33. if(x<0) putchar('-'),x=-x;
  34. if(x>9) wri(x/10);
  35. putchar(x%10+'0');
  36. }
  37. il void Pre()
  38. {
  39. memset(h,-1,sizeof(h));
  40. fp(i,41,1000)
  41. {
  42. re int flag=1;
  43. fp(j,2,sqrt(i))
  44. if(i%j==0) {flag=0;break;}
  45. if(flag) p[++tot]=i;
  46. if(tot>26) break;
  47. }
  48. while(scanf("%s",a[++n].s+1)!=EOF) a[n].len=strlen(a[n].s+1);--n;
  49. }
  50. il void SPFA(re int st)
  51. {
  52. dis[st]=-1;vis[st]=1;Q.push((node){st,0});
  53. while(!Q.empty())
  54. {
  55. re int u=Q.top().u;Q.pop();
  56. for(re int i=h[u];i+1;i=e[i].nxt)
  57. {
  58. re int v=e[i].to;
  59. if(dis[v]>dis[u]-1)
  60. {
  61. dis[v]=dis[u]-1;
  62. if(!vis[v]) vis[v]=1,Q.push((node){v,dis[v]});
  63. }
  64. }
  65. vis[u]=0;
  66. }
  67. }
  68. il void dfs(re int u)
  69. {
  70. sta[++tp]=u;
  71. for(re int i=h[u];i+1;i=e[i].nxt)
  72. {
  73. re int v=e[i].to;
  74. if(dis[v]==dis[u]+1)
  75. dfs(v);
  76. }
  77. }
  78. int main()
  79. {
  80. //freopen("2.in","r",stdin);
  81. Pre();
  82. fp(i,1,n)
  83. {
  84. a[i].Hash=1;
  85. fp(j,1,a[i].len)
  86. a[i].Hash*=(a[i].s[j]*p[a[i].s[j]-96]);
  87. }
  88. sort(a+1,a+1+n);
  89. /*fp(i,1,n)
  90. {
  91. fp(j,1,a[i].len) putchar(a[i].s[j]);
  92. printf(" %d %lld %d\n",a[i].len,a[i].Hash,i);
  93. }*/
  94. re int l=1,r1,r2;
  95. while(l<=n)
  96. {
  97. r1=r2=l;
  98. while(a[r1].len==a[l].len&&r1<=n) ++r1;
  99. r2=r1;r1--;
  100. while(a[r2].len==a[l].len+1&&r2<=n) ++r2;--r2;
  101. //printf("%d %d %d\n",l,r1,r2);
  102. fp(i,l,r1)
  103. fp(j,r1+1,r2)
  104. fp(k,1,26)
  105. 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);
  106. l=r1+1;
  107. }
  108. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  109. fp(i,1,n) if(dis[i]==1e9&&in[i]) SPFA(i);
  110. re int ans=0;
  111. //fp(i,1,n) printf("%d ",-dis[i]);puts("");
  112. fp(i,1,n) if(-dis[ans]<-dis[i]) ans=i;
  113. memset(h,-1,sizeof(h));cnt=0;
  114. fp(i,1,top) add(b[i].v,b[i].u);
  115. fp(i,1,n) dis[i]=1e9,vis[i]=0;
  116. SPFA(ans);re int pos;
  117. ans=0;
  118. fp(i,1,n) if(ans<-dis[i]) ans=-dis[i],pos=i;
  119. memset(h,-1,sizeof(h));cnt=0;
  120. fp(i,1,top) add(b[i].u,b[i].v);
  121. dfs(pos);
  122. printf("%d\n",ans);
  123. fp(i,1,tp)
  124. {
  125. fp(j,1,a[sta[i]].len) putchar(a[sta[i]].s[j]);
  126. puts("");
  127. }
  128. return 0;
  129. }

建边判断

最坏复杂度可以达到
。。。
脑子短路了,直接在每个字符串枚举加字符,看形成的字符串是否存在不就成了吗?
复杂度降为

最长路算法

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

此题要输出方案,用数组记一下前驱(随便哪次修改的前驱都可以)即可。

策略的修改

我一开始的策略是(为当前枚举到的字符串,为自己选的个不同素数)


发现这样很容易重复(因为字符串可以很长,乘的结果很大,取模后冲突概率大)。
观察发现字符串之间每个字符的出现次数出现不同的概率大得多。
于是策略改为(为第个小写字母在该字符串中的出现次数)

判重用又准又快。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #include<queue>
  9. #include<tr1/unordered_map>
  10. #define ll unsigned long long
  11. #define re register
  12. #define il inline
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int N=3e4+100;
  17. int n,cnt,h[N],in[N],dis[N],ans,pos,pr[N],sta[N],tp;
  18. std::tr1::unordered_map<ll,int>vis;
  19. queue<int>Q;
  20. struct Edge{int to,nxt;}e[N*500];
  21. struct dat
  22. {
  23. int len,tong[27];ll Hash;char s[111];
  24. }a[N];
  25. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;++in[v];}
  26. il ll gi()
  27. {
  28. re ll x=0,t=1;
  29. re char ch=getchar();
  30. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  31. if(ch=='-') t=-1,ch=getchar();
  32. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  33. return x*t;
  34. }
  35. il void Pre()
  36. {
  37. memset(h,-1,sizeof(h));
  38. while(scanf("%s",a[++n].s+1)!=EOF) a[n].len=strlen(a[n].s+1);--n;
  39. }
  40. il ll mHash(re int *tong)
  41. {
  42. re ll sum=1;
  43. fp(i,1,26) sum*=(233+i+tong[i]);
  44. return sum;
  45. }
  46. int main()
  47. {
  48. //freopen("1.in","r",stdin);
  49. Pre();
  50. fp(i,1,n)
  51. {
  52. a[i].Hash=1;
  53. fp(j,1,a[i].len) ++a[i].tong[a[i].s[j]-96];
  54. a[i].Hash=mHash(a[i].tong);
  55. vis[a[i].Hash]=i;
  56. //printf("%d %llu\n",i,a[i].Hash);
  57. }
  58. fp(i,1,n)
  59. fp(j,1,26)
  60. {
  61. ++a[i].tong[j];
  62. re int now=vis[mHash(a[i].tong)];
  63. if(now) add(i,now);//printf("!!!%d %d\n",i,now);
  64. --a[i].tong[j];
  65. }
  66. fp(i,1,n) if(!in[i]) Q.push(i),dis[i]=1;
  67. while(!Q.empty())
  68. {
  69. re int u=Q.front();Q.pop();
  70. for(re int i=h[u];i+1;i=e[i].nxt)
  71. {
  72. re int v=e[i].to;
  73. dis[v]=dis[u]+1;pr[v]=u;
  74. if(!(--in[v])) Q.push(v);
  75. }
  76. }
  77. fp(i,1,n) if(dis[i]>ans) ans=dis[pos=i];
  78. while(pos) sta[++tp]=pos,pos=pr[pos];
  79. printf("%d\n",ans);
  80. fq(i,tp,1)
  81. {
  82. fp(j,1,a[sta[i]].len) putchar(a[sta[i]].s[j]);puts("");
  83. }
  84. return 0;
  85. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注