csp-s 寄了之后回来准备 NOIP 了。

11.3 模拟赛总结

代码源 NOIP 模拟赛 Day 1。

7:29 开赛。T1 感觉是个贪心状物，先排序。猜测必然选择开头段和结尾段，最大值就是枚举开头段末尾 \(i\)，结尾段指针 \(j\) 贪心地往左跳，最小值反之。然后很快过了小样例。不是？大样例呢？那只能在 7:59 提交 T1，然后开始对拍。好像想不到怎么不用这个思路暴力，那就只能用这个思路地暴力取对拍了，肯定拍不出来思路对不对，但是能拍出来实现对不对。没拍出来啥，但是发现数组开小了。

尝试构造数据卡掉贪心，如果最大值极大的话……就错了。考虑选择一些位置达到答案，以最大值为例，小于等于平均值的必然要尽可能左移，这样肯定不劣，大于平均值的聚成一堆好像没啥影响吧。于是猜测必然是选择开头段，钦定其小于等于平均值，双指针做大于平均值的那一段。这样每次双指针是 \(O(n)\) 的，选择开头段是 \(O(n)\) 的，复杂度 \(O(n^2)\)，怎么过不去呀。9:48 提交 T1，期望得分 \(60\) 分。

然后随了几组数据，发现怎么最大值必然形如 \(\frac{x - 1}{x}\)，最小值必然为 \(0\) 或 \(\frac{1}{x}\)。于是猜测不用枚举开头段，只用选择第一个数就行，拍了拍没有任何问题，感觉很真啊。

9:57 提交 T1，期望得分 \(100\) 分。观察 T2，大概十分钟左右观察到了相邻选点必然距离相同且为奇数，肯定是要枚举这个距离 \(d\)。尝试直接 \(dp\)，考虑自己必选的方案数，不太会转移。考虑一旦确定了某个点必选，则每个点是否可选就都确定了。因此每个点向距离自己 \(d\) 的连边建新图，然后去做 DP。考虑找一条长为 \(d\) 的链，枚举上面的点钦定它必选，去 DP，感觉每个点的 DP 是不相交的，于是就是 \(O(n)\) 的，整体来看是 \(O(n^2)\)，实现起来很屎。

写了一个小时后发现假了，因为找到的这个链它可能都不选！尝试补救，做完这个链后删掉它，这样是 \(O(n^3)\)，也有很多分。然后发现不对啊，直接建边是错的，考虑一个点有两个距离自己为 \(d\) 的点，自己选了，它们也选了，这样是不合法的！因为他们之间的距离不可能是 \(d\)！这下坏了，白忙活了一个多小时。

观察 T3, T4，最简单的暴力有 \(15\) 分，先搁着，T2 我会差不多 \(30\) 分，状压和链。写写写，匆匆写完状压，链写完但是调不出来，似乎式子有点问题。

11:49 提交 T2，期望得分 \(15\) 分。重推了一遍式子，然后赶紧写，终于过样例了，跳转到浏览器界面发现倒计时剩 \(3s\)，赶紧交。哈哈哈哈哈哈没交上。第三次发生这样的事件，第一次是某场 abc 的 F，第二次是某场代码源 csp-s 模拟赛。

出成绩：\(100 + 15 + 0 + 0 = 115\)。如果再给点时间的话是能做到 \(145\) 的。T2 考虑连接所选点的最小子树，里面度数为 \(1\) 的叶子必选（不然不符合最小子树），\(\ge 3\) 的点必选(否则，从它的三个不同方向，各取一个距离它最近的所选点，就会构成上面所说矛盾的三元组)，于是删除的点只能度数为 \(2\)。还是考虑自己必选的方案数，设为 \(dp_u\)，于是距离它为 \(d\) 的子树内节点里，处于 \(u\) 同一个儿子的子树内的只能选择一个，于是有 \(dp_u = \prod\limits_{s \in \operatorname{son}(u)} (1 + \sum\limits_{v \in \operatorname{subtree}(s), \operatorname{depth}(v) - \operatorname{depth}(u) = d} dp_v)\)。

这个可以 \(O(n)\) 转移。考虑答案，钦定这个子树的最高点必选时，就是 \(\sum\limits_{u} dp_u\)。钦定最高点不选时，它的度数必然为 \(2\)，找到其左右儿子最高的必选点 \(u, v\)。因此，可以把上述 \(dp\) 改为 \(dp_{d}(u)\) 表示枚举到 \(d\) 时的方案数，全部求完后，枚举点对 \(u, v\)，要求不存在祖先关系，贡献 \(dp_{\operatorname{dis}(u, v)}(u) \times dp_{\operatorname{dis}(u, v)}(v)\)。