题解 CF1205A 【Almost Equal】
引领天下
2019-08-19 17:20:33
其实这个题就是个结论题=-=
~~然而我比赛的时候还是想了0.5h，还RE了一次~~
我们观察到在环上，**相对的两个数差为1**。
这意味着我们的每次递推必然产生两个数，于是很~~不~~自然的想到%2。
接下来就是大胆猜想不用证明的部分了：
- 观察样例，发现当$n=1$时，则填出的数列为$1,2$，所以可以猜想枚举的过程中$i$&$1$的话则$a_{n+i}=a_i+1$
- 既然$i$&$1$时为$a_{n+i}=a_i+1$，那么为了平衡，另一种情况我们就另$a_i=a_{n+i}+1$
- 观察到样例给出的$n=4$是无解的，手动画图发现$n=2$也是无解的，于是大胆猜想$n$为偶数时都无解。
事实上以上的3条猜想都是正确的。
证明：我们既然要相隔$n$的两个数相差$1$，但是相邻数之和尽可能接近，易证小数和大数间隔放是一种可行策略，而且当$n$为偶数时不满足。
~~好像我的证明过程一样没啥卵用~~
于是给出代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],cnt;
int main(){
scanf("%d",&n);
if(!(n&1))return !printf("NO");
puts("YES");
for (int i=1;i<=n;i++)if(i&1)a[i]=++cnt,a[i+n]=++cnt;
else a[i+n]=++cnt,a[i]=++cnt;
for (int i=1;i<=n*2;i++)printf("%d ",a[i]);
}
```