admin管理员组文章数量:1584640
https://codeforces/contest/1398/problem/F
太神了
从后往前预处理出每个位置向后最远多少个连续的mx[i],然后我们加入a[mx[i]]中,存相同的最多连续相同mx[i]的所有下标
然后用一个并查集维护对于下标idx来说,最近的能走>=x的位置是哪里,然后直接跳到那里,然后idx+=x
处理完x的答案后,我们枚举a[x]中的所有下标,把他们的f[i]=i+1,这个意思也就是下次求x+1的答案的时候,必须跳过这个位置,因为他不能走x+1,由于从小到大处理,所以我们并查集的父节点就是从idx开始跳过所有mx[i]=1...x的位置的下标,然后找到最近的>=x+1的位置,从那里开始连续x+1个然后结束一轮。
#include<bits/stdc++.h>
using namespace std;
const int maxl=1e6+10;
int n,ans;
vector<int> a[maxl];
int f[maxl],mx[maxl];
int dp[2][maxl];
char s[maxl];
inline void prework()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=n;i>=1;i--)
{
if(s[i]=='?')
dp[0][i]=dp[0][i+1]+1,dp[1][i]=dp[1][i+1]+1;
else if(s[i]=='1')
dp[0][i]=0,dp[1][i]=dp[1][i+1]+1;
else
dp[0][i]=dp[0][i+1]+1,dp[1][i]=0;
mx[i]=max(dp[0][i],dp[1][i]);
a[mx[i]].push_back(i);
f[i]=i;
}
}
inline int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
inline void mainwork()
{
int idx;f[n+1]=n+1;
for(int i=1;i<=n;i++)
{
ans=0;idx=1;
while(idx<=n)
{
idx=find(idx);
if(idx>n)
break;
ans++;idx+=i;
}
printf("%d ",ans);
for(int id:a[i])
f[id]=id+1;
}
}
int main()
{
prework();
mainwork();
return 0;
}
本文标签: codeforces1398FControversialRounds
版权声明:本文标题:codeforces1398F Controversial Rounds 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1727942490a1139053.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论