175 lines
2.7 KiB
Markdown
175 lines
2.7 KiB
Markdown
``` markdown
|
||
1（必做） 最优二分检索树
|
||
Score 100
|
||
给定标识符集 (a
|
||
1
|
||
|
||
,a
|
||
2
|
||
|
||
,…a
|
||
n
|
||
|
||
)，这些字符的下标从1开始按自然序编号，p
|
||
i
|
||
|
||
是对 a
|
||
i
|
||
|
||
成功检索的概率, q
|
||
i
|
||
|
||
是不成功检索的概率, 且 ∑
|
||
i=1
|
||
n
|
||
|
||
p
|
||
i
|
||
|
||
+∑
|
||
i=0
|
||
n
|
||
|
||
q
|
||
i
|
||
|
||
=1，问:它的最优二分检索树是怎样的？
|
||
|
||
输入格式:
|
||
第1行是 n ，表示字符个数。
|
||
第2行是这 n 个字符的成功检索概率p
|
||
i
|
||
|
||
,0<p
|
||
i
|
||
|
||
<1 。
|
||
第3行是失败检索概率 q
|
||
i
|
||
|
||
，0<q
|
||
i
|
||
|
||
<1 。
|
||
保证 ∑
|
||
i=1
|
||
n
|
||
|
||
p
|
||
i
|
||
|
||
+∑
|
||
i=0
|
||
n
|
||
|
||
q
|
||
i
|
||
|
||
=1 。
|
||
|
||
输出格式:
|
||
最优二分检索树先根遍历时得到的字符编号序列。若有多解，输出字典序最小的序列。
|
||
|
||
输入样例1:
|
||
4
|
||
0.1875 0.1875 0.0625 0.0625
|
||
0.125 0.1875 0.0625 0.0625 0.0625
|
||
输出样例1:
|
||
2 1 3 4
|
||
输入样例2:
|
||
5
|
||
0.1524 0.1369 0.0179 0.0007 0.3081
|
||
0.1567 0.1022 0.0682 0.0476 0.0084 0.0009
|
||
输出样例2:
|
||
2 1 5 3 4
|
||
数据范围
|
||
n≤100
|
||
|
||
Code Size Limit
|
||
16 KB
|
||
Time Limit
|
||
1000 ms
|
||
Memory Limit
|
||
512 MB
|
||
Stack size limit
|
||
65536 KB
|
||
```
|
||
|
||
|
||
``` markdown
|
||
2 数列游戏
|
||
Score 100
|
||
一个数列有n个整数。每次从中取走一个最长的递增子数列，最少几次能取走全部的数。递增子数列中，相邻两项可以相等。
|
||
|
||
输入格式:
|
||
第1行，一个整数n，表示数列的项数，1≤n≤10000。
|
||
|
||
第2行，n个整数Ai，用空格分隔，Ai表示数列中第i项，1≤Ai≤1000000，1≤i≤n。
|
||
|
||
输出格式:
|
||
第1行，一个整数，表示第一次取走的最长子数列的项数。
|
||
|
||
第2行，n个整数，用空格分隔，表示第一次取走的最长子序列。如果有多种选择，输出最靠左的一组。
|
||
|
||
第3行，一个整数，表示所求最少次数。
|
||
|
||
输入样例:
|
||
在这里给出一组输入。例如：
|
||
|
||
8
|
||
10 9 2 5 3 7 101 18
|
||
|
||
输出样例:
|
||
在这里给出相应的输出。例如：
|
||
|
||
4
|
||
2 5 7 101
|
||
4
|
||
|
||
```
|
||
|
||
|
||
|
||
``` markdown
|
||
3 演讲大厅安排
|
||
Score 100
|
||
有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。
|
||
我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使
|
||
演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。
|
||
请计算演讲大厅最大可能的使用时间。
|
||
|
||
输入格式:
|
||
第一行为一个整数 N，N≤5000，表示申请的数目。
|
||
|
||
以下 n 行每行包含两个整数 p，k，1 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。
|
||
|
||
输出格式:
|
||
一个整数，表示大厅最大可能的使用时间。
|
||
|
||
输入样例1:
|
||
5
|
||
0 3
|
||
2 6
|
||
5 7
|
||
1 5
|
||
5 9
|
||
输出样例1:
|
||
8
|
||
输入样例2:
|
||
12
|
||
1 2
|
||
3 5
|
||
0 4
|
||
6 8
|
||
7 13
|
||
4 6
|
||
9 10
|
||
9 12
|
||
11 14
|
||
15 19
|
||
14 16
|
||
18 20
|
||
输出样例2:
|
||
16
|
||
|
||
``` |