题解：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

次了，常数可能会小一点。

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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