USACO填坑计划
maya终于有填坑计划了
主要是最近不知道做什么题好
看到*利去年同期的刷题节奏感觉很带感的样子于是跟着进度做一做好了。虽然那种效率肯定是跟不上的
话说Silver的题好像确实都不是很难的样子反正按记录一路扫过去好了
[upd 9.11] 差不多都搞完了，刷水真是刷的人好虚。里面有的比较卡的题目要不就是比较神的贪心要不就是复杂度不科学但还是能过的题。
BZOJ1613 直接DP
BZOJ1622 我反正是乱搞，先建出一棵trie数然后每次维护一些还可以往下扩展的节点。但是复杂度算起来并不很科学，不过还是过了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 3050
#define M 105
queue <int> a[N],empty;
int n,m,s[N],ne[N][M],li[N],ans,len,st=1,sg[N];
char b[N],qu[N][N];
int main()
{
cin >>n>>m;
for (int i=1;i<=n;i++)
scanf("%s",qu[i]);
for (int i=1;i<=m;i++)
{
scanf("%s",b);len=strlen(b);
for (int j=0;j<len;j++)
if (b[j]<'a') b[j]=b[j]-'A'+'a';
int now=1;
for (int j=0;j<len;j++)
if (!ne[now][b[j]-'a'])
ne[now][b[j]-'a']=++st,now=st;else
now=ne[now][b[j]-'a'];
s[now]++;
}
for (int i=1;i<=n;i++)
{
len=strlen(qu[i]);ans=0;
for (int j=0;j<len;j++)
if (qu[i][j]<'a') qu[i][j]=qu[i][j]-'A'+'a';
for (int j=0;j<26;j++)
{
a[j]=empty;
if (ne[1][j]) a[j].push(1);
}
for (int j=0;j<len;j++)
{
int k=qu[i][j]-'a',ss=0;
while (a[k].size())
li[++ss]=a[k].front(),a[k].pop();
while (ss--)
{
int l=ne[li[ss+1]][k];
for (int q=0;q<26;q++)
if (ne[l][q])
a[q].push(l);
ans+=s[l];
}
}
printf("%d\n",ans);
}
return 0;
}
BZOJ1623 一个比较显然的贪心
BZOJ1628 用个set维护下现在还存在的矩形的高度然后从左往右扫一遍就好了
BZOJ1633 也是DP
BZOJ1634 按照Di/Ti排个序就是顺序，至于证明可以考虑交换两个相邻的牛的顺序对答案的影响
BZOJ1635 Get差分序列，感觉神神的，贪心也神神的。
BZOJ1636 直接倍增搞
BZOJ1637 值化成1和-1前缀和一下然后排个序求出同一前缀和的最大区间最后倍增统计答案
BZOJ1638 两次拓扑排序
BZOJ1639 二分答案
BZOJ1640 贪心，两端不同就取小的，否则往中间一直找不同的。这样可以搞成O(n)的。有人用后缀数组真是不明觉厉，不过本质还是一样的。
BZOJ1641 Floyd
BZOJ1642 排序扫一遍
BZOJ1643 DP
BZOJ1644 BFS
BZOJ1645 刚看题还以为是扫描线，结果sort一遍扫一遍就好了
BZOJ1646 BFS
BZOJ1648 BFS
BZOJ1649 背包
BZOJ1650 二分答案+贪心
BZOJ1651 二分答案
BZOJ1652 DP
BZOJ1653 爆搜
BZOJ1654 Tarjan求LCC
BZOJ1655 高J度+DP
BZOJ1657 单调队列
BZOJ1658 贪心+差分序列
就是方向向左的路线记为1，否则记为-1，然后每段区间的权值和的绝对值*路线长度的和就是答案，脑补感觉还是比较正确
BZOJ1660 单调队列
BZOJ1661 爆搜
BZOJ1662 数位DP
BZOJ1663 DP
BZOJ1664 排序乱搞
BZOJ1665 暴力建图BFS
BZOJ1666 高J度
BZOJ1668 DP
BZOJ1669 n^2 LIS都可以过
BZOJ1671 BFS
BZOJ1672 排序后贪心
BZOJ1673 因为个数不会太多所以直接爆搜
BZOJ1674 直接建图BFS
BZOJ1676 直接爆搞
BZOJ1677 DP
BZOJ1679 排序乱搞
BZOJ1680 贪心
BZOJ1681 最短路
BZOJ1682 最小生成树
BZOJ1683 同1628
BZOJ1684 枚举分母，则分子是可以限制在一定范围内的
BZOJ1685 有个神神的贪心是每次先把大的尽可能拿掉，最后补个最小的
BZOJ1688 并查集
BZOJ1689 贪心
BZOJ2014 贪心
BZOJ2015 SPFA
BZOJ2016 二分答案
BZOJ2019 SPFA
BZOJ2020 贪心
BZOJ2021 背包
BZOJ2023 DP
BZOJ2101 DP
BZOJ2102 爆搜
BZOJ3016 往前往后扫一遍
BZOJ3017 DP
BZOJ3018 跑n^2次SPFA
BZOJ3296 并查集
BZOJ3297 DP
BZOJ3298 打表找规律发现每条y=x+k总会有一个后手必胜点，然后就可以先把这些点预处理出来最后判断就好了
BZOJ3300 栈
BZOJ3301 DP
BZOJ3389 贪心
BZOJ3390 最小生成树
BZOJ3391 树的重心
BZOJ3392 BFS
BZOJ3396 Dinic
BZOJ3399 贪心
BZOJ3400 DP
BZOJ3402 BFS
BZOJ3403 队列
BZOJ3404 预处理
BZOJ3410 贪心
BZOJ3432 二分答案
BZOJ3433 好神的贪心，是每次看能不能填右端点大的，不能就填右端点较小的。
BZOJ3479 最小生成树
BZOJ3480 预处理背包一下求出每个大小的最小值，直接从左往右扫一遍就好了
BZOJ3538 三次SPFA
BZOJ3540 前缀和+归并排序
WC2013 糖果公园
早有耳闻的sxbk题
一直以为带修改树上莫队一定有着很高的技巧
于是去膜了一发题解
才发现这道题主要是在排序上面加特技
考虑将询问分块，然后与普通莫队不同的地方是我们将询问按照左端点的块编号、右端点的块编号、在第几次修改之后三个关键字排序。
这样在n^(2/3)个块区间里面的修改因为时间有序了所以是O(n)的。然后询问的话反正区间内的修改是n^(2/3)的，区间开头的询问也可以暴力O(n)搞。
所以时间的操作是O(n^(5/3))的，而其他树上莫队的部分也是O(n^(5/3))
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 400050
#define ll long long
#define eps 1e-5
int c[N*2][2],fi[N],fa[N],sg[N][2],rt,n,m,Sign[M],t[M];
int li[N],cl[N],mo[N][3],qu[N][2],ss,st,p,cnt[N];
int now,nt[M];ll ans[N],Ans,tot[N];
struct Color
{
ll wi[N],v[N],s[N];
inline void Insert(int x)
{Ans+=wi[++s[x]]*v[x];}
inline void Delete(int x)
{Ans-=wi[s[x]--]*v[x];}
} Aha;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
nt[sg[x][0]=++st]=x;tot[x]=2;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
{
if (nt[st]!=x) nt[++st]=x,tot[x]++;
fa[c[i][0]]=x,DFS(c[i][0]);
}
nt[sg[x][1]=++st]=x;
}
inline bool cmp(int x,int y)
{return Sign[qu[x][0]]<Sign[qu[y][0]]||
(Sign[qu[x][0]]==Sign[qu[y][0]]&&(Sign[qu[x][1]]<
Sign[qu[y][1]]||(Sign[qu[x][1]]==Sign[qu[y][1]]&&
t[x]<t[y])));}
void Pretreat()
{
DFS(1);
rt=pow(st,2.0/3.0)+eps;
for (int i=1;i<=st;i++) Sign[i]=(i-1)/rt;
for (int i=1;i<=p;i++)
{
if (sg[qu[i][1]][0]<sg[qu[i][0]][0])
swap(qu[i][1],qu[i][0]);
qu[i][0]=sg[qu[i][0]][sg[qu[i][0]][1]<sg[qu[i][1]][1]];
qu[li[i]=i][1]=sg[qu[i][1]][0];
}
for (int i=1;i<=now;i++)
mo[i][1]=cl[mo[i][0]],cl[mo[i][0]]=mo[i][2];
for (int i=now;i>=1;i--)
cl[mo[i][0]]=mo[i][1];
sort(li+1,li+p+1,cmp);
}
inline void Move(int x,int y)
{
bool r=(cnt[mo[x][0]]<tot[mo[x][0]])
&&(cnt[mo[x][0]]>0);
if (r) Aha.Delete(mo[x][y]);
cl[mo[x][0]]=mo[x][3-y];
if (r) Aha.Insert(mo[x][3-y]);
}
inline void Modify(int x,int y)
{
cnt[x]+=y;
if (!cnt[x]||cnt[x]==tot[x]) Aha.Delete(cl[x]); else
if (cnt[x]-y==0||cnt[x]-y==tot[x]) Aha.Insert(cl[x]);
}
void Solve()
{
int le=1,ri=0;now=0;
for (int i=1;i<=p;i++)
{
int k=qu[li[i]][0],l=qu[li[i]][1];
for (;le<k;le++) Modify(nt[le],-1);
for (;le>k;) Modify(nt[--le],1);
for (;ri>l;ri--) Modify(nt[ri],-1);
for (;ri<l;) Modify(nt[++ri],1);
for (;now<t[li[i]];) Move(++now,1);
for (;now>t[li[i]];) Move(now--,2);
ans[li[i]]=Ans;
}
return;
}
int main()
{
n=Read();m=Read();p=Read();
for (int i=1;i<=m;i++) Aha.v[i]=Read();
for (int i=1;i<=n;i++) Aha.wi[i]=Read();
for (int i=1;i<n;i++)
Line(Read(),Read());
for (int i=1;i<=n;i++) cl[i]=Read();
int o=p;p=0;
while (o--)
if (Read())
qu[++p][0]=Read(),qu[p][1]=Read(),t[p]=now;else
mo[++now][0]=Read(),mo[now][2]=Read();
Pretreat();
Solve();
for (int i=1;i<=p;i++)
printf("%lld\n",ans[i]);
return 0;
}
SPOJ QTREE5
话说这博客我自己都有的时候上不去不知道是smg
题面：给n（n<=10w）个点，一开始全部都是黑色的，有（好像是）10w个操作，每次改变一个节点的颜色（黑白转换）或者询问一个点与其最近白点的距离（如果没有就是-1）
这题比QTREE4（BZOJ 1095）好写到不知道哪里去了，反正我是用了树链剖分
就是每个节点把其所有轻儿子的子树的节点的白点距离用set存起来，每次变颜色就只会改变log n个，然后弄两棵线段树存下一条重链上所有点set的顶部的值+其到链首/链尾的距离，所以也可以直接查询。
动态树分治的思路跟QTREE4差不多，只不过查询那个点到重心的距离+重心的其它子树的最小值的和的最小值，反正也是用几个set搞一下什么的，但是感觉麻烦些。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
multiset <int> a[N];
set <int> :: iterator it;
int fa[N],c[N*2][2],fi[N],sg[N],st=0,ss=1,n,m;
int h[N][3],rf[N],dep[N],tot,sum[N];bool b[N];
struct Segment_Tree
{
int a[N*3];
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
a[z]=INF;
if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
}
void Ins(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {a[z]=p;return;}
if (o<=i) Ins(x,i,j,o,p);else
Ins(i+1,y,j+1,o,p);
a[z]=min(a[j],a[j+1]);
}
int Que(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1,k=INF;
if (x==o&&y==p) return a[z];
if (o<=i) k=Que(x,i,j,o,min(p,i));
if (p>i) k=min(k,Que(i+1,y,j+1,max(o,i+1),p));
return k;
}
void Insert(int x,int y)
{Ins(1,n,1,x,y);}
int Query(int x,int y)
{return Que(1,n,1,x,y);}
} mi[2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x][0]=h[fa[x]][0]+1;sum[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),sum[x]+=sum[c[i][0]];
return;
}
int DSF(int x,int y)
{
int k=0;sg[x]=++st;
rf[x]=y;h[x][1]=h[x][0]-h[y][0];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&sum[c[i][0]]>sum[k])
k=c[i][0];
dep[x]=!k?x:DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
h[x][2]=h[dep[x]][0]-h[x][0];
return dep[x];
}
void Insert(int x)
{
int s=0;
while (x)
{
it=a[x].begin();
int k=it==a[x].end()?INF:*it;
a[x].insert(s);
if (s<k)
mi[0].Insert(sg[x],s+h[x][1]),
mi[1].Insert(sg[x],s+h[x][2]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
}
void Delete(int x)
{
int s=0;
while (x)
{
it=a[x].begin();int k=*it;
it=a[x].lower_bound(s);a[x].erase(it);
it=a[x].begin();int l=it==a[x].end()?INF:*it;
if (k!=l)
mi[0].Insert(sg[x],l==INF?INF:l+h[x][1]),
mi[1].Insert(sg[x],l==INF?INF:l+h[x][2]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
}
int Query(int x)
{
int s=0,ans=INF;
while (x)
{
ans=min(ans,s+mi[0].Query(sg[x],sg[dep[x]])
-h[x][0]+h[rf[x]][0]);
ans=min(ans,s+mi[1].Query(sg[rf[x]],sg[x])
-h[dep[x]][0]+h[x][0]);
s+=h[x][0]-h[fa[rf[x]]][0];x=fa[rf[x]];
}
return ans;
}
int main()
{
n=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);
mi[0].Set_up(1,n,1);mi[1].Set_up(1,n,1);
m=Read();
while (m--)
if (!Read())
{
int k=Read();b[k]=!b[k];
if (!b[k]) Delete(k),tot--;else Insert(k),tot++;
} else
{
int k=Read();
printf("%d\n",tot?Query(k):-1);
}
return 0;
}
BZOJ 1095
这题做的我真是感动
有线段树和动态树分治的做法（话说第一次看到我还以为是动态树的分治【捂脸*ei】），我在考场上面写的是后者，但是当时打错了一个变量，然后爆零了，改完就A了。但是那个题好像数据比较特殊，所以那题代码蒯过来是wa的。于是这种喜闻乐见的东西我重写了一遍，调了一上午，欲仙欲死。
裸题，首先点分治一下，然后用2n个set保存每个分治的重心和它的儿子们的答案，然后对于每次操作就直接添加删除什么的就好了。
当然用优先队列是要比set快一些的。
代码高能
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
struct Set
{
multiset <int> li;
set <int> :: iterator it;
inline int Sum()
{return li.size();}
inline void Ins(int x)
{li.insert(-x);}
inline void Del(int x)
{it=li.lower_bound(-x);li.erase(it);}
inline int Top()
{it=li.begin();return it!=li.end()?-*it:0;}
inline int Sec()
{it=li.begin();return Sum()<2?0:Top()-*(++it);}
} a[N*2];
int h[N][20],s[N],n,m,c[N*2][2],fi[N],tot,la[N];
int ss=1,st=0,li[N],sum[N][2],sub[N][20];
int sg[N],rt[N][20],cnt;bool t[N];char b[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
int BFS(int x)
{
int le=1,ri=1;
li[1]=x;sum[x][1]=++tot;sum[x][0]=la[x]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
sum[c[i][0]][1]=tot,sum[c[i][0]][0]=0,
li[++ri]=c[i][0],la[c[i][0]]=li[le];
for (--le;le;le--)
sum[la[li[le]]][0]+=++sum[li[le]][0];
return ri;
}
void BSF(int x,int y)
{
int le=1,ri=1;
li[1]=x;sum[x][1]=++tot;h[x][y]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&sum[c[i][0]][1]!=tot)
sum[c[i][0]][1]=tot,h[c[i][0]][y]=h[li[le]][y]+1,
li[++ri]=c[i][0];
return;
}
int Find(int x,int y)
{
while (1)
{
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=la[x]&&sum[c[i][0]][1]==tot&&
sum[c[i][0]][0]>y/2)
{x=-c[i][0];break;}
if (x>0) return x;else x=-x;
}
}
void Set_up(int x,int y)
{
int k=BFS(x),root=Find(x,k),le=2;BSF(root,y);
a[sg[root]=sub[root][s[root]=y]=++st].Ins(0);
if (k==1) {a[0].Ins(0);return;}
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]])
a[sub[c[i][0]][y]=++st].Ins(1),
rt[c[i][0]][y]=sg[root];
for (;le<=k;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!s[c[i][0]]&&!sub[c[i][0]][y])
a[sub[c[i][0]][y]=sub[li[le]][y]].
Ins(h[c[i][0]][y]),rt[c[i][0]][y]=sg[root];
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]])
a[sg[root]].Ins(a[sub[c[i][0]][y]].Top());
a[0].Ins(a[sg[root]].Sec());
for (int i=fi[root];i;i=c[i][1])
if (!s[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
void Insert(int x)
{
for (int i=1;i<s[x];i++)
{
int ans=a[sub[x][i]].Top(),Ans,S;
a[sub[x][i]].Ins(h[x][i]);
if (h[x][i]<=ans) continue;
Ans=a[rt[x][i]].Sec();
if (a[sub[x][i]].Sum()>1) a[rt[x][i]].Del(ans);
a[rt[x][i]].Ins(a[sub[x][i]].Top());
S=a[rt[x][i]].Sec();
if (S!=Ans)
a[0].Del(Ans),a[0].Ins(S);
}
a[sg[x]].Ins(0);
if (a[sg[x]].Sum()==2) a[0].Ins(a[sg[x]].Sec());
}
void Delete(int x)
{
for (int i=1;i<s[x];i++)
{
int ans=a[sub[x][i]].Top(),Ans,S;
a[sub[x][i]].Del(h[x][i]);
if (h[x][i]<ans) continue;
Ans=a[rt[x][i]].Sec();
a[rt[x][i]].Del(ans);
if (a[sub[x][i]].Sum())
a[rt[x][i]].Ins(a[sub[x][i]].Top());
S=a[rt[x][i]].Sec();
if (S!=Ans)
a[0].Del(Ans),a[0].Ins(S);
}
int Ans=a[sg[x]].Sec();
a[sg[x]].Del(0);
if (a[sg[x]].Sum()==1) a[0].Del(Ans);
}
int main()
{
n=cnt=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
Set_up(1,1);m=Read();
while (m--)
{
scanf("%s",b);
if (b[0]=='G')
printf("%d\n",cnt<=1?cnt-1:a[0].Top());else
{
int k=Read();
if (t[k]) cnt++,Insert(k);else
cnt--,Delete(k);
t[k]=!t[k];
}
}
return 0;
}
后缀自动机乱做
最近看了SAM课件+论文+博客
基本懂是什么sxbk东西了，有几个主要性质：一个状态所代表的子串互为后缀，并且长度连续；有一个right集合是这个子串出现的位置集合；当前状态的parent状态也是当前状态的子串的后缀，并且其right集合包含了当前状态的right集合；当前状态的最长长度已经处理出来了就是val，而最短长度就是BFS一遍可以得到（maya明明这个就是suf的val+1的所以不用求了）；suf可以建成一棵树；right集合可以O(S)求最大最小值或者元素个数，这些都要先把suf树上的叶子节点也就是所有前缀所代表的状态设个初值然后就可以往上传值，并且两个节点的right集合要不就交集为空要不就一个为另外一个的祖先，而求出这个集合可以用启发式合并。
然后背了下模板，还要学下怎么建后缀数组，准备把cls课件还有论文上面的题目写掉一些。
SPOJ LCS：
求两个子串的最长公共子串
将其中一个的SAM建出来，另外一个在上面跑一遍，同时记录跑完当前字符之后当前的状态以及当前匹配长度，这东西之所以不能直接当成val是因为有可能比val小，于是每往下走的时候就val++，当当前匹配不了时就suf走，然而由性质当前的长度肯定大于suf的长度所以往回走的时候长度又要变成val。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 250050
#define M 26
char b[N];
struct State
{
State *suf,*go[M];int val;
State(): val(0),suf(0)
{memset(go,0,sizeof(go));}
} *root,*last,*cur,statePool[N*2],*now;int ans,t;
void extend(int w)
{
State *p=last,*np=cur++;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p) np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
int main()
{
scanf("%s",b);
cur=statePool;root=last=cur++;
for (char* i=b;*i;i++)
extend(*i-'a');
scanf("%s",b);
t=0;now=root;
for (char* i=b;*i;i++)
if (now->go[*i-'a'])
now=now->go[*i-'a'],ans=max(ans,++t);else
{
while (now&&!now->go[*i-'a']) now=now->suf;
if (now==NULL)
now=root,t=0;else
ans=max(ans,t=now->val+1),now=now->go[*i-'a'];
}
cout <<ans<<endl;
return 0;
}
SPOJ LCS2：
给10个串要求最大匹配大小
当然也是求出第一个串的SAM，然后每个串在上面跑一遍，每跑一遍每个节点记录当前跑出来的最长匹配是多少，并且这个东西可以传给suf的，这样跑10遍，每个点每次跑出的答案要取最小值，所有点的最小值还要取个最大值就是答案。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define M 26
char b[N];
struct State
{
State *par,*go[M],*ne;int val,t[12],ma;
State(): ne(0),par(0)
{memset(go,0,sizeof(go));memset(t,0,sizeof(t));}
} *root,*last,statePool[N],*cur,*fi[N];
int st=0,ans=0,len;
inline State* Line(int x)
{cur->val=x;cur->ne=fi[x];fi[x]=cur;return cur++;}
void extend(int w)
{
State *p=last,*np=Line(p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->par;
if (!p)
np->par=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->par=q;else
{
State *nq=Line(p->val+1);
memcpy(nq->go,q->go,sizeof q->go);
nq->par=q->par;
q->par=np->par=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->par;
}
}
last=np;
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;last=root=Line(0);
for (char *i=b;*i;i++) extend(*i-'a');
while (st++,scanf("%s",b)!=EOF)
{
State* now=root;int s=0;
for (char *i=b;*i;i++)
{
int k=*i-'a';
while (now&&!now->go[k])
now=now->par,s=now?now->val:0;
if (!now)
now=root,s=0;else
now=now->go[k],now->t[st]=max(now->t[st],++s);
}
}
for (int i=len;i>=1;i--)
for (State* j=fi[i];j;j=j->ne)
{
int l=i;
for (int k=1;k<st;k++)
{
l=min(l,j->t[k]);
if (j->par)
j->par->t[k]=max(j->par->t[k],j->t[k]);
}
ans=max(ans,l);
}
cout <<ans<<endl;
return 0;
}
SPOJ SUBLEX：
求一个长为n(n<=9w)串的去重的子串集合中的第k(k∈int)大的串并输出，q(q<=500)组询问
还是建出SAM，然后处理出每个状态的可达子串有多少个，这个东西可以拓扑排序之后算一下就好了。然后将询问排序，从root出发依次处理每个询问，同时枚举当前状态的每个转移计算加上这个转移的子串数后是否超过答案，是则到下一个转移，否则进入这个转移。这题时限还只有0.2s左右，还好不卡int（虽然不知道能不能卡），T了好几发删掉了long long才勉强过，SPOJ卡时卡的sxbk。话说一开始这题没看样例以为没有去重的。这样的话每个状态的所代表的子串个数就是right集大小*（最长子串长度-最短子串长度），这样不加long long能过就sxbk了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 180050
#define M 26
#define fr first
#define sc second
struct State
{State *go[M],*suf,*ne;int val,t,wz;};
State *root,*last,*cur,statePool[N],*fi[N],*Stack[N];
int st,len,m,ans[M*20][2],sta[N];
pair <int,int> qu[M*20];char b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(State* y,ll x)
{y->val=x;y->ne=fi[x];fi[x]=y;}
void extend(int w)
{
State *p=last,*np=cur;Line(cur++,p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur;Line(cur++,(p->val)+1);
memcpy(nq->go, q->go, sizeof q->go);
nq->suf=q->suf;q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Right()
{
State* now=root;int l=0;
for (char *i=b;*i;i++)
{
int k=*i-'a';
if (now->go[k])
now=now->go[k];else
{
while (now&&!now->go[k]) now=now->suf;
if (!now) now=root;else now=now->go[k];
}
now->wz=l++;
}
for (int i=len;i>=1;i--)
for (State* j=fi[i];j;j=j->ne)
j->suf->wz=j->wz,j->t=1;
for (int i=len;i>=0;i--)
for (State* j=fi[i];j;j=j->ne)
for (int k=0;k<M;k++)
if (j->go[k]) j->t+=j->go[k]->t;
}
inline void Update(int x,int y,int z)
{ans[z][1]=x;ans[z][0]=x-y+1;}
void Solve()
{
m=Read();
for (int i=1;i<=m;i++)
qu[i].fr=Read(),qu[i].sc=i;
sort(qu+1,qu+m+1);int ri=1,i=1;ll now=0;
Stack[1]=root;sta[1]=0;
while (i<=m)
{
if (!Stack[ri]->go[sta[ri]])
sta[ri]++;else
if (now+Stack[ri]->go[sta[ri]]->t<qu[i].fr)
now+=Stack[ri]->go[sta[ri]]->t,sta[ri]++;else
if (now+1==qu[i].fr)
Update(Stack[ri]->go[sta[ri]]->wz,ri,qu[i++].sc);else
now++,Stack[ri+1]=Stack[ri]->go[sta[ri]],sta[++ri]=0;
while (ri&&sta[ri]==26) sta[--ri]++;
}
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;st=-1;Line(cur,0);last=root=cur++;
for (char *i=b;*i;i++) extend(*i-'a');
Right();Solve();
for (int i=1;i<=m;i++)
{
for (int j=ans[i][0];j<=ans[i][1];j++)
putchar(b[j]);
printf("\n");
}
return 0;
}
SPOJ NSUBSTR
求字符串中每个长度的相同子串最多有多少，n<=25w
直接求right集合大小，而这个大小是可以更新1~val的ans的，所以对于每个节点直接更新val的ans，最后再从后往前扫一遍用长的ans更新短的ans
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 250050
#define M 26
struct State
{State *suf,*go[M],*ne;int val,ri;};
State *root,*last,*cur,statePool[N*2],*fi[N];
int len,ans[N];char b[N];
inline State* Line(int x)
{cur->ne=fi[x];cur->val=x;fi[x]=cur;return cur++;}
void extend(int w)
{
State *p=last,*np=Line(p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=Line(p->val+1);
memcpy(nq->go,q->go,sizeof q->go);
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Right()
{
State* now=root;
for (char *i=b;*i;i++)
{
int k=*i-'a';
while (now&&!now->go[k])
now=now->suf;
now=now->go[k];
now->ri++;
}
for (int i=len;i>=1;i--)
for (now=fi[i];now;now=now->ne)
now->suf->ri+=now->ri;
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;root=last=Line(0);
for (char* i=b;*i;i++) extend(*i-'a');
Right();
for (;root!=cur;root++)
ans[root->val]=max(ans[root->val],root->ri);
for (int i=len-1;i>=1;i--)
ans[i]=max(ans[i+1],ans[i]);
for (int i=1;i<=len;i++)
printf("%d\n",ans[i]);
return 0;
}
SPOJ NSUBSTR2
动态加字符，同时给定一个串并且询问这个串在母串中出现几次。强制在线
如果没有修改就是直接处理出每个点的right集合大小。这样也差不多，反正每个点要求出自己子树内的叶子节点个数，就可以上LCT了。在建图过程中不会对suf树造成太大影响，只要处理下nq、q还有np的情况就好了。
然而SPOJ卡时间卡的实在sxbk，我硬是把所有能想到的优化都加上了还不能过，最后还是把每次询问的结点Splay一下才过了= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 160050
#define M 26
struct State
{State *suf,*go[M];int val,t;};
State *root,*last,statePool[N],*cur;
int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans;
bool fz[N],d[N];char b[N];
inline void fzj(int x)
{
if (!x||!fz[x]) return;
swap(c[x][0],c[x][1]);
fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]];
fz[x]=fz[0]=0;
}
inline void adj(int x)
{
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
ad[x]=ad[0]=0;
}
inline void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else
rf[x]=rf[i],rf[i]=0;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
}
void Up(int x)
{if (fa[x]) Up(fa[x]);fzj(x);adj(x);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
}
void Access(int x)
{
int i=0;
while (x)
{
Splay(x);
rf[c[x][1]]=fa[i]=x;
fa[c[x][1]]=rf[i]=0;
c[x][1]=i;i=x;x=rf[x];
}
}
void Delete(int x,int y)
{
Splay(x);
if (rf[x]==y) rf[x]=0;else
Splay(y),c[y][1]=fa[x]=0;
}
void extend(int w)
{
State *p=last,*np=cur++;np->t=++st;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;nq->t=++st;
memcpy(nq->go,q->go,sizeof q->go);
Delete(q->t,q->suf->t);t[st]=t[q->t];
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
rf[q->t]=st;rf[st]=nq->suf->t;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;rf[np->t]=np->suf->t;
Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t);
}
int main()
{
scanf("%s",b);
cur=statePool;root=last=cur++;root->t=st=1;
for (char* i=b;*i;i++) extend(*i-'a');
cin >>m>>A>>B;
while (m--)
{
scanf("%s",b);State* now=root;ans=0;
for (char* i=b;*i;i++)
if (!now->go[*i-'a'])
{ans=-1;break;}else
now=now->go[*i-'a'];
ans=ans?0:(Splay(now->t),t[now->t]);
printf("%d\n",ans);
extend((A*ans+B)%26);
}
return 0;
}
BZOJ2555
跟上题基本上一样= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 3000050
#define M 26
struct State
{State *suf,*go[M];int val,t;};
State *root,*last,statePool[N],*cur;
int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans,n,mask;
bool fz[N],d[N];char b[N],f[M];
inline void fzj(int x)
{
if (!x||!fz[x]) return;
swap(c[x][0],c[x][1]);
fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]];
fz[x]=fz[0]=0;
}
inline void adj(int x)
{
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
ad[x]=ad[0]=0;
}
inline void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else
rf[x]=rf[i],rf[i]=0;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
}
void Up(int x)
{if (fa[x]) Up(fa[x]);fzj(x);adj(x);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
}
void Access(int x)
{
int i=0;
while (x)
{
Splay(x);
rf[c[x][1]]=fa[i]=x;
fa[c[x][1]]=rf[i]=0;
c[x][1]=i;i=x;x=rf[x];
}
}
void Delete(int x,int y)
{
Splay(x);
if (rf[x]==y) rf[x]=0;else
Splay(y),c[y][1]=fa[x]=0;
}
void extend(int w)
{
State *p=last,*np=cur++;np->t=++st;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;nq->t=++st;
memcpy(nq->go,q->go,sizeof q->go);
Delete(q->t,q->suf->t);t[st]=t[q->t];
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
rf[q->t]=st;rf[st]=nq->suf->t;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;rf[np->t]=np->suf->t;
Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t);
}
int main()
{
scanf("%d%s",&m,b);
cur=statePool;root=last=cur++;root->t=st=1;
for (char* i=b;*i;i++) extend(*i-'A');
while (m--)
{
scanf("%s%s",f,b);
for (int i=0,len=strlen(b),Mask=mask;i<len;i++)
Mask=(Mask*131+i)%len,swap(b[i],b[Mask]);
if (f[0]=='A')
for (char* i=b;*i;i++) extend(*i-'A');else
{
State* now=root;ans=0;
for (char* i=b;*i;i++)
if (!now->go[*i-'A'])
{ans=-1;break;}else
now=now->go[*i-'A'];
ans=ans?0:(Splay(now->t),t[now->t]);
printf("%d\n",ans);mask^=ans;
}
}
return 0;
}
BZOJ 3676
题面：给定一个串，一个回文子串的权值是它的长度*它的出现次数，要求求出串中最大权值。|S|<=30w
题解：因为是在Keavil论文上看到这道题，但是按他的思路一直都没想出来怎么做，主要是一个状态可以是很多子串，所以不能直接更新出现次数。后来知道这题好像有至少三种写法真是sxbk，回文自动机的写法以后补，还有一个好神的hash和hzwer的SAM写法。后面两种主要都是有一个性质就是一个串中的不同的回文子串个数是O(n)的，感觉果然是manacher没学好= =，所以就可以直接在manacher过程中搞。hash解法好像是在manacher过程中把当前这个串hash然后建出一棵树，然后好像就可以搞了。SAM就是manacher的时候用当前回文子串倍增找到这个串所在答案，查询right集合大小更新答案。搞懂之后还调了好久，一开始naive没看空间限制，后面重新用数组写一遍才勉强卡过限制，结果还是写挂了好多地方调了好久= =，果然人太弱了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
#define M 26
#define ll long long
int fi[N],ne[N*2],val[N*2],go[N*2][M],suf[N*2][19];ll ans=0;
int pre[N],p[N*2],b[N*2],n,m,root,last,cur,ri[N*2];char c[N];
void extend(int w,int x)
{
int p=last,np=cur++;
val[np]=val[p]+1;
ne[np]=fi[val[np]];fi[val[np]]=np;
while (p&&!go[p][w])
go[p][w]=np,p=suf[p][0];
if (!p)
suf[np][0]=root;else
{
int q=go[p][w];
if (val[q]==val[p]+1)
suf[np][0]=q;else
{
int nq=cur++;
val[nq]=val[p]+1;
ne[nq]=fi[val[nq]];fi[val[nq]]=nq;
memcpy(go[nq],go[q],sizeof go[q]);
suf[nq][0]=suf[q][0];
suf[q][0]=suf[np][0]=nq;
while (p&&go[p][w]==q)
go[p][w]=nq,p=suf[p][0];
}
}
ri[last=pre[x]=np]=1;
}
void Set_up()
{
for (int i=n;i>=1;i--)
for (int j=fi[i];j;j=ne[j])
ri[suf[j][0]]+=ri[j];
for (int i=1;i<=n;i++)
for (int j=fi[i];j;j=ne[j])
for (int k=0;k<18&&suf[suf[j][k]][k];k++)
suf[j][k+1]=suf[suf[j][k]][k];
}
inline ll max(ll x,ll y)
{return x>y?x:y;}
void Query(int x,int y)
{
if (x>y) return;
int t=pre[y];
for (int i=18;i>=0;i--)
if (suf[t][i]&&val[suf[t][i]]>=y-x+1)
t=suf[t][i];
ans=max(ans,(ll)(ri[t])*(y-x+1));
}
void Manacher()
{
int k=0,l=-1;
for (int i=0;i<n;i++)
b[i*2+1]=c[i];
n*=2;b[n+1]=-1;
for (int i=0;i<=n;i++)
{
if (i<l) p[i]=min(p[k*2-i],l-i+1);
while (i-p[i]>=0&&b[i-p[i]]==b[i+p[i]])
Query(i-p[i] >> 1,i+p[i]-1 >> 1),p[i]++;
if (i+p[i]-1>l)
l=i+p[i]-1,k=i;
}
}
int main()
{
scanf("%s",c);n=strlen(c);
cur=1;last=root=cur++;
for (int i=0;i<n;i++) extend(c[i]-'a',i);
Set_up();Manacher();
cout <<ans<<endl;
return 0;
}
SAM转后缀数组就是标记每个结束状态然后DFS一遍SAM就很愉快了。
