2020ICPC 南京 K Co-prime Permutation（构造）

题意：
构造一个排列，使得$gcd(i,p_i)=1$的$p_i$数目严格为$k$。

思路：
因为$1$的存在，所以$k$一定不会是0。
因为$gcd(x,x+1)=1$，所以只需要交换相邻两个数就可以使得结果加2。
当$k$为奇数的时候使得$p_1=1$，然后后面的数相邻两个进行交换就好了。
当$k$为偶数的时候从1开始相邻两个数进行交换。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int maxn = 2e3 + 7;
typedef long long ll;

int main() {
    int n,k;scanf("%d%d",&n,&k);
    if(k == 0) {
        printf("-1n");
    } else {
        if(k % 2 == 0) {
            for(int i = 1;i <= k / 2;i++) {
                printf("%d %d ",i * 2,i * 2 - 1);
            }
            for(int i = k + 1;i <= n;i++) {
                printf("%d ",i);
            }
        } else {
            printf("%d ",1);
            for(int i = 2;i <= k;i += 2) {
                printf("%d %d ",i + 1,i);
            }
            for(int i = k + 1;i <= n;i++) {
                printf("%d ",i);
            }
        }
    }
    return 0;
}

最后

以上就是轻松西装为你收集整理的2020ICPC 南京 K Co-prime Permutation（构造）的全部内容，希望文章能够帮你解决2020ICPC 南京 K Co-prime Permutation（构造）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。