题解 CF1205A/1206C 【Almost-Equal】

发表于 更新于 阅读次数： Waline：
CF1205A/1206C 【Almost-Equal】题解。

其实这个题就是个结论题=-=

然而我比赛的时候还是想了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$为偶数时不满足。

好像我的证明过程一样没啥卵用

于是给出代码：

1
2
3
4
5
6
7
8
9
10
11
#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]);
}