杭电多校第七场 1009 Increasing and Decreasing 题解

题目大意

给你是三个数字$n,x,y$，问你能否构造1~n的最长上升子序列长度为x，最长下降子序列长度为y的序列。

解题思路

这场比赛直接爆零了。。

这个签到题都完全没有思路。。

后面看题解，发现原来有个这个定理。

上升子序列的个数等于最长下降子序列的长度

下降子序列的个数等于最长上升子序列的长度

人都傻了。。

详解点击这里，大佬的博客，偏序集-Dilworth定理。

知道了这个定理，就可以先判断不能构造的条件。

最少的情况是，x-1个下降子序列长度为1，1个下降子序列长度为y，如果$x-1+y>n$，说明数字太多了。

最多的情况是，每个下降子序列长度都为y，如果$x*y<n$说明数字太少了。

由于题目要求字典序要最小，所以越长的应该放在越后面，这个可以用栈来实现。

假设目前需要构造x个下降子序列，最长长度为y。

先判断构造这个y之后，能否满足n能够构造剩下的x-1个最短的下降子序列。

如果可以，则可以进行构造。

如果不行，就需要将y进行减小直到可以构造。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

stack<int> s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n, x, y; cin >> n >> x >> y;
		if (x - 1 + y > n || 1LL * x * y < n)	cout << "NO" << endl;
		else {
			cout << "YES" << endl;
			while (n) {
				if (n - y >= x - 1) {
					for (int i = n - y + 1; i <= n; i++)	s.push(i);
					n -= y; x--;
				}
				else while (n - y < x - 1) y--;
			}
			while (!s.empty()) {
				int t = s.top(); s.pop();
				cout << t;
				if (!s.empty())	cout << ' ';
				else cout << endl;
			}
		}
	}
	return 0;
}