[2025线上NOIP联测第三阶段] 模拟赛 1
链接：link
题解：暂无
时间：4.5h (2025.11.08 13:00~17:30)
题目数：4
难度：
| A | B | C | D |
|---|---|---|---|
| \(\color{#52C41A} 绿\) | |||
| *1600 |
估分：100 + 100 + 0 + 0 = 200
得分：100 + 10 + 0 + 0 = 110
Rank：21/44
场祭
读题。
A 签，注意到 \(H \le 100\) 所以直接拆点就行了。
B 大概率是 meet in the middle。但是发现直接两边都爆搜不行，先看左边，考虑维护一个 \(f_{i,S}\) 表示「当前在点 \(i\)，已经经过了公司集合 \(S\)」这个状态是否可达，然后 \(O(2^{n/2}m)\) 转移，思考一下发现可以直接推到右边，因为在右边做的时候就不需要考虑右边没出现的公司了，这样 \(|S|\) 还是 \(O(n/2)\) 级别的，具体地把左边出现过的直接算掉贡献，转移到右边即可，右边再用一个 \(g_{i,S}\) 表示「当前在点 \(i\)，已经经过了公司集合 \(S\)」能匹配的左边最大贡献。
这样可以分成 L-L L-R R-R 三段，复杂度还是 \(O(2^{n/2}m)\)。
开写！因为要维护从左边 \(S\) 到右边 \(S'\) 的映射，所以 L-R 部分并不是很好写。
调了一会儿发现读错题了，改了改只会发现还是读错题了！
死因是公司编号记录的时候出错了，发现并改掉后就只剩下 1h 了。
不过好在大样例确实过了。
看 C，怎么会给数据范围这么小的部分分？\(O(n^3)\) 暴力不是显然的吗？不管了先看看 D，欸似乎可以 dsu on tree 做，思考了下发现换根的复杂度是神秘的 \(O(\sum siz_u)\)，不过足矣过掉菊花图了。能有不少分，开写。
……然后太急了忘了咋维护了！！11
寄。
补题
B 怎么挂完了 /ll
天依宝宝可爱！