题解：P10279 [USACO24OPEN] The 'Winning' Gene S

· · 题解

区区 3\times 10^3，n^3 又能怎？

Solution P10279

Idea

考虑枚举 l。

紧接着枚举序列，然后把子串预处理出来。

记 S_i 为以 i 开头的子串。

接下来基本套路：把枚举型问题转化为贡献型问题。考虑一个子串 S_l，对哪些 k 有贡献。

那么需要找到 S_l 左边最靠右的，字典序小于等于 S_l 的子串及右边最靠左的，字典序小于 S_l 的子串。这个单调栈容易维护。

然后设字典序小于 S_l 的子串左端点为 R，左边最靠右的，字典序小于等于 S_l 的子串左端点为 L，于是对于 k\in[1en,R-L+1en+1]，都可以产生贡献。实际在代码实现中，为了节省空间，我把第 len 位的数组左移了 len 位，至 [1,R-L+1]。区间加法可以用差分实现。

但是问题是：普通整数的比较是 \operatorname{O}(1) 的，但是字符串是 \operatorname{O}(n) 的！这很要命！

于是考虑优化。

  1. 记忆化优化。

不难发现如果有两个字符串 S_i,S_j，因为 len 从小到大枚举，所以 S_i,S_j 只会变长。如果在某个时刻，S_i>S_j（或小于），那么就记录下来，后续比较的时候直接返回即可。

  1. 类当前弧优化。

不难发现什么数据会把我们卡住呢？就像这样的：

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

每一次我们需要比较这两个字符串，都需要从 1 开始，枚举，直到枚举到 b 才能被记忆化。那么如果我们比较出来是相同的，不妨记录一个 h_{i,j} 表示 S_i 与 S_j 的第 [1,h_{i,j}] 位已经被验证是相同的，这样就可以从 h_{i,j}+1 位开始枚举，大大降低总复杂度。

这样你就能卡过去。

::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
string s;
char ch[N][N];
int n;
int ans[N][N],cnt[N];
int L[N],R[N];
stack<int>st;
int f[N][N],g[N][N];
int h[N][N],o[N][N];
bool biggerb(int p1,int p2,int len,char s1[],char s2[]){
    if(f[p1][p2]==1)return true;    
    if(f[p1][p2]==-1)return false;  
    for(int i=h[p1][p2]+1;i<=len;i++){
        if(s1[i]>s2[i]){
            f[p1][p2]=1;
            return true;
        }
        if(s1[i]<s2[i]){
            f[p1][p2]=-1;
            return false;
        }
    }
    h[p1][p2]=len;
    return false;
}
bool biggere(int p1,int p2,int len,char s1[],char s2[]){
    if(g[p1][p2]==1)return true;    
    if(g[p1][p2]==-1)return false;  
    for(int i=o[p1][p2]+1;i<=len;i++){
        if(s1[i]>s2[i]){
            g[p1][p2]=1;
            return true;
        }
        if(s1[i]<s2[i]){
            g[p1][p2]=-1;
            return false;
        }
    }
    o[p1][p2]=len;
    return true;
}
int main(){
    cin>>n>>s;s=' '+s;
    for(int len=1;len<=n;len++){
        for(int l=1,r=len;r<=n;l++,r++){
            ch[l][len]=s[r];
        }
        while(!st.empty())st.pop();
        for(int l=1,r=len;r<=n;l++,r++){
            while(!st.empty()&&biggerb(st.top(),l,len,ch[st.top()],ch[l])){
                st.pop();
            }
            if(!st.empty())L[l]=st.top()+1;
            else L[l]=1;
            st.push(l);
        }
        while(!st.empty())st.pop();
        for(int r=n,l=n-len+1;l>=1;l--,r--){
            while(!st.empty()&&biggere(st.top(),l,len,ch[st.top()],ch[l])){
                st.pop();
            }
            if(!st.empty())R[l]=st.top()-1;
            else R[l]=n-len+1;
            st.push(l);
        }
        for(int l=1,r=len;r<=n;l++,r++){
            ans[1][len]++;ans[R[l]-L[l]+2][len]--;
        }
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i<=n;i++){
            ans[i][len]+=ans[i-1][len];
            cnt[ans[i][len]]++;
        }
    }
    for(int i=1;i<=n;i++)cout<<cnt[i]<<'\n';
    return 0;
}

::::