美圖欣賞 | 設為首頁 | 加入收藏 | 網站地圖

當前位置:新錦江平臺:www.xjj7.com-電腦中國 > 編程 > C++ >

CodeForces 309B Context Advertising

2019-10-18 14:51|來源:未知 |作者:dnzg |點擊:

洛谷題目頁面傳送門 & 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;
    }
}
(責任編輯:dnzg)
相關閱讀
安卓手机安全赚钱软件哪个好用 天津11选五开奖结果走势图解 玩pc蛋蛋赚q币 北京pk拾前一的技巧 股票融资和债券融资 北京快三开奖结果今天 股股赢配资 11选5复式 股票杠杆融资 体彩20选5开奖 体育彩票排列5开奖结果