首页 > 其他分享 >【自创题】云梯 题面+题解

【自创题】云梯 题面+题解

时间:2024-09-28 17:12:43浏览次数:8  
标签:垫脚石 unicornFairy 自创 题面 题解 len int 序列 云梯

题目描述

这是晴练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\) ,我们希望其值更小,以有更多机会能拼接数。

因此,我们得到了转移策略:

  1. 找到最大的 \(x\) ,使 \(f_x < a_i\) 。
  2. 将 \(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

相关文章

  • BLE Audio显示连接成功,但没有音乐播放问题解决方案
    背景最近一直在搞这个问题,和原厂一起分析,背景可以参考前面的文章https://blog.csdn.net/Jzj1234555/article/details/142518444?spm=1001.2014.3001.5501https://blog.csdn.net/Jzj1234555/article/details/142595444?spm=1001.2014.3001.5501解决方案今天原厂承认了他......
  • P5165 xtq的棋盘 题解
    这个题也可以用矩阵加速解决。先考虑70pts的做法,我们设\(f_i\)为从\(i\)位置到达\(0\)的期望步数,并尝试用\(f_n\)表示出所有\(f_i\)并利用\(f_0\)解出\(f_n\)然后回带即可。具体地,设\(f_i=a\timesf_n+b\),\(f_{i-1}=c\timesf_n+d\),则由于:\[f_i=pr......
  • Codeforces Round 975 (Div. 2) 题解:D、E
    第一次进前50,上分最爽的一次D.Speedbreaker对\(a\)按照时间升序排序,不难发现,对于升序排序后的数组,当我们搜到时间\(t\)时,记录已经搜过的时间对应原城市编号最小值为\(l\),最大值为\(r\),则我们一定要在\(a_t\)时间之前走过所有\([l,r]\)之间的城市。则若\(r-l+1>a_t\)则无解,因......
  • [USACO22DEC] Breakdown P 题解
    T1[USACO22DEC]BreakdownP比较显然的一点是,一次加一条边/一次删一条边,显然转化,这是显然的一条套路。这题的\(K\le8\),很有意思的数据范围,然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑\(K\le4\)的情况,令\(\mathit{st}\)表示折半搜索中考虑的起点。维......
  • [NOIP2017 提高组] 奶酪 题解
    题目背景NOIP2017提高组D2T1题目描述现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为 z=0,奶酪的上表面为 z=h。现在,奶酪的下表面有一只小老鼠Jerry,......
  • 洛谷P1827 [USACO3.4] 美国血统 题解
    上题目:题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树,并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和......
  • 洛谷P1162 填涂颜色题解
    老规矩上题目:题目描述由数字 00 组成的方阵中,有一任意形状的由数字 11 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 22。例如:6×66×6 的方阵(n=6n=6),涂色前和涂色后的方阵如下:如果从某个 00 出发,只向上下左右 44 个方向移动且仅经过其他 00 的情况下,无法......
  • 题解 HZOJ 284 超市卖货 C/C++
    题目传送门:超市卖货-题目-OnlineJudge(haizeix.com)https://oj.haizeix.com/problem/284思路:每次寻找价格最高的商品,并尝试卖掉它:寻找未卖出商品的日期,优先锁定其保质期最后一天,若该日期已卖出则继续向前寻找能找到未卖出商品的日期时,收入增加,标记该日期代码实现:为......
  • Echarts图表知识点汇总及请求django服务器后端跨域问题解决
    1.引入echartsvue3中通过npm引入:npminstallecharts--saveimport*asechartsfrom'echarts';//基于准备好的dom,初始化echarts实例varmyChart=echarts.init(document.getElementById('main'));//绘制图表myChart.setOption({title:{text:'ECha......
  • P9019 [USACO23JAN] Tractor Paths P 题解
    P9019[USACO23JAN]TractorPathsP题解难度其实绝对不止蓝题。先考虑第一问。维护任意两点之间的最短路是困难的,难以dp或是采取其它方法解决。难以算最短路就转换思路,考虑从\(x\)走\(p\)步能走到哪。考虑到这个东西是有单调性的,也就是说对于\(x<y<z\),从\(x\)能走到......