CF1818B Indivisible 题解

lgydkkyd · 2024-02-24 14:06:23 · 题解

将这道题之前先给大家普及一下高斯求和公式：求 x+(x+1)+(x+2)+...+(y-1)+y 的和可以转化成 \lfloor (x+y)\times(y-x+1)/2 \rfloor。

然后进入正文，看完题目后可以得知，本题是一道构造题，还是大家最熟悉的分类讨论，当 n 为一时，该序列只能为一这一个数，当 3\le n 且 n 为奇数时，本组数据无解，原因如下：题目明确要求对于任意 l 和 r 满足从第 l 项至第 r 项的和不为 r-l+1 的倍数，那么当 l 为一，而 r 为 n 时，第 l 项至第 r 项的和为 \lfloor (1+n)\times n/2 \rfloor ，如果 n 为奇数，则所有项之和一定为 n 即 1+n-1 的倍数，则无解。

剩下的情况就是 n 为偶数，无论 l 和 r 的奇偶性是否相同都存在合法解，于是开始构造序列，当 i 为奇数时输出 i+1 否则输出 i-1。

Code

#include<bits/stdc++.h>//万能头最好啦 
using namespace std;
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){//t组数据 
        scanf("%d",&n);//输入n 
        if(n==1){//特判当n为1时 
            printf("1\n");//该序列只能为1 
        }
        else if(n%2==1){//当n为大于1的奇数时 
            printf("-1\n");
        }
        else{//n为偶数时 
            for(int i=1;i<=n;i++){
                if(i%2==0)printf("%d ",i-1);//i为偶数 
                else printf("%d ",i+1);//i为奇数 
            }
            printf("\n");//换行 
        }
    }
    return 0;//华丽结束~~~ 
}