ADS题目选析

实际上摊还时间由我们的势能函数决定。我的逆天势能函数可以让摊还时间变得无比大。

很有意思的一道题。大意是这样的：对于 Activity Selection Problem （如果是高中打OI的选手可能更喜欢叫它：线段覆盖[ac01]），我们给出一种比较差的贪心做法 SF ，它每次贪心地挑出与当前安排不冲突的活动中占用时间最短的一个活动（也就是最短的线段）。题目给出一种证明它是 2-approximation 的方式，让我们判断这个证明对不对。
它的证明思路是这样的（把题目原本的描述稍微形式化了一下）：我们试图构造一个从最优解 OPT 中挑出来的活动到 SF 贪心做法挑出来的活动的映射，使得对于最优解 OPT 中的活动都对应至少一个 SF 中的活动，而 SF 中的活动最多对应 OPT 中的两个活动。假设我们真的找到了这样一个对应方式，那么 2-approximation 就是比较显然的了。
这个对应方式是这样的，对于 OPT 中的一个活动 ai ，假如在 SF 中也有这个活动 ai ，那么我们就从 OPT 中的 ai 对应到 SF 中的 ai ；假如 SF 中没有这个活动 ai ，那么一定至少有一个活动 aj 和它冲突。不然的话没有任何一个活动和 ai 冲突，那 SF 应该会把 ai 挑进来的。我们就从 OPT 中的 ai 对应到 SF 中的 aj 。
显然，最优解 OPT 中的活动都对应至少一个 SF 中的活动。那么为什么 SF 中的活动最多对应 OPT 中的两个活动呢？因为我们考虑，假如 SF 中的 aj 对应了 OPT 中的三个活动 a1, a2, a3 ，那么 a1, a2, a3 中至少有一个活动是被 aj 完全包起来的（就是占用的时间区间 aj 是它的超集），因为 aj 这个活动的两个端点只会在 a1, a2, a3 中的某两个里，那么剩下的那个肯定就是被 aj 包裹起来了。为什么包裹起来不行呢？因为我们这个 SF 贪心每次选取的是能放进去的时间最短的活动。那么被 aj 包裹起来的那个活动显然时间更短，在 SF 安排 aj 的时候应该优先安排那个小活动才对。
综上，这个是对的。

如果有过竞赛经历的同学估计对矩阵快速幂并不陌生。我们都知道快速幂的复杂度是 logn ，但是这道题比较让人疑惑的事情是，我们实际上计算 本身我认为就不可能是 logn 的。我们都知道，朴素的乘法从算法的角度上说复杂度是 O(k^2) 的，这里 k = 这个数的位数。如果使用快速傅里叶变换可以做到 O(klogk) 。当然，我们的硬件层面实现可以让乘法本身是一个 O(1) 的操作，但是这里讲求渐进复杂度，n 可以是任意大，肯定不能当做是硬件可以直接算出来的规模。

这个题做错了，出来之后杨洋老师问我考的如何，我只能讪讪一笑… 对于这种 full binary tree 的定义，我一向搞不清楚。这里，full 指代的是要么没有儿子要么有两个儿子。

讲到选择题了，吐槽一句：我怎么抽到这么多错题！而且最后没多少时间才改正！搞得我心态炸裂，还浪费时间。稍微验一下题，这种很基础的数据结构模拟题就不至于题出错吧………

对于第一个 statement ，我们发现如果一个钱不是 5 的倍数，那么不管怎么凑，总之需要一些个 1 块钱来把它变成 5 的倍数。所以我们直接只考虑钱数是 5 的倍数的情况。既然面值和目标钱都是 5 的倍数，我们直接让它们都除 5 。这样就相当于用 1, 3, 5 去凑钱。总共才三个变量反证法随便假设一下就行了。
对于第二个 statement，从直觉上想就觉得非常对。给一个简单的证明：首先我们先证明，最优解不可能让某个面值用大于等于 c 次。这很显然，如果用了大于等于 c 次，直接让它变成更大一级的面值就行。有了这个结论之后，我们知道一个数它的 c 进制肯定是唯一的。所以这个问题就解决了，我们的贪心显然就相当于把目标钱数转化为 c 进制，假设贪心不是最优解，而最优解又不可能让某个面值用大于等于 c 次，说明最优解也是一种目标钱数的 c 进制，发生了矛盾。
对于第三个 statement，显然错。构造很简单，面值为：9，4，1，目标钱数为 12 。

经典算法题。可见：https://blog.csdn.net/beiyeqingteng/article/details/7533304。百度一下可以搜到很多。
即便我们不知道这个算法，也可以通过简单的判断知道这个复杂度不应该和 n, m 有关系。因为前 k 个数字只需要两个数组的分别前 k 个就够了。

碎碎念：把 C 算出来之后比较激动，觉得 C 非常对，完全忘记了这个题是选 FALSE 。

A. 显然。
B. 对于任何一个 box ，它为空的概率都是 ，根据年久失修的微积分可知这是自然常数 e 的对数 1 / e 。所以 B 也是对的。
C. 这一问很有意思。我们先考虑 A 选项。A 通过期望的线性性很容易得到，但是如果我们根据期望的原始定义来求实际上是不好求的，所以它的期望定义式将会是一个很有用的式子而不是一个显然的式子。具体来说式子是这样的： ，其中 pi 为单个箱子含有 i 个球的概率。那么我们 C 选项要求的东西是什么呢？实际上对于单个箱子，它要求的东西就是这个： 。为什么呢？因为假如这个箱子里没球，那就 reject 0 个球；其他情况下，箱子里有 i 个球，就会 reject (i - 1) 个球。简单观察可以发现这两个式子非常相似，实际上：
这个时候大家应该就能感受到了，减号前面正是 A 选项中的那个式子，所以它等于 1 。所以：
。
所以 C 也是对的。
D. 看着就很错。它相当于是说把所有原本球数大于等于 2 的情况全部变成了等于 2 。所以单个 box 球数等于 2 的概率就是除去等于 1 和等于 0 的概率。这两个概率都很好算，总之算出肯定不是 1 / e 。

此题不难，刚看到的时候比较疑惑为什么 size(T) 要除掉 3 ，然后再在前面乘个系数来抵消开销，感觉多此一举。想了一下，原来是为了保证势能函数最后一定是非负数，我鲁莽了。虽然课本和PPT要求势能函数必须是非负数，但是势能函数最后是负数其实没有太大的关系。我们通过加常系数、乘常系数的方式必然可以把势能函数变成非负数。

这道题思考的时间比较短，发现 C 可行之后就跑了。此时回看，感觉 A D 的反例好像不是很好构造。这个日后填坑。
A. 挖坑待填
首先 B 肯定是错的。因为度数的和不会有变化的，都是一棵树，必然没变化。
然后 C 肯定是对的。这个 3 的幂的作用在于 w 的度数是比较大的，所以它的邻接边被砍掉是很痛的，它度数减少 1 ，势能函数就会减少 ，而我们知道 u 和 v 的度数的较大值加 1 都没有 w 的度数大，所以它们的度数增长对于势能函数的增长最大是： 。所以增长没有减少多，势能函数是严格降低的。
D. 挖坑待填。

没有想法，完全不知道该怎么做 [ac07]

希望近期能把 张国川 老师那道完全没思路的题填了，再把最小度数生成树的两个构造填了。

完结撒花。