总结

今天是正月初五啦，迎财神！恭喜发财！

废话不多说，今天是和 nfls 一起考的，已知两道题是原题。今天发挥稳定，感觉如果再加把劲能做出来第一题。第三题思路很巧妙，如果不说感觉想不出来。

题解

先上链接：NOI2024省选模拟赛34 。

A. duyi 的切题树

原题是 CF750F。这道题的限制比原题更加严格。就是一个满二叉树，每次询问一个编号的点会给出它相邻的所有点的编号，层数最多 12，让你在不超过 50 步问出来。

第一步是找一个点延伸出两个叶子，那么 lca 就一定是中间的点。然后结果这一步我没有想到……我想的是随机几次找到一个叶子……因为这样的概率是一半嘛，结果，后来发现可能会随机 10 次。浪费了很多。主要是不清楚那个性质就是满二叉树叶子的 lca 距离一样。

然后就很方便了，一层一层往上，每个点确定了一个儿子，然后枚举另一个看一下是不是儿子就行，然后一直往上。

这样暴力做的话是，会超，容易发现后面几个太多了可以暴力枚举，因此。会发现超了一个，容易发现枚举到最后剩下的那个一定是根，所以可以再少一个。刚刚好卡满。这里可以有一个小技巧，就是写一个函数间接调用交互库的函数，然后到了了之后不询问直接返回两个大小的 vector 就行了嘿嘿。

B. 红蓝大作战

很有趣的构造题。我的想法和正解有一点不一样。就是一个的方阵，R 和 B 各有个，然后左上角和右下角是一对。然后要求所有 R 两两连边，B 同理，然后要求你给每条边一个方向，让所有向量加起来为 0 向量。

如果是奇数很好做，可以跑欧拉路（据说会 mle，我也不会……），但是可以直接当成多边形来看，我是把在正多边形中所有长度一样的对角线旋转那样来思考的……

然后正解是就是隔离左上角右下角的点，做一个奇数的，然后所有点向这两个点中对应的那个连边就行。容易证明。就是考虑对称。我的思路其实和它差不多，也是有个通过对称思考的步骤，但我考虑的是偶数边多边形对角线正对的两个点会形成几个数对然后给数分组来考虑的，比较复杂。至于为什么我这么想大概是因为我当时忘记左上角右下角的条件了……因此回想起来是必须要至少有一个不同颜色位置中心对称才行，按照我的方法理解就是不这样奇偶凑不上。

C. 发讲义

来自 UR 7，link 。

一颗树，两个人初始从根节点出发，每一步每个人可以选择原地不动或者走向某个儿子。一步后，一个人可以瞬移到另一个人所在节点上。 最少需要多少步，使得每个节点都被遍历过？

。

容易想到错误做法，比如我。然后发现最大样例错了，但是想不出来反例。据说可以拍出来。例子是有毛刺的筷子。建议看官方题解。很好。这里给一份很好的代码博客：blog 。这个人代码写得很清楚，赞b(￣▽￣)d。

后记

不想写，拜拜咯。