P9573 「TAOI-2」核心共振

One-JuRuo / 2023-08-23 / 原文

思路

这道题最开始没发现数列必须是 \(1,2,3,\cdots,n\)，然后直接交了个输出 \(n\) 遍 \(p\) 的代码。~~我真的好蠢啊~~

后面才发现这一点，于是开始思考，首先从 \(p\) 比较小的情况。

如果 \(p\) 是 \(1\) 的话，那显然直接输出 \(1,2,3,\cdots,n\) 就好了。

如果 \(p\) 是 \(2\) 的话，显然奇数和偶数放在一次效果最佳。

如果 \(p\) 是 \(3\) 的话，那 \(3\) 的倍数放一次，余数是 \(1\) 和 \(2\) 交替放在一次最好。

至此，我们便发现了一个大致解法，就是余数为 \(0\) 的应当放在一起，余数和为 \(p\) 的应当放在一起，才能最大化共振次数。

55pts 代码

#include<bits/stdc++.h>
using namespace std;
int T,n,p,t;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&p),t=p;
		if(n==1){printf("%d\n",1);continue;}//当时没想好的时候特判的，后面懒得删了
		for(int i=0;i<p;++i)
		{
			for(int j=0;j*t+i<=n;++j)
			{
				if(!i&&!j) continue;//对于0的特殊情况
				if(i==0||t-i==i) printf("%d ",j*t+i);//余数为0和p/2的情况不需要交替输出
				else
				{
					printf("%d ",j*t+i);
					if(j*t+t-i<=n) printf("%d ",j*t+t-i);//后面一个可能会比前一个少一个，注意判断
				}
			}
			if(i!=0&&t-i!=i)--p;//重复的需要减了（绝对不是我懒得去算到底有多少次）
		}
		puts("");
	}
	return 0;
}

居然 TLE 了，想了一下，我这个第一层最多是 \(p\)，第二层最多是 \(\frac{n}{p}\) 乘起来不就 \(n\) 吗？

一看数据范围，\(\sum n\) 最大也才 \(3\times10^5\) 怎么会 TLE 呢。

就在我百思不得其解的时候，突然看到样例最后一组，\(p\) 比 \(n\) 大，所以共振次数必定是 \(0\)，然后一看 \(p\) 的范围，居然有 \(10^8\)，这样一看，如果每次都是 \(p\) 都比 \(n\) 大，那复杂度就是 \(O(p)\) 了，再乘以个 \(T\)，超时是必然的。

所以循环的时候再加个 \(min(n+1,p)\) 就好了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int T,n,p,t;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&p),t=p;
		if(n==1){printf("%d\n",1);continue;}
		for(int i=0;i<min(n+1,p);++i)//与上面的没什么区别，就这里改了
		{
			for(int j=0;j*t+i<=n;++j)
			{
				if(!i&&!j) continue;
				if(i==0||t-i==i) printf("%d ",j*t+i);
				else
				{
					printf("%d ",j*t+i);
					if(j*t+t-i<=n) printf("%d ",j*t+t-i);
				}
			}
			if(i!=0&&t-i!=i)--p;
		}
		puts("");
	}
	return 0;
}