"洛谷題目頁面傳送門" & "CodeForces題目頁面傳送門" 給定一個$n$個單詞的文本，第$i$個單詞的長度為$len_i$，要求截取文本的一段（單詞必須取整的），分若幹行放，同行詞語用空格分隔，使得每行的長度不超過$m$，最多放$s$行。求截取的單詞數最多的截法。 $n\in[1,10^6 ...
洛谷題目頁面傳送門 & 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}\)，那麼我們可以從後往前two-pointers，求\(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;
}
}
