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

思路

感觉 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;
}

:::