贪心

P3129 [USACO15DEC]High Card Low Card P

本题贪心的想法很容易想到：设 $f_i$ 表示从 $1$ 到 $i$ 都用规则一赢的最多场数，$g_i$ 表示从 $i$ 到 $n$ 都用规则二赢的最多场数，那么答案就是 $\max(f_i+g_{i+1})$。但是可能会出现一个数 $x$ 在两个地方都被用到的情况，那为什么还是对的呢？因为这样一定有个 $y$ 在两个地方都没出现，那么这个 $y$ 一定可以取代一个地方的 $x$。

CF505E Mr. Kitayuta vs. Bamboos

最大值的最小值肯定用二分求解，那么问题就变成了怎么判定 $m$ 天后 $h$ 的最大值是否小于等于 $mid$。这里用到很重要的技巧：倒着解决问题，因为 $h$ 减少到 $0$ 以下很难处理，因此我们把问题转化为初始时每棵树高度都为 $mid$，每天可以选择一棵树加上 $p$，所有树都会砍掉 $a_i$，需要保证竹子减少 $a_i$ 后不会 $<0$，每次选最快小于 $0$ 的拔高就行了。

CF727F Polycarp's problems

我们发现尽量用正数去填绝对值较小的负数更优，因此我们用堆维护负数贪心地做。然后我们处理出没消完的负数，这些就是留给 $a_0$ 来消的，然后对于每一个询问都二分查找一下就行。

CF746F Music in Car

首先因为是连续的字串所以显然可以用双指针来做，那问题就是加入和删除元素时要怎么操作。我们建立两个 set，第一个存打折的另一个存不打折的，加入一个新元素 $a_r$ 时我们先默认它是打折的，把它加入第一个 set 里，若 set 的大小大于 $m$ 的话我们弹出 set 中最小的元素加入第二个 set 里。删除一个元素 $a_l$ 的话，先判断它在哪个 set 里，这个可以通过比较和第一个 set 的首元素的大小得出，然后再操作。记住删去第一个 set 中元素后要把第二个 set 里最大的补到第一个里。

AT2335 [ARC069C] Frequency

我们发现先以数值大小为第一关键字，下标大小为第二关键字排序之后，$i$ 会被选到仅当前面所有数小于等于 $a_i$，因此排序后我们扫一遍再统计答案就行了。

dp

P3959 [NOIP2017 提高组] 宝藏

首先明确题意：要求构造一棵生成树，使得构造的代价最小，开发一条边的代价为这条边的边权 $\times$ 生成树的深度。看到 $n\leq 12$ 我们可以想到状压 dp，我们设 $f_{S,i}$ 表示选择的点集为 $S$，生成树深度为 $i$ 的最小代价。接下来考虑怎么转移， 我们用 $S$ 的子集 $s$ 来更新 $S$ 的答案，具体来说我们预处理出所有状态能扩展出去的点，然后在用 $s$ 更新 $S$ 的时候，我们枚举 $s$ 能扩展出去的点，在这些中找到边权最小的来更新。

P5020 [NOIP2018 提高组] 货币系统

我们发现一个数不会被用到只当前面的数能组成它，因此我们把 $a$ 从小到大排序然后跑完全背包，尝试用前面的拼出 $a_i$，能拼出的话答案减 $1$。

P4310 绝世好题

首先有个朴素想法：类似于最长上升子序列的 $O(n^2)$ 做法，显然不行，那么考虑换个思路。我们发现 $a$ & $b\ne 0$ 只要 $a$ 和 $b$ 有一位都是 $1$ 即可，那么我们设 $f_i$ 表示有 $1$ 的最高为是 $i$ 的最长子序列长度，直接转移即可。

P5023 [NOIP2018 提高组] 填数游戏

找规律。具体看这篇 博客 吧。

CF605E Intergalaxy Trips

期望 dp。发现正着考虑会不知道到当前位置要走几步，因此我们倒着考虑，设 $f_i$ 表示从 $i$ 走到 $n$ 的最小期望天数。转移的时候，对于一个 $j$，我们会走它当且仅当其他比它小的都没有出现，然后就可以用类似 dijkstra 的方法 $O(n^2)$ 做了。