CodeForces 309B Context Advertising

洛谷题目页面传送门 & codeforces题目页面传送门

给定一个\(n\)个单词的文本，第\(i\)个单词的长度为\(len_i\)，要求截取文本的一段（单词必须取整的），分若干行放，同行词语用空格分隔，使得每行的长度不超过\(m\)，最多放\(s\)行。求截取的单词数最多的截法。

\(n\in[1,10^6],\sum\limits_{i=1}^nlen_i\in[1,5\times10^6],ms\in[1,10^6]\)。

这道题想要ac还是很容易的。考虑枚举截取的第\(1\)个单词，然后计算往后最多能延申多少个单词，最后取个\(\max\)。重点在于如何计算往后最多能延申多少个单词，这个可以傻傻地贪心。先求出\(spl\)数组，表示从第\(i\)个单词开始最多能往后延申到第\(spl_i-1\)个单词放在一行。很显然，“是否能延申到第\(x\)个单词放在一行”具有单调性，于是\(spl\)数组可以\(\mathrm o(n\log_2n)\)配合前缀和二分求出。那么从第\(i\)个单词往后最多能延申的单词数就是\(\underbrace{spl_{spl_{spl_{\cdots_{i}}}}}_{s\text{次}spl\text{映射}}-i\)。这个又显然可以总共\(\mathrm o(n\log_2n)\)倍增求出。于是\(\mathrm o(n\log_2n)\)的复杂度是extremely easy的。

而我们是追求完美的oier，这个复杂度能否达到\(\mathrm o(n)\)呢？带\(\log\)复杂度的地方有\(2\)个——求\(spl\)数组和\(s\)次\(spl\)映射，我们一个一个来看。

首先是求\(spl\)数组。不难发现，\(spl\)数组本身具有单调性，即\(spl_i\le spl_{i+1}\)，那么我们可以从后往前递推，求\(spl_i\)时，只需从\(spl_{i+1}\)到\(i\)从后往前试是否能延申到即可。其中边界是\(spl_{n+1}=n+1\)。这样所有单词均摊被试\(\mathrm o(n)\)次，时间复杂度就没有\(\log\)了。

接下来是映射。仍然利用\(spl\)数组的单调性，若在所有\(i\)和\(spl_i\)之间连一条边，若\(i=spl_i\)则不连边，那么一定会形成一个森林，而对\(i\)进行\(s\)次映射显然就等于节点\(i\)的\(\min(s,dep_i)\)辈祖先。我们对森林里的每一棵树进行dfs，同时维护一个递归栈\(stk\)，那么\(\mathrm o(1)\)便可找到节点\(i\)的\(\min(s,dep_i)\)辈祖先，复杂度也变成整体\(\mathrm o(n)\)了。

下面贴代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int n=1000000;
int n/*单词数*/,m/*每行最多能放的长度*/,s/*最多能放的行数*/;
string a[n+1];//单词们 
int sum[n+1];//前缀长度和（每个单词后面加上空格） 
vector<int> son[n+2];int fa[n+2];//树，fa即spl数组 
int stk[n+1],top;//递归栈 
int ans[n+2];//从第i个单词开始最多能延伸的单词数 
void dfs(int x){//对树dfs 
    stk[top++]=x;//将此节点入栈 
    ans[x]=stk[max(0,top-1-s)]-x;//o(1)找min(s,dep[i])辈祖先 
    for(int i=0;i<son[x].size();i++){
        int y=son[x][i];
        dfs(y);
    }
    top--;//出栈 
}
int main(){
    cin>>n>>s>>m;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i].size()+1/*预处理前缀和*/;
    fa[n+1]=n+1;//递推边界 
    for(int i=n;i;i--){//从后往前递推 
        fa[i]=fa[i+1]; 
        while(sum[fa[i]-1]-sum[i-1]-1>m)fa[i]--;//从后往前试 
        if(fa[i]!=i)son[fa[i]].pb(i);//连边 
    }
//  for(int i=1;i<=n+1;i++)cout<<fa[i]<<" ";puts("");
    for(int i=1;i<=n+1;i++)if(fa[i]==i)top=0,dfs(i);//dfs每棵树 
    int mx=*max_element(ans+1,ans+n+2);//最大答案 
    for(int i=1;i<=n+1;i++)if(ans[i]==mx){
        while(s--){//输出 
            for(int j=i;j<fa[i];j++)cout<<a[j]<<(j<fa[i]-1?" ":"\n");
            i=fa[i];
        }
        return 0;
    }
}