admin管理员组

文章数量:1584610

题意：

给定长度为n的字符串,由0,1,?构成,
给定x,每x个相同的0或者1可以计算一次贡献,
假设x为3,串为000000,那么贡献为2,也就是说不可以重叠.
'?'位置可以指定0或者1,问对于这个x,这个串的最大贡献是多少.
对x=[1,n]都计算一次答案.

数据范围：n<=1e6

解法：
令pre[i][0/1]表示i左边第一个0/1的位置(包括i)
如果s[i]=='?'的话pre[i]继承pre[i-1]
对于s[l,r]
如果pre[r][0]==pre[l-1][0],说明整个区间内全是1或者?
如果pre[r][1]==pre[l-1][1],说明整个区间内全是0或者?
说明这个区间满足条件

对于每一个x,考虑从左边到右边一直暴力判断,
如果[l,l+x-1]满足条件,则对答案产生贡献,左端点l+=x

如果不能跳成功呢?
那么就要从[l,l+x-1]中找到一个新的起点l,从这个新的起点开始跳.
如果串为0101,那么应该从最后一个1的位置开始继续判断
如果串为0111,那么应该从第一个1的位置开始继续判断
其实就是从右端点r=l+x-1开始,找到一个位置p,满足[p,r]中0和1不同时出现
那么p=min(pre[r][0],pre[r][1])+1,
那么[p,l+x-1]这一段一定都是?和一种数,这种数要么是0要么是1

复杂度分析:
只考虑x>=2的情况:
1.如果区间满足条件,l+=x,左端点移动x格
2.如果区间不满足条件,l=p(p的定义看上面)
区间不满足条件的时候,说明区间内既有0又有1
最坏情况下是0111,左端点会跳到第一个1的位置,只移动了一格,
当x=2,串=010101010101的时候,复杂度为O(n)
但是当x=3的时候,011这种串第一次只移动一格,那么下一次一定至少移动两格.
显然两次连续的移动,至少移动x格,复杂度小于2*logn
当x>3的时候和x=3的情况差不多
综上:除了x=1和2的情况,一趟的复杂度是O(log)的,整个程序总复杂度为O(n*logn)

ps:
找前面一个0或者1也可以用并查集找前驱的方法
code：
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e6+5;
int pre[maxm][2];//pre[i][0/1]表示i左边第一个0/1的位置(包括i)
char s[maxm];
int a[maxm];
int n;
signed main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        if(s[i]!='?')a[i]=s[i]-'0';
        else a[i]=2;
    }
    for(int i=1;i<=n;i++){
        pre[i][0]=pre[i-1][0];
        pre[i][1]=pre[i-1][1];
        if(a[i]==2)continue;
        pre[i][a[i]]=i;
    }
    for(int x=1;x<=n;x++){
        int l=1;
        int ans=0;
        while(l+x-1<=n){
            int r=l+x-1;
            if(pre[r][0]==pre[l-1][0]||pre[r][1]==pre[l-1][1]){//[l,r]为1和?,或者[l,r]为0和?.
                ans++;
                l=r+1;
            }else{//如果不满足,则找新的起点
                l=min(pre[r][1],pre[r][0])+1;
            }
        }
        printf("%d ",ans);
    }
    return 0;
}

本文标签： 复杂度暴力ControversialRounds

版权声明：本文标题：Codeforces1398 F. Controversial Rounds（暴力，预处理，复杂度分析） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1727942470a1139050.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。