题目描述
这是晴练P2876云梯的题面。原链接
unicornFairy开始了新的学期。学校换了一个新校长,随之而来的是周五放学的时间由晚上七点半延时到了晚上八点半。unicornFairy认为这很不公平,所以她准备抢先一步回家。晚饭后,unicornFairy来到了一处没有监控的围墙旁。
小马将援助unicornFairy逃出学紫。学校的校长办公室共有 \(n\) 块石砖,小马使用魔法将这些垫脚石按 \(1-n\) 的编号空投至unicornFairy的位置。规定每个垫脚石有一个特征值 \(a[i]\) ,这块垫脚石的长度和 \(a[i]\) 成反比例。unicornFairy需要将它们组成云梯。可惜unicornFairy实在是太娇弱了,她的手上同时只能拿一块垫脚石。对于每块符合要求的垫脚石,unicornFairy可以选择是否将其放在云梯顶端。为了防止云梯倒塌,放上去的垫脚石一定比前一块更长。不要的垫脚石会被立即销毁,防止校长发现。云梯的高度定义为这条云梯上所有的垫脚石的数量。unicornFairy现在很急!她需要一条最长的云梯的所有垫脚石的特征值序列 \(b[i]\),使得垫脚石编号组成的序列的字典序最小。
现在请你帮助unicornFairy写一个程序,求出云梯的最大高度 \(h\) ,并且求出对应的特征值的序列 \(b[i]\)。由于这道题被大佬lzyqwq秒了,现在需要你求出所有组成高度为 \(k\) 的云梯的所有方案数。请注意,每块垫脚石都是不同的,意味着两种方案的云梯形状可能是相同的。方案数对 \(1,000,000,007\) 取模。(详见样例1)
输入格式
第一行,一个正整数 \(n\) ,表示垫脚石的个数。
第二行, \(n\) 个正整数 \(a[i]\) ,表示每个垫脚石的特征值 \(a[i]\) 。
输出格式
第一行,一个正整数 \(h\) ,表示云梯最大的高度。
第二行,共 \(h\) 个正整数 \(b[i]\) ,表示unicornFairy放置垫脚石的方案。
第三行,一个正整数 \(k\) ,表示搭出高度为 \(h\) 的云梯的所有方案数。方案数对 \(1,000,000,007\) 取模。
样例数据
测试用例1
Input:
6
13 3 3 2 4 19
Output:
3
3 4 19
3
样例说明
通过计算可得最大高度 \(h\) 为3, \(b\) 序列为 3 4 19
。
总共有三种方案:
1. 13 3 3 2 4 19
^ ^ ^
2. 13 3 3 2 4 19
^ ^ ^
3. 13 3 3 2 4 19
^ ^ ^
测试用例2
Input:
10
7 2 4 4 9 9 1 0 5 2
Output:
3
2 4 9
6
测试用例3
Input:
50
33 38 39 27 6 41 16 5 39 49 10 37 24 30 19 32 32 30 27 29 12 43 42 20 27 42 11 30 35 7 16 23 18 40 21 17 26 34 4 10 48 44 46 24 33 24 2 45 50 46
Output:
11
6 16 24 27 29 30 35 40 44 46 50
45
数据范围与提示
- 对于数据点
weak1~5
, \(n \leq 20\) 且 \(a[i] \leq 50\) - 对于数据点
6~10
, \(n \leq 100\) 且 \(a[i] \leq 10,000\) - 对于数据点
11~20
,没有额外限制。 - 对于全部数据,保证 \(n \leq 1,000,000\) 并且 \(a[i] \leq 1,000,000,000\)
提示:您可以使用快读降低程序输入常数。
inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
题解
解题思路
这个问题分为两块,一是前面的最长上升子序列模板,二是后面的序列以及方案数。
一、最长上升子序列(模板)
- 采用动态规划。
- 观察数据范围, \(n \leq 500000\) ,因此我们给出的解答是时间复杂度为 \(nlogn\) 的做法。
设 \(f_i\) 表示长度为 \(i\) 的上升子序列的最后一个数字,\(len\) 为 \(i\) 的最大值(即答案)。
设有一组数据为:
\(n = 2\)
\(a = \{1,3,7,2\}\)
则 \(f_1 = 1, f_2 = 2, f_3 = 7, len = 3\)
我们 $i = 1 $ 至 \(n\) 对序列 \(a\) 进行遍历。因为我们需要求最长上升子序列,考虑 \(a_i\) 如何在已有序列后拼接:
\(f_i\) 表示长度为 \(i\) 的序列最后一个数字,那么 \(a_i\) 可能 拼在所有 \(f_x < a_i\) 后面,这时 \(f_{x+1}\) 的值可能为 \(a_i\)。
因为我们需要求最长上升子序列而不是上升子序列,我们的最优选择是:
- 对于 \(f_x < a_i\) ,我们希望 \(x\) 尽可能大。换句话说,每个数拼接到尽可能长的一个序列后。
- 对于 \(f_i\) ,我们希望其值更小,以有更多机会能拼接数。
因此,我们得到了转移策略:
- 找到最大的 \(x\) ,使 \(f_x < a_i\) 。
- 将 \(f_{x+1}\) 修改为 \(a_i\) 。
这样求出的最大的 \(x\) 就是 \(len\) 。
// n
// a[N]
int len = 0;
int f[N];
for (int i = 1; i <= n; i++) {
if (a[i] > f[len]) {
f[++len] = a[i];
} else {
int pos = std::lower_bound(f+1, f+1+n, a[i]) - a - 1;
f[pos] = a[i];
}
}
二、求最靠左的最长上升子序列及方案数
做完所有操作后,我们的 \(f_i\) 中并不是最终答案。因为 \(f\) 仅保证了对于 \(i\) 位置上, \(f\) 所有计算过的值都在 \(a_i\) 后面。
考虑每个 \(f_i\) 。
举一组例子:
\(n = 10\)
\(a = {7, 2, 4, 4, 9, 9, 1, 0, 5, 2}\)
我们记录 \(f\) 为
\(f_1 : 7, 2, 1, 0\)
\(f_2 : 4, 4, 2\)
\(f_3 : 9, 9, 5\)
这样很难看出为什么要记录 \(f_i\) 的变化。进而,我们用角标表示元素在 \(a\) 序列中的位置。
\(f_1 : 7_1, 2_2, 1_7, 0_8\)
\(f_2 : 4_3, 4_4, 2_{10}\)
\(f_3 : 9_5, 9_6, 5_9\)
观察得: \(f_i\) 中的每一个元素都遵循了该元素值不增,元素的下标递增的规律。
我们结合这个性质考虑如何找到一个最长的上升子序列。
我们考虑某一个 \(a_i\) ,假设它在子序列中的位置是 \(p\) ,则需要在 \(f_{p-1}\) 中找一个数拼在后面。要求这个数小于 \(a_i\) 且它在 \(a\) 中的顺序比 \(a_i\) 靠前。这样我们每一个数都能找到一个在它之前的可以拼接的元素集合。
例如第三个 \(4\) 和第四个 \(4\) 都能接在 第二个 \(2\) 后,且第十个 \(2\) 可以接在 \(1_7,0_8\) 后,因此长度为 \(2\) 的上升子序列数量为 \(6\) 。但考虑到最后一位数只取两个 \(4\) 不取 \(2\),最后的答案是 \(6\) 。
寻找两个最值可以使用二分,时间复杂度为 \(log\) 级别,两次操作总共不超过 \(nlogn\) 。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#define N 100010
const int MOD = 1e9+7;
typedef long long ll;
struct node{
int v;
int pos;
node() {}
node(int V, int P) {v = V, pos = P;}
};
int n;
int arr[N];
int len = 0;
std::vector<node> f[N];
int fx[N];
int res[N];
std::vector<int> g[N];
std::vector<ll> sum[N];
bool cmp1(const int &a, const node &b) {
return a > b.v;
}
bool cmp2(const int &a, const node &b) {
return a < b.pos;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
if (len == 0 || fx[len] < arr[i]) {
++len;
f[len].push_back(node(arr[i], i));
fx[len] = arr[i];
} else {
int p = std::lower_bound(fx+1, fx+1+len, arr[i]) - fx;
f[p].push_back(node(arr[i], i));
fx[p] = arr[i];
}
}
for (int i = len; i >= 1; i--) {
if (i == len) {
res[i] = f[len][0].v;
continue;
}
std::vector<node>::iterator it = std::upper_bound(f[i].begin(), f[i].end(), res[i+1], cmp1);
res[i] = it->v;
}
for (int i = 1; i <= len; i++) {
for (int j = 0; j < f[i].size(); j++) {
if (i == 1) {
g[i].push_back(1);
continue;
}
int l, r;
if (f[i][j].v > f[i - 1][0].v) {
l = 0;
} else {
l = std::upper_bound(f[i - 1].begin(), f[i - 1].end(), f[i][j].v, cmp1) - f[i - 1].begin();
}
if (f[i][j].pos > f[i - 1][f[i - 1].size() - 1].pos) {
r = f[i - 1].size() - 1;
} else {
r = std::upper_bound(f[i - 1].begin(), f[i - 1].end(), f[i][j].pos, cmp2) - f[i - 1].begin() - 1;
}
ll s = (r >= l) ? ((l == 0) ? sum[i - 1][r] : sum[i - 1][r] - sum[i - 1][l - 1]) : 0;
s %= MOD;
g[i].push_back(s);
}
for (int j = 0; j < f[i].size(); j++) {
ll s = ((j == 0) ? 0 : sum[i][j - 1]) + g[i][j];
s %= MOD;
sum[i].push_back(s);
}
}
ll s = 0;
for (int i = 0; i < g[len].size(); i++) {
s += g[len][i];
s %= MOD;
}
printf("%d\n", len);
for (int i = 1; i <= len; i++) {
printf("%d ", res[i]);
}
printf("\n%lld", s);
return 0;
}
标签:垫脚石,unicornFairy,自创,题面,题解,len,int,序列,云梯
From: https://www.cnblogs.com/chengxumiao/p/18438165