E题中线直接取了$\frac{a_1+a_n}{2}$也过了，是数据太弱还是这就是正解哇
2021.3 月赛题解
oxx1108 edited 3 年，9 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先，感谢以下同学为本次月赛命题做出的贡献：
出题人：oxx1108 （A C D E）、ssshwy （B）。
施工大队：Once （题面）、bingoooooooo （A C）、yanghong （D E）
验题人：xryjr233、shirakami_fbk、yaoR、naitir
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。
最后，祝各位 ACMer 和 OIer 们春分快乐，学业有成。
扫描二维码关注我们的微信公众号，获得更多信息。本次月赛的获奖名单和后续竞赛通知将通过公众号发布。
此外，一年一度的“图森未来杯”华东师范大学程序设计大赛暨全国程序设计邀请赛即将在 4 月 10 日举办，欢迎来自全国各地的选手前来参加！
A 读不懂古神语的程序员不是一个合格的探险家
第一次问 $2^n$, $1$ 和 $2^{n-1}$, $2^{n-1}+1$, 可以判断最大值在 $[1, 2^{n-1}]$ 还是 $[2^{n-1}+1, 2^n]$。接着二分问中间相邻两个点，可以缩小一半的区间，每次问两个直到最后剩两个数。
次数开到 $2n+2$ 是给大家各种二分写法一些常数冗余，其实 $2n$ 次也是够的。
可能是有些同学对交互题并不熟悉，在这道题浪费了大量的时间。
B 我想把我的心意叠成小小的一块塞进你的心里
模拟题。可能也算贪心。
其实根本就没有「最优方案」一说，我们遵循「能折就折，直到不能折」的方法，折出来一定是结点数最小的。
这个过程可以 DFS 实现。
具体地，维护树 $T’$ 和指针 $p$。$T’$ 初始时只有结点 $1$，$p$ 指向 $1$。我们在 $T$ 上从 $1$ 开始 DFS。记 $p$ 指向的结点为 $u_p$（$u_p\in T’$）。
在 DFS 到结点 $u$（$u\in T$）时，考虑 $u$ 的儿子 $v$：
- 如果 $u_p$ 存在邻居 $z$ 满足 $w(u_p,z)=w(u,v)$ 且 $a_z=a_v$，那么就让 $p$ 指向 $z$。
- 否则，在 $T’$ 中新建一个结点 $z$，令 $w(u_p,z)=w(u,v)$，令 $a_z=a_v$，然后让 $p$ 指向 $z$。
然后对 $v$ 进行 DFS。DFS 完了 $v$ 记得回溯（让 $p$ 指回 $u_p$）。
答案就是 $T’$ 的结点数。
C 不会吧不会吧不会这道题还有同学答案错误吧
这道题虽然把点数限制放到了 $5000$，但其实用很少的点数也可以构造出合适的解。只要你大胆去暴力枚举十个点组成的各种树的形态再进行判断，就很快能得出一组解。
一种比较理性的构造方案：一个菊花图加上一条长链（长度大于菊花图点数个数的两倍）。根据子树大小分治的方法会先在链上拆边再分治到菊花图上。
D 关于小方的爆款桌游还没面世就要夭折这回事
签到题，类似于这种先手后手在对称棋盘上下棋、无处落子即败的题目，往往可以通过棋盘的对称性入手。列数为偶数时无论先手在何处落子，后手只要在中心对称的位置下模仿棋即可，故后手必胜。列数为奇数时，先手可以把第一子落在棋盘正中，然后在中心对称的位置模仿后手的棋，故先手必胜。
Once ：围棋其实也有模仿棋一说，但是由于有吃子规则，所以白棋可以在天元附近设陷阱去杀黑棋。再加上黑子贴目的规则，所以朴素的模仿棋并不一定会让黑棋占优。
oxx1108 ：这是 Cram 游戏，在行列均为奇数时暂未被解决（无法在多项式时间内得出谁必胜，也没有被证明为 NP-hard 问题）。
E 蟹老板的梦幻传送门真的能让宅男走出家门吗
先把位置坐标排序使得 $a_1 \le a_2 \le a_3 \le \dots \le a_n$
可以把位置分为左右两部分，左边的只走左边的传送门， 右边的只走右边的传送门。
那么显然左边的传送门放在左半部分坐标所覆盖的区间的中点最优，右传送门同理应该放在右区间的中点。
那么可以枚举两个区间的分界线$a_i (i \in[1, n - 1])$ , 那么左传送门的坐标$X = \frac{a_1 + a_i}{2}$, 右传送门的坐标$Y = \frac{a_{i + 1} + a_n}{2}$。 $\max d(i, j)$ 可以表示为：
$$ \max ( X - a_1 + a_n - Y, a_i - a_1, a_n - a_{i+1} )\\= \max ( \frac{a_i - a_1 + a_n - a_{i + 1}}{2}, a_i - a_1, a_n - a_{i + 1} )\\=\max ( a_i - a_1, a_n -a_{i + 1})$$
三月十七号发的邮件，可以检查检查是不是进垃圾箱了。
3.17没收到过任何邮件。。垃圾箱也没找到。。
我们这边邮件系统里显示已经发送了。