字符串专题
B - Yet Another LCP Problem
相似题目差异
题目主要内容就是求 $ \sum lcp(T_i,T_j) $
利用后缀自动机,并求height数组。
我们发现,统计答案的先后顺序是没有影响的,我们不妨用排序后的顺序统计。
\[lcp(i,j)=\min_{k=i}^{j}\{ height[k] \} \]发现这是具有单调性的。
我们用单调栈维护一段的最小height,直接扫过去,统计答案即可。
注意特判空栈就好。复杂度 $ O(n) $
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+100;
int n,q,k,l,a,b,m;
char s[N];
int sa[N],rak[N],tax[N],tp[N],sum,ans,height[N];
int qs[N];
struct solve{
int id,val;
};
stack<solve>st;
void qsort(){
memset(tax,0,sizeof(tax));
for(int i=1;i<=n;i++)tax[rak[i]]++;
for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
for(int i=n;i>=1;i--)sa[tax[rak[tp[i]]]--]=tp[i];
}
void suffixsort(){
m=200;
for(int i=1;i<=n;i++){
rak[i]=s[i];
tp[i]=i;
}
qsort();
for(int w=1,p=0;p<n;w<<=1,m=p){
p=0;
for(int i=1;i<=w;i++)tp[++p]=n-w+i;
for(int i=1;i<=n;i++)
if(sa[i]>w)tp[++p]=sa[i]-w;
qsort();swap(rak,tp);
rak[sa[1]]=p=1;
for(int i=2;i<=n;i++){
rak[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
}
}
}
void get_height(){
int j,k=0;
for(int i=1;i<=n;i++){
if(k)k--;
j=sa[rak[i]-1];
while(s[i+k]==s[j+k])k++;
height[rak[i]]=k;
}
}
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
suffixsort();
get_height();
for(int i=n;i>=1;i--){
qs[i]=qs[i+1]+i;
}
for(int i=1;i<n;i++)ans+=qs[i+1];
for(int i=1;i<n;i++)ans+=i*(n-i);
for(int i=1;i<=n;i++){
while(!st.empty()&&st.top().val>height[i]){
solve k=st.top();
st.pop();
sum-=k.val*(k.id-st.top().id);
}
if(!st.empty())
sum+=height[i]*(i-st.top().id);
else sum+=height[i]*(i-1);
st.push(solve{i,height[i]});
ans-=2*sum;
}
cout<<ans<<endl;
}
正解
通过上一题后,这题就好理解多了。
我们将a数组和b数组合并为一个大数组,由于不一定连贯,我们用ST表处理每两个之间height最小值,然后类似于上一题的做法,最后还要去重,因为贡献中多计算a与自身和b与自身。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+100;
int n,q,k,l,a[N],b[N],m;
char s[N];
int sa[N],rak[N],tax[N],tp[N],height[N];
int v[N];
int st[20][N],lg[N];
int sum,ans;
int minn[N];
stack<int>sta;
void qsort(){
memset(tax,0,sizeof(tax));
for(int i=1;i<=n;i++)tax[rak[i]]++;
for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
for(int i=n;i>=1;i--)sa[tax[rak[tp[i]]]--]=tp[i];
}
void suffixsort(){
m=200;
for(int i=1;i<=n;i++){
rak[i]=s[i];
tp[i]=i;
}
qsort();
for(int w=1,p=0;p<n;w<<=1,m=p){
p=0;
for(int i=1;i<=w;i++)tp[++p]=n-w+i;
for(int i=1;i<=n;i++)
if(sa[i]>w)tp[++p]=sa[i]-w;
qsort();swap(rak,tp);
rak[sa[1]]=p=1;
for(int i=2;i<=n;i++){
rak[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
}
}
}
void get_height(){
int j,k=0;
for(int i=1;i<=n;i++){
if(k)k--;
j=sa[rak[i]-1];
while(s[i+k]==s[j+k])k++;
height[rak[i]]=k;
}
}
bool cmp(int x,int y){
return rak[x]<rak[y];
}
int solve(int x[],int len){
int w;
w=lg[x[1]];
minn[1]=min(st[w][1],st[w][x[1]-(1<<w)]);
for(int i=2;i<=len;i++){
w=lg[x[i]-x[i-1]];
if(x[i]==x[i-1])minn[i]=n-sa[x[i]]+1;
else
minn[i]=min(st[w][x[i-1]+1],st[w][x[i]-(1<<w)+1]);
}
// for(int i=1;i<=len;i++)cout<<minn[i]<<endl;
while(!sta.empty())sta.pop();
m=sum=0;
for(int i=1;i<=len;i++){
while(!sta.empty()&&minn[sta.top()]>minn[i]){
int w=sta.top();
sta.pop();
sum-=minn[w]*(w-sta.top());
}
if(!sta.empty())sum+=minn[i]*(i-sta.top());
else sum+=minn[i]*(i-1);
sta.push(i);
m+=sum;
}
return m;
}
signed main()
{
scanf("%d%d",&n,&q);
scanf("%s",s+1);
suffixsort();
get_height();
for(int i=2;i<N;i++){
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=n;i++){
st[0][i]=height[i];
}
for(int i=1;i<=lg[n]+1;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
while(q--){
scanf("%d%d",&k,&l);
for(int i=1;i<=k;i++){
scanf("%d",&a[i]);
v[i]=a[i];
}
for(int i=1;i<=l;i++){
scanf("%d",&b[i]);
v[k+i]=b[i];
}
sort(v+1,v+k+l+1,cmp);
sort(a+1,a+k+1,cmp);
sort(b+1,b+l+1,cmp);
for(int i=1;i<=k;i++)a[i]=rak[a[i]];
for(int i=1;i<=l;i++)b[i]=rak[b[i]];
for(int i=1;i<=k+l;i++)v[i]=rak[v[i]];
printf("%lld\n",solve(v,k+l)-solve(a,k)-solve(b,l));
}
}
G - x-prime Substrings
AC自动机+DP
发现X非常小,我们枚举所有可能的"x-prime"串,放在AC自动机上,并拿字符串s匹配,如果一个节点是某个"x-prime"串的最后一个字符,打上flag标记。现在问题成为:s在自动机上匹配,不能经过flag标记,最少需要删掉几个字符。
有以下DP方程:
\[dp[i][v]=\min\{dp[i-1][u],dp[i-1][v]+1 \}(!flag[v]) \]当前节点可以由其父亲节点转移,也可以删除当前节点,由自身转移。
可以特判根节点的情况。
CODE
#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int x,n;
char s[N];
vector<int>h_pri;
char t[N<<2][N],k[N];
int p,num,len[N<<2],dp[N][N<<3];
int cnt=1;
struct AC{
int son[30],fail;
bool flag;
}trie[N<<5];
void dfs(int tot){
if(tot==x){
for(int i=1;i<=p;i++){
int sum=0;
for(int j=i;j<=p;j++){
sum+=k[j]-'0';
if(x%sum==0&&x!=sum)return ;
}
}
num++;
for(int i=1;i<=p;i++){
t[num][i]=k[i];
}
len[num]=p;
}
if(tot>=x)return ;
for(auto i:h_pri){
k[++p]='0'+i;
dfs(tot+i);
p--;
}
}
void insert(int a){
int u=1;
for(int i=1;i<=len[a];i++){
if(!trie[u].son[t[a][i]-'0']){
trie[u].son[t[a][i]-'0']=++cnt;
}
u=trie[u].son[t[a][i]-'0'];
}
trie[u].flag=1;
}
void getfail(){
for(int i=1;i<=9;i++)trie[0].son[i]=1;
queue<int>q;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=1;i<=9;i++){
int v=trie[u].son[i];
int fail=trie[u].fail;
if(!v){
trie[u].son[i]=trie[fail].son[i];
continue;
}
trie[v].fail=trie[fail].son[i];
q.push(v);
}
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
scanf("%d",&x);
for(int i=2;i<=min(x,9);i++){
if(x%i!=0){
h_pri.push_back(i);
}
}
if(x<=9)h_pri.push_back(x);
dfs(0);
for(int i=1;i<=num;i++){
insert(i);
}
getfail();
memset(dp,0x3f,sizeof(dp));
dp[0][1]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
int v=trie[j].son[s[i]-'0'];
dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(j!=1){
if(!trie[v].flag)
dp[i][v]=min(dp[i][v],dp[i-1][j]);
}
else{
if(v){
if(!trie[v].flag)
dp[i][v]=min(dp[i][v],dp[i-1][j]);
}
else dp[i][1]=min(dp[i][1],dp[i-1][1]+1);
}
}
}
int ans=INT_MAX;
for(int i=1;i<=cnt;++i) ans=min(ans,dp[n][i]);
cout<<ans<<'\n';
}