A. Knapsack
猜个结论——先把所有的东西加起来，如果小于 (frac{1}{2}m) 就输出不合法；如果在 ([frac{1}{2}m, m])之间直接全部输出；若大于 (m)，那就想办法把他减到 (m) 以下并且大于等于 (frac{1}{2}m)，那么问题就转化为了求序列减完以后大于等于 (frac{1}{2}m) 的情况下的最小值。那我们排个序，从大到小循环，把当前能减的都减掉就是了。
for (int i = n; i; i--)
{
//fout << '$' << p[i] << ' ' << a[p[i]] << ' ';
if ((sum - a[p[i]]) * 2 >= W)
{
sum -= a[p[i]];
used[p[i]] = false;
}
}
B. Catching Cheaters
又是一个巧妙的序列 DP。设 (f_{i,j})表示 (a) 中选出的子段以 (i) 结尾、(b) 中选出的子段以 (j) 结尾的最大相似值。为什么可以这么设状态呢？因为我们根本不关心前面是什么样子的，我只想知道截止 ((i-1,j-1)) 这个位置的最大相似值，并且这个东西满足最优子结构。状态转移方程：
[f_{i,j} = max{0, f_{i-1,j}+1, f_{i,j-1}+1, f_{i-1,j-1}+4[a_i==b_j] - 2}
]
这个东西思考起来很困难，因为总感觉这个和两个序列所选段的起始点有关；仔细想想，其实是无关的。
C. Xor Tree
假设留下了 (k) 个点，则一共 (k) 条边，要构成一个可以有重边的树，那么它合法当且仅当这个重边唯一，即 (j) 是 (i) 要找的点且 (i) 是(j) 要找的点，这样的点对唯一。
最少扣掉几个数转化为最多留下几个数。把原序列搞到 0/1 Trie 上，设 (f_x) 表示 (subtree(x)) 中最多留下几个点。如何转移？我们发现，若它的其中一颗子树的 (size > 1)，那么这颗子树一定是自己内部全连完；若它两颗子树的 (size_1) 都大于 1，那么这颗树就断开了。所以状态转移方程为 (f_x = max(f_{ls},f_{rs})+1)，若只有一个孩子就直接等于。可以证明这样是充分必要的。