【LGR-152-Div.2】洛谷 8 月月赛 Ⅲ &「TAOI」Round 2 T1 题解
include13_fAKe
·
·
题解
题意
给定正整数 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。
正确的序列可以是 $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}$**。不然也有可能出错。
## 代码
```cpp
#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;
}
```