#P16457. 旋律序列工坊
旋律序列工坊
旋律序列工坊
题目背景
音乐程序设计师许言正在制作一套“旋律片段生成器”。一段旋律可以用整数序列表示,而从中按原顺序选出若干严格升高的音符,就能形成一段上升旋律片段。
系统只关心片段本身的数值序列:即使同一段上升旋律能从原序列中的多个不同位置选出,也只会被记录一次;空旋律也会被计入。现在许言希望构造一段尽可能短的旋律,使系统恰好识别出指定数量的不同上升旋律片段。
题目描述
给定整数 ,构造一个整数序列满足其上升子序列种数为 ,你的得分与序列长度相关。注意如果某个上升子序列出现了多次,应只计数一次,空序列算作一个上升子序列。
输入格式
多组测试数据,第一行一个整数 表示测试数据组数,接下来 行每行一个整数 。
输出格式
对于每组测试数据,输出两行:第一行包含一个整数 ,表示序列长度。第二行包含 个整数,表示输出序列。请确保输出的 ,并且序列中的数在区间 范围内。
补充样例
原始样例输入输出文件尚未找到。以下给出本次整理的完整补充样例:三个输出序列的不同上升子序列集合,与原文保留下来的三段解释逐项一致。
3
8
7
10
4
1 1 4 5
4
1 9 8 0
5
1 4 9 0 1
补充样例解释
输出构造并不唯一。下面逐组列出补充样例中的全部不同上升子序列:
对于第1组数据,上升子序列有以下8个:,,,,,,,。需要注意的是, 在序列中出现了多次,但应该只计入一次。
对于第2组数据,上升子序列有以下7个:,,,,,,。
对于第3组数据,上升子序列有以下10个:,,,,,,,,,。
数据范围与提示
。
本题有部分分:对于每组数据,在输出合法的前提下,根据以下表格,你可以获得对应百分比的分数。一个测试点的分数为其下所有测试数据的分数的最小值。
| 输出长度 | 分数 |
|---|---|