admin管理员组文章数量:1584444
题意:
给定长度为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://m.elefans.com/dongtai/1727942470a1139050.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论