2021.3 月赛题解

oxx1108 edited 3 年前

本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先,感谢以下同学为本次月赛命题做出的贡献:

出题人:oxx1108 (A C D E)、ssshwy (B)。

施工大队:Once (题面)、bingoooooooo (A C)、yanghong (D E)

验题人:xryjr233shirakami_fbkyaoRnaitir

感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划,使得 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$:

然后对 $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})$$

Comments

SmallY

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

馨儿不吃糖呀

嘤嘤嘤

zwczwczwc

otto,帅!

MAOoo

这场没收到邮件啊QAQ

Once

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

MAOoo

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

Once

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