题解：P14127 [SCCPC 2021] K-skip Permutation

a_gold_TomAndJerry · 2025-10-05 14:35:50 · 题解

第一次写 SJ，写得不好请见谅。

要使得 f(P,k) 最大，即要使 P 中公差为 k 的等差数列个数最大。

代码实现方式类似于埃氏筛。即从 1 开始以 k 为公差进行构造，直到无法构造为止。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,k;
bool a[maxn];
vector<int> ans;
int main(){
    memset(a,0,sizeof(a));
    scanf("%d%d",&n,&k);
    int h=1;
    while(h<=n){
        if(!a[h]){
            ans.push_back(h);
            for(int i=h+k;i<=n;i+=k){
                ans.push_back(i);
                a[i]=1;
            }
        }
        h++;
    }
    for(int i=0;i<ans.size()-1;++i) cout<<ans[i]<<" ";
    cout<<ans[ans.size()-1];
    return 0;
}