2021.3 月赛题解

oxx1108 edited 4 年，1 月前

本次 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^{\prime }$ 和指针 $p$。$T^{\prime }$ 初始时只有结点 $1$，$p$ 指向 $1$。我们在 $T$ 上从 $1$ 开始 DFS。记 $p$ 指向的结点为 $u_p$（$u_p\in T^{\prime }$）。

在 DFS 到结点 $u$（$u\in T$）时，考虑 $u$ 的儿子 $v$：

• 如果 $u_p$ 存在邻居 $z$ 满足 $w(u_p,z)=w(u,v)$ 且 $a_z=a_v$，那么就让 $p$ 指向 $z$。
• 否则，在 $T^{\prime }$ 中新建一个结点 $z$，令 $w(u_p,z)=w(u,v)$，令 $a_z=a_v$，然后让 $p$ 指向 $z$。

然后对 $v$ 进行 DFS。DFS 完了 $v$ 记得回溯（让 $p$ 指回 $u_p$）。

答案就是 $T^{\prime }$ 的结点数。

C 不会吧不会吧不会这道题还有同学答案错误吧

这道题虽然把点数限制放到了 $5000$，但其实用很少的点数也可以构造出合适的解。只要你大胆去暴力枚举十个点组成的各种树的形态再进行判断，就很快能得出一组解。

一种比较理性的构造方案：一个菊花图加上一条长链（长度大于菊花图点数个数的两倍）。根据子树大小分治的方法会先在链上拆边再分治到菊花图上。

D 关于小方的爆款桌游还没面世就要夭折这回事

签到题，类似于这种先手后手在对称棋盘上下棋、无处落子即败的题目，往往可以通过棋盘的对称性入手。列数为偶数时无论先手在何处落子，后手只要在中心对称的位置下模仿棋即可，故后手必胜。列数为奇数时，先手可以把第一子落在棋盘正中，然后在中心对称的位置模仿后手的棋，故先手必胜。

Once ：围棋其实也有模仿棋一说，但是由于有吃子规则，所以白棋可以在天元附近设陷阱去杀黑棋。再加上黑子贴目的规则，所以朴素的模仿棋并不一定会让黑棋占优。

oxx1108 ：这是 Cram 游戏，在行列均为奇数时暂未被解决（无法在多项式时间内得出谁必胜，也没有被证明为 NP-hard 问题）。

E 蟹老板的梦幻传送门真的能让宅男走出家门吗

先把位置坐标排序使得 $a_1\le a_2\le a_3\le \cdots \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}$。 $maxd(i,j)$ 可以表示为：

$$\begin{gathered} 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}) \end{gathered}$$

Comments

馨儿不吃糖呀

4 年前

嘤嘤嘤

回复 1 0

SmallY

4 年，1 月前

E题中线直接取了$\frac{a_1+a_n}{2}$也过了，是数据太弱还是这就是正解哇

回复 1 0

MAOoo

4 年，1 月前

这场没收到邮件啊QAQ

回复 0 0

Once

4 年，1 月前

三月十七号发的邮件，可以检查检查是不是进垃圾箱了。

回复 0 0

MAOoo

4 年，1 月前

3.17没收到过任何邮件。。垃圾箱也没找到。。

回复 0 0

Once

4 年，1 月前

我们这边邮件系统里显示已经发送了。

回复 0 0

zwczwczwc

4 年前

otto，帅！

回复 0 0