Codeforces 19xx 合集

CF1974

• A. Phone Desktop

每个手机只能填两个大的，先把大的填完，然后剩下的地方用小的补上，最后小的不够用了再拿新的手机。

• B. Symmetric Encoding

直接模拟吧。

• C. Beautiful Triple Pairs

一个比较好写的做法，是先不管那个不同的，把所有存在两个相同的都加上，最后减去三遍三个都相同的部分。

• D. Ingenuity-2

写起来有点细节。先只考虑一种方向（比如南北），显然必须是两者数量同奇偶才有答案，构造的话来回选 R、H 就好了。然后换一种方向的时候，把 R、H 的优先级调换一下顺序写起来会好受一点。

• E. Money Buys Happiness

看到这个数据范围就想 dp 了吧，\(dp_{i,j}\) 代表幸福度为 \(j\) 的最大钱数，转移先看能不能减，然后最后别忘了全体加上最后的收益。

• F. Cutting Game

维护两个方向的平衡树，然后删的时候如果已经被删过了就不计入答案，每个点最多被删两次，均摊复杂度正确。

• G. Money Buys Less Happiness Now

注意这里幸福度的收益是一样，所以直接按从小到大的顺序贪心的去取肯定是最优的，那么用数据结构（线段树）维护一下这个过程就好了。