P7957 tj

David_yang · 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，请放心食用。

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