LOADING

加载过慢请开启缓存 浏览器默认开启

P14127 [SCCPC 2021] K-skip Permutation 题解

2025/10/8

题目传送门


思路:

首先,不难看出,如果 k > n,那么 f(P,k) 肯定为 0,所以可以随便输出(比如从小到大)。

而 k ≤ n 时,我们可以通过每个数除以 k 的余数进行分类,即除以 k 余数相同的数,两两差 k,要放在一起。而且这样可以 1 到 n 的每个整数恰好出现一次

最后还得注意行末不能有空格


AC code:

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005],tmp=1;
int main()
{
    cin>>n>>k;
    if(k>n)					//0个,随便来 
    {
        for(;tmp<=n;tmp++)
        {
            a[tmp]=tmp;
        }
    }
    else					//按余数来
    {
        for(int i=0;i<k;i++)//余数的可能性
        {
            for(int j=0;j*k+i<=n;j++)
            {
                if(j*k+i>0)
                {
                    a[tmp++]=j*k+i;
                }
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<a[n];				//无空格
    return 0; 
}