A是水题，此处略去题解
B - PreSuffix ZOJ - 3995 （fail树+LCA）
给定多个字符串，每次询问查询两个字符串的一个后缀，该后缀必须是所有字符串中某个字符串的前缀，问该后缀最长时，是多少个字符串的前缀。
思路：对所有串构造ac自动机，根据fail指针的性质，a节点的fail指针指向b时，b一定是a的某个后缀。所以每次询问对两个字符串对应的节点在fail树上求一下LCA，插入时经过了LCA节点的字符串的个数便是答案。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int kind = ;
#define mem(x) memset(x,0,sizeof x)
const int maxn=;
int trie[maxn][];
int p_cnt;
int coun[maxn];
char s[maxn];
int mp[maxn];
int fail[maxn];
vector<int> G[maxn];
int f[maxn],d[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],tid[maxn],cnt;
inline void init()
{
p_cnt=;
cnt=;
mem(trie),mem(coun),mem(fail),mem(mp);
mem(f),mem(d),mem(siz),mem(son),mem(rk),mem(top),mem(tid);
}
void insert(char *str,int num)
{
int p=;
int i=,index;
while(str[i])
{
index=str[i]-'a';
if(trie[p][index]==) trie[p][index]=++p_cnt;
p=trie[p][index];
coun[p]++;
i++;
}
mp[num]=p;
}
inline void addedge(int x,int y)
{
G[x].push_back(y);
G[y].push_back(x);
}
void build_ac_automation()
{
deque<int>dq;
int i;
fail[]=;
dq.push_back();
while(!dq.empty())
{
int tmp=dq.front();
dq.pop_front();
int p=;
for(i=; i<kind; i++)
{
if(trie[tmp][i])
{
if(tmp==)
{
fail[trie[tmp][i]]=;
addedge(trie[tmp][i],);
}
else
{
p=fail[tmp];
while(p!=)
{
if(trie[p][i]!=)
{
fail[trie[tmp][i]]=trie[p][i];
addedge(trie[tmp][i],trie[p][i]);
break;
}
p=fail[p];
}
if(p==)
{
fail[trie[tmp][i]]=;
addedge(trie[tmp][i],);
}
}
dq.push_back(trie[tmp][i]);
}
}
}
}
void dfs1(int u,int fa,int depth)
{
f[u]=fa;
d[u]=depth;
siz[u]=;
for(int i=; i<G[u].size(); i++)
{
int v=G[u][i];
if(v==fa)
continue;
dfs1(v,u,depth+);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t)
{
top[u]=t;
tid[u]=++cnt;
rk[cnt]=u;
if(!son[u])
return;
dfs2(son[u],t);
for(int i=; i<G[u].size(); i++)
{
int v=G[u][i];
if(v!=son[u]&&v!=f[u])
dfs2(v,v);
}
}
int LCA(int x,int y)
{
if(x==y)
return x;
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(d[fx]>=d[fy])
{
x=f[fx];
}
else
{
y=f[fy];
}
fx=top[x];
fy=top[y];
}
if(tid[x]<=tid[y]) return x;
else return y;
}
#define debug cout<<"debug\n"
int main()
{
//freopen("in.txt","r",stdin);
int n,q;
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=;i<=n;i++)
{
scanf("%s",s);
insert(s,i);
}
for(int i=;i<=p_cnt;i++)
G[i].clear();
build_ac_automation();
dfs1(,,);
dfs2(,);
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
x=mp[x];
y=mp[y];
int z=LCA(x,y);
if(coun[z]==) puts("N");
else printf("%d\n",coun[z]);
}
}
return ;
}
E - Yet Another Data Structure Problem ZOJ - 3998 （线段树)
给定一个长度为N的数列，每次询问有三种操作：
1.将区间[l,r]中的每个元素乘上v
2.将区间[l,r]中的每个元素变为原来的k次方
3.求[l,r]中每个数的乘积对1e9+7取模.
一道相对较裸的数据结构题。用一棵线段树维护区间乘积，用两个lazy印记来标记修改，对于操作1，相当于区间乘积乘上v^(r-l+1)，对于操作2，相当于区间中的乘积变为原来的k次方即可。利用快速幂取模以及a^b%mod=a^(b%(mod-1))%mod来避免指数爆long long，以及注意细节即可。(注意两个印记破坏的先后顺序)
大常数制造机
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+;
const int mod=1e9+;
ll ans[maxn*];
ll tag1[maxn*];
ll tag2[maxn*];
ll a[maxn];
inline ll q_p(ll a,ll b)
{
ll ans=;
a%=mod;
while(b)
{
if(b&)
ans=a*ans%mod;
b>>=;
a=a*a%mod;
}
return ans;
}
void build(int o,int l,int r)
{
tag1[o]=tag2[o]=;
if(l==r)
{
ans[o]=a[l];
return;
}
int lson=o<<,rson=lson|;
int m=(l+r)>>;
build(lson,l,m);
build(rson,m+,r);
ans[o]=(ans[lson]*ans[rson])%mod;
}
void update1(int o,int l,int r,int ql,int qr,int k)//区间修改:将[l,r]区间每个数*k
{
int lson=o<<,rson=lson|;
int m=(l+r)>>;
if(ql<=l&&qr>=r)
{
tag1[o]*=k;
tag1[o]%=mod;
ans[o]*=q_p(k,r-l+);
ans[o]%=mod;
return;
}
if(tag2[o]!=)
{
tag2[lson]*=tag2[o];
tag2[rson]*=tag2[o];
tag2[lson]%=mod-;
tag2[rson]%=mod-;
ans[lson]=q_p(ans[lson],tag2[o]);
ans[rson]=q_p(ans[rson],tag2[o]);
tag1[lson]=q_p(tag1[lson],tag2[o]);
tag1[rson]=q_p(tag1[rson],tag2[o]);
tag2[o]=;
}
if(tag1[o]!=)
{
tag1[lson]*=tag1[o];
tag1[rson]*=tag1[o];
tag1[lson]%=mod;
tag1[rson]%=mod;
ans[lson]*=q_p(tag1[o],(m-l+));
ans[rson]*=q_p(tag1[o],(r-m));
ans[lson]%=mod;
ans[rson]%=mod;
tag1[o]=;
}
if(qr<=m)
update1(lson,l,m,ql,qr,k);
else if(ql>m)
update1(rson,m+,r,ql,qr,k);
else
{
update1(lson,l,m,ql,qr,k);
update1(rson,m+,r,ql,qr,k);
}
ans[o]=ans[lson]*ans[rson]%mod;
}
void update2(int o,int l,int r,int ql,int qr,int k)//区间修改:将[l,r]区间每个数变为k次方
{
int lson=o<<,rson=lson|;
int m=(l+r)>>;
if(ql<=l&&qr>=r)
{
tag1[o]=q_p(tag1[o],k);
tag2[o]*=k;
tag2[o]%=mod-;
ans[o]=q_p(ans[o],k);
return;
}
if(tag2[o]!=)
{
tag2[lson]*=tag2[o];
tag2[rson]*=tag2[o];
tag2[lson]%=mod-;
tag2[rson]%=mod-;
ans[lson]=q_p(ans[lson],tag2[o]);
ans[rson]=q_p(ans[rson],tag2[o]);
tag1[lson]=q_p(tag1[lson],tag2[o]);
tag1[rson]=q_p(tag1[rson],tag2[o]);
tag2[o]=;
}
if(tag1[o]!=)
{
tag1[lson]*=tag1[o];
tag1[rson]*=tag1[o];
tag1[lson]%=mod;
tag1[rson]%=mod;
ans[lson]*=q_p(tag1[o],(m-l+));
ans[rson]*=q_p(tag1[o],(r-m));
ans[lson]%=mod;
ans[rson]%=mod;
tag1[o]=;
}
if(qr<=m)
update2(lson,l,m,ql,qr,k);
else if(ql>m)
update2(rson,m+,r,ql,qr,k);
else
{
update2(lson,l,m,ql,qr,k);
update2(rson,m+,r,ql,qr,k);
}
ans[o]=ans[lson]*ans[rson]%mod;
}
ll query(int o,int l,int r,int ql,int qr)//区间查询
{
int lson=o<<,rson=lson|;
int m=(l+r)>>;
if(ql<=l&&qr>=r)
return ans[o];
if(tag2[o]!=)
{
tag2[lson]*=tag2[o];
tag2[rson]*=tag2[o];
tag2[lson]%=mod-;
tag2[rson]%=mod-;
ans[lson]=q_p(ans[lson],tag2[o]);
ans[rson]=q_p(ans[rson],tag2[o]);
tag1[lson]=q_p(tag1[lson],tag2[o]);
tag1[rson]=q_p(tag1[rson],tag2[o]);
tag2[o]=;
}
if(tag1[o]!=)
{
tag1[lson]*=tag1[o];
tag1[rson]*=tag1[o];
tag1[lson]%=mod;
tag1[rson]%=mod;
ans[lson]*=q_p(tag1[o],(m-l+));
ans[rson]*=q_p(tag1[o],(r-m));
ans[lson]%=mod;
ans[rson]%=mod;
tag1[o]=;
}
if(qr<=m)
return query(lson,l,m,ql,qr);
if(ql>m)
return query(rson,m+,r,ql,qr);
return query(lson,l,m,ql,qr)*query(rson,m+,r,ql,qr)%mod;
}
inline void init()
{
memset(ans,,sizeof ans);
memset(tag1,,sizeof tag1);
memset(tag2,,sizeof tag2);
memset(a,,sizeof a);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
int n,q;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%lld",a+i);
build(,,n);
while(q--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==)
{
ll k;
scanf("%lld",&k);
update1(,,n,l,r,k);
}
if(op==)
{
ll k;
scanf("%lld",&k);
update2(,,n,l,r,k);
}
if(op==)
{
printf("%lld\n",query(,,n,l,r));
}
}
}
}
H - Traveling Plan ZOJ - 4001（最小生成树+路径最大值）
一个图上，有n个点，m条边，其中一些点是补给站，可以将主人公的背包充满，走在路上会消化边权值的食物，q次询问，问从x点旅行到y点，最少要带多大的背包才能使得不会主人公不会受饿。
做法：
求出每个点到最近的补给站的距离dist[i]，然后将所有边权修改为dist[i]+dist[j]+w，求一下最小生成树，对于每次询问x,y，答案即为树上的边权最大值。
#include<bits/stdc++.h>
using namespace std;
#define mem(x) memset(x,0,sizeof x)
#define debug cout<<"debug\n"
const int maxn=;
int n;
struct edge
{
int u,v,val;
edge(int _u=,int _v=,int _val=)
{
u=_u;
v=_v;
val=_val;
}
}e[*maxn];
bool cmp(edge a,edge b)
{
return a.val<b.val;
}
vector<edge>G[maxn];
vector<edge>G2[maxn];
inline void addedge(int u,int v,int val)
{
G[u].push_back(edge(u,v,val));
G[v].push_back(edge(v,u,val));
}
inline void addedge2(int u,int v,int val)
{
G2[u].push_back(edge(u,v,val));
G2[v].push_back(edge(v,u,val));
}
typedef pair<int,int> p;
int dist[maxn];
priority_queue<p,vector<p>,greater<p> >q;
int a[maxn];
int find(int x)
{
if (x != a[x])
{
a[x] = find(a[x]);
}
return a[x];
}
bool merge(int u,int v)
{
u=find(u);
v=find(v);
if(u!=v)
{
a[u]=v;
return true;
}
return false;
}
int b[maxn],cnt,f[maxn],d[maxn],siz[maxn],son[maxn],rk[maxn],top[maxn],tid[maxn];
void dfs1(int u,int fa,int depth)
{
f[u]=fa;
d[u]=depth;
siz[u]=;
for(int i=; i<G2[u].size(); i++)
{
int v=G2[u][i].v;
if(v==fa)
continue;
b[v]=G2[u][i].val;
dfs1(v,u,depth+);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t)
{
top[u]=t;
tid[u]=++cnt;
rk[cnt]=u;
if(!son[u])
return;
dfs2(son[u],t);
for(int i=; i<G2[u].size(); i++)
{
int v=G2[u][i].v;
if(v!=son[u]&&v!=f[u])
dfs2(v,v);
}
}
int tr[maxn*];
void build(int o,int l,int r)
{
if(l==r)
{
tr[o]=b[rk[l]];
return;
}
int lson=o<<,rson=lson|;
int m=(l+r)>>;
build(lson,l,m);
build(rson,m+,r);
tr[o]=max(tr[lson],tr[rson]);
}
int query(int o,int l,int r,int ql,int qr)//区间查询
{
int lson=o<<,rson=lson|;
int m=(l+r)>>;
if(ql<=l&&qr>=r)
return tr[o];
if(qr<=m)
return query(lson,l,m,ql,qr);
if(ql>m)
return query(rson,m+,r,ql,qr);
return max(query(lson,l,m,ql,qr),query(rson,m+,r,ql,qr));
}
int ask(int x,int y)
{
int ans=-;
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(d[fx]>=d[fy])
{
ans=max(ans,query(,,n,tid[fx],tid[x]));
x=f[fx];
}
else
{
ans=max(ans,query(,,n,tid[fy],tid[y]));
y=f[fy];
}
fx=top[x];
fy=top[y];
}
if(tid[x]==tid[y])
return ans;
if(tid[x]<tid[y])
ans=max(ans,query(,,n,tid[x]+,tid[y]));
else
ans=max(ans,query(,,n,tid[y]+,tid[x]));
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
int m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
a[i]=i;
int mark;
scanf("%d",&mark);
if(mark)
q.push(p(,i));
else
dist[i]=1e9;
}
for(int i=; i<=m; i++)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
addedge(u,v,val);
}
while(!q.empty())
{
p a=q.top();
q.pop();
int u=a.second;
int d=a.first;
if(dist[u]<d) continue;
for(int i=;i<G[u].size();i++)
{
int v=G[u][i].v;
int dd=G[u][i].val;
if(dist[v]>d+dd)
{
q.push(p(d+dd,v));
dist[v]=d+dd;
}
}
}
int cnt=;
for(int i=;i<=n;i++)
{
for(int j=;j<G[i].size();j++)
{
G[i][j].val+=dist[i]+dist[G[i][j].v];
e[++cnt]=edge(i,G[i][j].v,G[i][j].val);
}
}
sort(e+,e+cnt+,cmp);
for(int i=;i<=cnt;i++)
{
int x=e[i].u;
int y=e[i].v;
if(merge(x,y))
addedge2(x,y,e[i].val);
}
cnt=;
dfs1(,,);
dfs2(,);
build(,,n);
int Q;
scanf("%d",&Q);
while(Q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y));
}
return ;
}
J - Distance ZOJ - 4003 （思维)
给定两个数列a,b，分别在两个数列上选取相同长度的连续的子序列，使得两个子序列中Σ(abs(a[i]-b[j])^p)<=v，问有多少种选取方案
首先考虑暴力去枚举两个子序列的起始位置i,j，然后从i和j出发一个一个的求和直到sum>v，就得到了从i,j起头的可行方案，然后将所有的方案加起来就是答案，复杂度O(n^3)
思考：
如果a[1...5]与b[2...6]是求出来的最长可行方案，那么对于2,3起头的时候，a[2...5]与b[3...6]也是可行的，如此，便不需要再从2和3开始跑。
于是做出以下优化：
在每次暴力的时候记录i,j对应的尾位置
那么对于在之前已经做过求和的一对数字a[tmp_i]和b[tmp_j]，获取上一次计算这一段时的尾位置，从尾位置开始往后延申，跑到sum>v为止，记录尾位置
复杂度O(n^2)
需要注意的细节：请手写求幂，请手写求幂，请手写求幂（重要的事情说三遍），用库里的pow函数会tle（大常数）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x) memset(x,0,sizeof x)
#define debug cout<<"debug\n"
const int maxn=;
ll a[maxn],b[maxn];
int tail[maxn][maxn];
ll sum[maxn][maxn];
ll n,v,p;
inline ll f(int i,int j)
{
ll ans=;
ll x=abs(a[i]-b[j]);
for(int i=;i<p;i++)
ans*=x;
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&v,&p);
for(int i=; i<=n; i++) scanf("%lld",a+i);
for(int i=; i<=n; i++) scanf("%lld",b+i);
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
ll tmp=sum[i-][j-]-f(i-,j-);
int k;
for(k=tail[i-][j-]-; i+k<=n&&j+k<=n; k++)
{
if(tmp+f(i+k,j+k)<=v)
tmp+=f(i+k,j+k);
else
break;
}
sum[i][j]=tmp;
tail[i][j]=k;
}
}
ll ans=;
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
ans+=tail[i][j];
tail[i][j]=sum[i][j]=;
}
}
printf("%lld\n",ans);
}
return ;
}