某岛

… : "…アッカリ~ン . .. . " .. .
December 2, 2022

Codeforces Global Round 24

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() 求最大生成树(因为单调性恰好是反的)就可以得出树的结构,再简单冗斥就可以得出边权。
也可以反过来先用冗斥直接得出距离函数,再用距离函数求最小生成树即可得到树的结构,参考 这里

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