Controversial Rounds

admin管理员组

文章数量:1584610

传送门

题意：给你一个长度为你的由0,1，？构成的字符串，你可以选择将？改成0或1，问你构成连续i个的0或1，问你最大能构成多少个，i取1到n。

题解：首先对于每一位置维护出从当前位置往后最多能有多少个连续的0或者1，这一步分可以从前往后dp转移。考虑最暴力的做法，对于每一个i从往后长度大于i的里面选一个大于当前位置的最小id出来，如果能找到ans++，更新当前位置，否则跳出，复杂度n^2,然后考虑优化，后面寻找的过程可以用线段树来进行优化，对于后面查满足条件的最小id在线段树中实际就是大于等于当前区间的满足往后跳转的长度大于i的最小id，以最远跳转长度作为权值，进行建树，朴素情况下就是直接进入优先进入左子树查询，找到答案返回，否则进入右子树，但是这样最坏情况下需要查询线段树的所有端点，考虑优化，思想与传送门相同，记录一个最大值，单次查询为2*long，总复杂度为2*n*log在乘上一个调和级数。

AC代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mid ((l+r)>>1)
#define ls k<<1
#define rs (k<<1)+1
using namespace std;
const int maxn=1e6+5;
const ll inf=1e9;
int read(){
    char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');
    if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')
        x=x*10+c-'0';return x*y;
}
int tree[maxn<<2];
int dp[2][maxn],mma[maxn];
void build(int l,int r,int k){
    if(l==r){
        tree[k]=mma[l];
        return ;
    }
    build(l,mid,ls),build(mid+1,r,rs);
    tree[k]=max(tree[ls],tree[rs]);
}
int query(int l,int r,int wi,int va,int k){
    if(tree[k]<va||r<wi) return -1;
    if(l==r) return l;
    int ans=-1;
    if(tree[ls]>=va&&mid>=wi) ans=query(l,mid,wi,va,ls);
    if(ans!=-1) return ans;
    if(tree[rs]>=va&&r>=wi) ans=query(mid+1,r,wi,va,rs);
    return ans;
}
char s[maxn];
int main( ){
    int n=read();
    scanf("%s",s+1);
    dp[0][n+1]=dp[1][n+1]=0;
    for(int a=n;a>=1;a--){
        if(s[a]=='?') dp[0][a]=dp[0][a+1]+1,dp[1][a]=dp[1][a+1]+1;
        else{
            if(s[a]=='0') dp[0][a]=dp[0][a+1]+1,dp[1][a]=0;
            else dp[0][a]=0,dp[1][a]=dp[1][a+1]+1;
        }
        mma[a]=max(dp[0][a],dp[1][a]);
    }
    build(1,n,1);
    printf("%d",n);
    for(int a=2;a<=n;a++){
        int ans=0,id=1;
        while(id<n){
            int id2=query(1,n,id,a,1);
            if(id2==-1) break;
            id=id2+a;
            ans++;
        }
        printf(" %d",ans);
    }
    printf("\n");
}

本文标签： ControversialRounds