Problem A. 字体设计

做法一：RMQ


首先 a[1] 肯定需要选择。

。。设当前选择的元素为 l。。。考察下一个要选择的元素。。

分两种情况讨论。。

如果。。a[l] < a[l+1]。。
。。那么找到 a[l] 右边第一个比 a[l] 小的元素 a[x]。。。。下一个选择的元素是 (l, x) 之间的 max rmq。。

如果。。a[l] > a[l+1]。。
。。情况类似。


rmq 可以用 O(nlogn) 预处理，O(1) 询问。。。
找右边比某个数小的第一个元素，可以用 rmq + 二分 O(nlogn)。。
也可以单调队列 O(n)。

如果 rmq 用 O(n) 预处理，O(1) 那么复杂度为 O(n)。

做法二：贪心 + 递归

设当前递归区间为 [l, r]，最大的最小的显然必须选择。
设他们的坐标是 ll, rr。。(ll < rr)
。。。[ll, rr] 显然已经合法。。
那么之后 [l, ll] 和 [rr, r] 是结构相同的子问题，递归处理即可。
复杂度 O(n)。


Problem B. 开锁魔法III

组合数学 + 动态规划 

为了使得可以打开所有盒子，必须每个循环中至少存在一个元素。
因此只要预处理出每个循环的长度。。按照循环划分阶段。。
dp[i][j]：表示当前已经处理了前 i 组循环，一共分配了 j 个初始钥匙时的概率即可。

Problem C. 与链

考察每个位，一定是 111111000 这种模式。。

考虑数位 DP。。

Int f(int n, int o)

表示 [0, n] 位处理完毕，第 n 位的进位为 o 时的方案数。。
枚举这个位上 1 的数目，计算需要多少位进位。。。

最后返回 f(63, 0) 即可。