自动搬运

查看原文

来自洛谷，原作者为

	include13_fAKe 一路坎坷而来，或将随风而去。

搬运于2025-08-24 22:49:43，当前版本为作者最后更新于2023-08-21 09:04:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给定正整数 $p$ 和 $n$。对于一个排列，我们称其中相邻两项产生「共振」当且仅当这两个数的和为 $p$ 的倍数。

请你构造一个 $1 \sim n$ 的排列，最大化其中产生「共振」的次数。如果有多种方案，输出任意一种即可。

思路

Subtask 1

直接暴力枚举所有可能的排列的情况，并选择「共振」的次数最大的一种方案并输出。

时间复杂度 $O(Tn!)$。

Subtask 2

因为要产生「共振」，且 $p=2$，所以要尽量使奇数和奇数放在一起，偶数和偶数放在一起，使得相邻数之和能够被 $2$ 整除，进而使得产生「共振」的次数最大。

产生「共振」的最大次数为 $n-2$。因为一共有 $n-1$ 个「相邻组」（即相邻两数组成的二元组），而肯定有一个「相邻组」是一边奇数、一边偶数。

例如：$n=9,p=2$ 时

正确的序列可以是 $1,3,5,7,9,2,4,6,8$。

Subtask 3

这个子任务满足 $p=3$。

我们可以将模 $3$ 余 $1$ 的数和模 $3$ 余 $2$ 的数交替着放。最后放能够被 $3$ 整除的数。

不难发现，产生「共振」的最大次数为 $n-2$。

例如：$n=9,p=3$ 时

正确的序列可以是 $1,2,4,5,7,8,3,6,9$。

Subtask 4

推广 $p=3$ 时的做法，就可以得到正解。

我们可以枚举每一个 $i$，保证 $1\le i< \frac{p}{2}$，将模 $p$ 余 $i$ 的数和模 $p$ 余 $p-i$ 的数交替着放。

然后放能够被 $p$ 整除的数。

但是，这里有个大坑点！

若 $2\mid p$，则我们还没有输出模 $p$ 余 $\frac{p}{2}$ 的数。

我们可以发现，两个模 $p$ 余 $\frac{p}{2}$ 的数的和一定可以被 $p$ 整除，所以把它们放在一起，最大化「共振」的次数。

此时，最多可能有 $\lfloor \frac{p}{2}\rfloor$ 个「相邻组」不产生「共振」。

例如：$n=12,p=4$ 时

正确的序列可以是 $1,3,5,7,9,11,4,8,12,2,6,10$。

$n=12,p=5$ 时

正确的序列可以是 $1,4,6,9,11,2,3,7,8,12,5,10$。

但是，这里还有问题！

当 $p$ 足够大时，代码的时间复杂度常数就会非常大。

但是，当 $2n≤p$ 时，「共振」不可能发生。

此时，我们就输出 $1,2,3,4,\dots,n-1,n$ 即可。

（蒟蒻在此处看到自己 TLE on #10，还以为自己是没用快读快写才出的问题，但尝试表明，用了也不能 AC，所以在这里卡了很长时间）

另外，在枚举这些配对的数时，一定要保证它们 $\bm{\le n}$。不然也有可能出错。

代码

#include<bits/stdc++.h>
using namespace std;

int n,p;
inline void solve(){
	scanf("%d%d",&n,&p);
	if(n*2<p){
		for(int i=1;i<=n;i++){
			printf("%d ",i);
		}
		return ;
	}
	for(int i=1;i*2<p;i++){
		for(int j=0;j<=n;j+=p){
			if(i+j<=n)	printf("%d ",i+j);
			if(j+p-i<=n)	printf("%d ",j+p-i);
		}
	}
	for(int i=p;i<=n;i+=p){
		printf("%d ",i);
	}
	if(p%2==0){
		for(int i=p/2;i<=n;i+=p){
			printf("%d ",i);
		}
	}
	printf("\n");
	return;
}
int T;
int main(){
	scanf("%d",&T);
	while(T--)	solve();
	return 0;
}