自动搬运

查看原文

来自洛谷，原作者为

	David_yang 没有一根棒棒糖解决不了的事情，如果有，就再来一根

搬运于2025-08-24 22:34:38，当前版本为作者最后更新于2024-01-31 16:47:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

第四篇题解，如有不妥请忽视指出。

题目大意：

构造一个长为 $n$ 的序列，使它的 LIS 或 LDS 刚好等于 $k$。

算法：

一道思维题，没有算法。

解析：

首先来判断无解的情况。不难发现，当 $k^2<n$ 时是不行的。举几个栗子：当 $n=6$，$k=2$ 时，构造出 5 6 3 4 1 2，LIS 是满足了，但 LDS 不行。我最开始想了一个序列：1 1 1 1 1 2。但是，如果这样可以，那么样例 $1$ 是不是可以构造成 1 2 3 3？可是实际情况是这样：https://www.luogu.com.cn/record/145160568（我还是加了这个特判的）。

所以，你现在知道为什么 $k^2<n$ 时是不行的了吧。

然后再来看看有解的情况。我这里就提供一种构造方法：我们分成 $n \div k$ 轮，每轮输出 $k$ 个连续的数，从 $n-k+1$ 开始。每轮完后，$n$ 减去 $k$。最后是不是还有剩下的？只要从 $1$ 开始把剩下的输完就可以了。

听起来有点抽象，我这次举个桃子：比如 $n=17$，$k=5$。第一轮输出 13 14 15 16 17，第二轮输出 8 9 10 11 12……最后是不是还剩下了一个 $1$ 和 $2$？直接输出就好了。就像是每次看起来马上就要超了，结果突然“柳暗花明又一村”。最后一看 LDS，也没有超。这也是为什么 $k^2<n$ 时是不行的原因，超过 $k$ 轮后，LDS 也要超。

现在解释的差不多了，最后提醒一句：不开 long long 见祖宗！

Code:

#include<bits/stdc++.h>
using namespace std;
long long n,k;
int main()
{
	scanf("%lld%lld",&n,&k);
	if(k*k<n)						//特判k*k>n的情况
	{
		printf("-1");
		return 0;
	}
	for(int i=n;i>=k;i-=k)			//分为n/k轮
	{
		for(int j=k;j>=1;j--)		//每轮输出连续k个数
		{
			printf("%lld ",i-j+1);	//从n-k+1开始
		}
	}
	for(int i=1;i<=n%k;i++)			//剩下的从1开始输完
	{
		printf("%lld ",i);
	}
	return 0;
}

注：代码已 AC，请放心食用。

最后：浏览过看过也要赞过！