9.11 模拟赛（炼石计划 11 月 05 日 NOIP 模拟赛 #17）

炼石计划 11 月 05 日 NOIP 模拟赛 #17【补题】 - 比赛 - 梦熊联盟 (mna.wang)

概况

预计 \(50+[20, 36] + 20+10 = [100,116]\)。

实际 \(35+36+20+0=91\)。挂飞了/qq

最后补题 \(50+100+20+10=180\)。T2 用 std 跑了较大数据终于找到了规律！！！T1 是笛卡尔树的高级应用，于是先学一手笛卡尔树。第三题听不懂讲解，第四题前置知识都没学过直接放弃。

复盘

逆风局。

读完题后先写了 T2 的爆搜。本来想靠它输出的结果找规律然后推正解，但是搜索很不优秀，只能跑 \(n \le 5\) 的数据。规律啥也看不出来。

爆搜调了很长时间终于对了。先让它跑 \(n = 6\) 的数据，往后看题。

实际上等了很长时间后它也没跑出来。于是直接把 exe 关了。靠爆搜找规律的思路暂时放弃。

T1 的 \(50\) 分是极易的。但是剩下的 \(50\) 分看起来不太好做。想到点分治（？）但是当时没学会。题解里确实有提到这个做法但是不是 std。想了一会就放弃了。先写前 \(50\) 分。

写了三个 namespace，分别是暴力、链和菊花。变量名能重复真的很强！很快过了题目给的所有样例。很不幸这些数据中没有菊花图的情况，于是赛后发现菊花的挂了/ll /ll

挂的原因有二：*max_element(d + 1, d + n + 1) == n + 1 和 long long。

T3 极其神秘。幸亏想到了欧拉路径可以用度数来判，得了 \(20\) 分。想不到可能 \(10\) 都拿不了，因为最暴力的搜索并不好写。

T4 大数学题。先跳。这是一个明智的选择。

重新做 T2。程序跑不出我人脑模拟还不行！

用了一点时间手模出了 \(n \in [5,8 ]\) 的情况！快膜拜我。但还是没有什么规律。检查了一下改了几个错误，其中最严重的错误是 \(n = 6\) 的第一行输出不对。改过来后很快发现了第一行的数的规律 \(\lfloor \frac n2 \rfloor \times \lceil \frac n2 \rceil\)。算了一下最多能拿 \(20+80 \times 20\% = 36\) 分，最少 \(100 \times 20\% = 20\) 分。感觉还不错。

快结束了，先不写 T2 正解了。最后一会时间写了 T4 的 \(10\) 分，但挂 \(0\) 了。

总结

好的：

• T1 用了 namespace 数据分治。这样写不容易犯错。
• T2 手模的 \(n \in [5, 8]\) 的数据都对了。这代表模拟的时候真的很有耐心。
• 果断跳了 T4。因为它远超我的能力。

不足：

• T1 判菊花判错了。
• T1 没开 long long。这两点挂了 \(15\) 分。
• T2 上来写了复杂度极假的爆搜。以后即使写打标的爆搜也要算好时间复杂度。\(2^{114514}\) 的复杂度一定别写。
• 时间分配出了问题。T2 如果按照手模出的 \(n \le 8\) 的数据再找一段时间规律应该能做掉。

知识点

• T1：单调栈，笛卡尔树。

• T2：找规律。

• T3：树。

• T4：数论。

题解

A. Imbalance

链的做法可以 P6510 奶牛排队 的单调栈 + 二分。介绍一种笛卡尔树的做法。

我们建一颗小根堆笛卡尔树。显然在 \(u\) 是其子树中的最小值。

那么对于其子树中的任意一个点 \(v\)，区间 \([u, v]\) 的最小值一定是 \(a_u\)。

同理我们再建一颗大根堆笛卡尔树。对于 \(u\) 的子树中的任意一个点 \(v\)，\([u, v]\) 的最大值一定是 \(a_u\)。

问题就转化成了：有两棵树，求有多少 \(u, v\) 满足两棵树中都满足 \(u\) 是 \(v\) 的祖宗或 \(v\) 是 \(u\) 的祖宗。

\(4\) 种情况分类讨论。子树可以用 dfs 序转化。于是就变成了一个二维数点。

代码非常难写。

B. 原子

找规律。证明过于抽象。

C. 旅行计划

注意到原问题等价于从树上删除一些边，使得图中存在欧拉路径。而欧拉路径可以通过求有多少点的度数为奇数来判断。这样暴力能得 \(20\) 分。

D. 简单题

真 · 简单题。

不会。