CodeForces 1253C

65 阅读 0 评论 43 点赞

我是靠谱客的博主哭泣蜜蜂，最近开发中收集的这篇文章主要介绍CodeForces 1253C，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思维题
任意连续n个值的差小于等于1
容易想到分成两个区间，然后奇数时候一区间比二区间大一
偶数相反，然后枚举所有区间
时间复杂度O（n）

ll a[400005];
int n;
map<ll,int>mp1;
void solve()
{
cin>>n;
int cnt=0;
ll num=0;
for(int i=1;i<=n;i++){
if(i&1){
a[i]=++cnt;
a[n+i]=++cnt;
a[2*n+i]=a[i];
a[3*n+i]=a[n+i];
}else{
a[n+i]=++cnt;
a[i]=++cnt;
a[2*n+i]=a[i];
a[3*n+i]=a[n+i];
}
num+=a[i];
}
int k=0;
if(!mp1[num]){
k++;
mp1[num]=1;
}
for(int i=n+1;i<=4*n;i++){
num-=a[i-n];
num+=a[i];
if(!mp1[num])
k++,mp1[num]=1;
}
if(k>2){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
for(int i=1;i<=2*n;i++){
cout<<a[i]<<' ';
}
}
}