题解：P11084 [ROI 2019] 灯串 (Day 2)

· · 题解

出到集训里了，写个题解。

思路

感觉 dp 很没有前途啊，所以还是考虑枚举吧。

设我们当前枚举的连续的 0 的长度为 k，则我们需要从原来的串中找到由连续 k 个 0 和一个 1 构成的子序列，显然贪心的找即可，因为剩下的部分更多一定是不劣的，这样我们就有了一个 O(n^2) 的暴力。

那么考虑优化，你发现如果你能够在 O(B) 的时间内从一个位置 1 跳到下一个与其间隔有 k 个 0 的 1 上，则你的总时间复杂度是 O(Bn\ln n) 级的，因为枚举的 k 显然最多构成 \frac{n}{k} 段连续的 0，于是就是调和级数量级的。

你发现，你可以预处理处每个位置后面的 0 的位置，然后倍增向后跳，这样 B=\log n 了，于是你得到了小常数的 O(n\log^2n) 的做法。

害怕过不去，所以加了一个不知道有没有用的优化，就是倍增跳的时候每次跳当前剩余距离 x 的 \operatorname{lowbit}(x)，这样就不是每个数都得跳严格 \left\lceil\log_2x\right\rceil 次了，常数可能会小一点。

代码

:::success[代码]

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int
using namespace std;
const ll N=5e5+10;
string s;
inline ll lowbit(ll x){return x&(-x);}
ll n,f[N],sum[N],bk1[N],bk0[N][19],lg[N];
ll jp(ll now,ll dis){
    if(!dis) return now;
    if(lowbit(dis)==dis) return bk0[now][lg[dis]];
    return jp(bk0[now][lg[lowbit(dis)]],dis^(lowbit(dis)));
}
void solve(){
    cin>>n>>s;s=' '+s;
    ll anslen=0,ansdis=0;
    for(ll i=1;i<=n;i++){
        if(s[i-1]=='0') bk0[i][0]=i-1;
        else bk0[i][0]=bk0[i-1][0];
        for(ll j=1;j<19;j++) bk0[i][j]=bk0[bk0[i][j-1]][j-1];
        if(s[i-1]=='1') bk1[i]=i-1;
        else bk1[i]=bk1[i-1];
        anslen+=(s[i]=='1');
    }
    for(ll i=1;i<=n;i++){
        ll now=n,ncnt=0;
        if(s[now]!='0') now=bk0[now][0]; 
        while(now){
            now=jp(now,i-1);
            if(now!=0) ncnt++;
            now=bk0[bk1[now]][0];
        }
        if(ncnt>1){
            if(ncnt*i+ncnt-1>anslen){
                anslen=ncnt*i+ncnt-1;
                ansdis=i;
            }
        }
    }
    cout<<anslen<<"\n";
    while(anslen){
        anslen-=ansdis;
        for(ll i=1;i<=ansdis;i++) cout<<'0';
        if(anslen){cout<<'1';anslen--;}
    }
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    lg[1]=0;for(ll i=2;i<N;i++) lg[i]=lg[i>>1]+1;
    solve();
    return 0;
}

:::