• https://codeforces.com/contest/1764
• https://t.me/algorithm_daily_of_minako/7665

Problem D. Doremy’s Pegging Game

总之很像是 上一场的 D 题。。也是需要枚举一些东西的组合计数。。。
先枚举最后剩下的角度，再枚举这个角度中间还剩几个即可，最后记得讨论一下奇偶。

Problem E. Doremy’s Number Line

首先如果 x 能被染色，那么 x-1 也一定能被染色，因此我们只要求出能够构造出的最大值，并和 k 做比较即可。
那么显然我们有平凡下界 a[0] 和平凡上界 a[0] + b[0]，这是因为我们最后一步必须染 0。

现在我们不考虑 0，看剩下的数最大染色能否到达 a[0]，于是我们归约到了一个子问题，但是这里我们还是有一颗关于排列的搜索树需要处理。
问题的核心就是考察这棵搜索树，寻求剪枝。

我们发现只要根据 a 进行排序，就可以把搜索树的规模优化成 O(n)。
具体看 题解。。。

还有一种做法是按 a+b 进行排序，也可以把搜索树的规模优化成 O(n)。
具体看 这里。。。

利用排序重新组织搜索顺序倒是搜索题的常见剪枝技巧。。。不过这次是直接变成简单贪心。。。
总之看起来很简单。。但是对我来说还是挺难的。。。

Problem F. Doremy’s Experimental Tree

让人想起 #21 的 F 题。。不过这个题其实更容易。。

核心是 f() 函数满足在树中路径包含关系的单调性（四边形不等式？），而树的距离函数也满足这一性质。
因此直接用 f() 求最大生成树（因为单调性恰好是反的）就可以得出树的结构，再简单冗斥就可以得出边权。
也可以反过来先用冗斥直接得出距离函数，再用距离函数求最小生成树即可得到树的结构，参考 这里。

总之题目所给定的信息量是冗余的，做法应该很多。