USACO DEC17,Platinum

admin管理员组

文章数量:1122855

USACO DEC17,Platinum

        第一次打usaco，感觉题目还挺有趣的。（为啥感觉美国人的英语比日、俄的英语还要难读呢）

Standinfg Out from the Herd.

        题意：给n个字符串，对每个字符串求有多少本质不同的子串只在这个字符串中出现。

        这题我直接求了一个广义后缀自动机，然后给每个点一个标记表示这个点对应的子串是否只在某个字符串中出现。然后随便统计一下就做完了。O(N)。

AC代码如下：

#include<bits/stdc++.h>
#define N 200009
using namespace std;int n; long long ans[N]; char s[N];
struct sam{int tot,fst[N],nxt[N],ch[N][26],fa[N],len[N],f[N];sam(){ tot=1; }void calc(int x,int y){ f[x]=(f[x] && f[x]!=y?-1:y); }int add(int k,int c,int p){int np=++tot; calc(np,k); len[np]=len[p]+1;for (; p && !ch[p][c]; p=fa[p]) ch[p][c]=np;if (!p){fa[np]=1; return np;}int q=ch[p][c];//cerr<<"	"<<k<<' '<<c<<' '<<p<<' '<<q<<' '<<len[p]<<' '<<len[q]<<endl;if (len[q]==len[p]+1) fa[np]=q; else{int nq=++tot; len[nq]=len[p]+1;//cerr<<nq<<endl;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q]; fa[q]=fa[np]=nq;//cerr<<q<<' '<<np<<endl;for (; p && ch[p][c]==q; p=fa[p]) ch[p][c]=nq;}return np;}void dfs(int x){int y;for (y=fst[

本文标签： USACO DEC17Platinum