2020.1 月赛题解

oxx1108 edited 5 年，3 月前

申明

由于比赛期间出现了网络问题，比赛延长了半小时。也因此问题，我们决定本场月赛 Unrated .

由于网络问题造成比赛体验不佳，敬请谅解。

花絮

Xiejiadong ：一千个人能干什么？能把 EOJ 代理炸掉。还能顺带把 ECNU 主站也炸了。

Xiejiadong ：EOJ 月赛重回千人。想想上一次还是 oxx1108 出题的时候。或许这就是 oxx1108 的魅力吧。

oxx1108 ：现在都在研究图论，准确说是 hierarchy 的图（ tree 和 DAG ），所以变为了图论（树）专场，原来还有一个比较难的图论移到之后比赛里了。

oxx1108 ：之后可能会办马拉松，拿一些 research 中和竞赛又有一些相关的问题，让大家感受一下异同。（也有可能咕咕咕了）

Xiejiadong ：idea 都是 oxx 的。我是一个没有感情的数据生成器。

#	Tag	Idea	Developer	Tester
A	模拟	oxx1108	Xiejiadong	Kilo_5723
B	图论 构造	oxx1108	Xiejiadong	Special Judge
C	图论	oxx1108	Xiejiadong	Kilo_5723
D	哈希	oxx1108	Xiejiadong	Kilo_5723
E	数学	Xiejiadong	Xiejiadong	Kilo_5723

Problem A 回文时间

First Solved：interestingLSY

签到题。

字符串或者用数字枚举一下所有回文串然后 check 一下就行。

如果用数字的话输出有个小技巧， printf 可以用 %0xd 自动补前置 $0$ ， $x$ 是位数。

Problem B 构树挑战

First Solved：いけないボーダーライン

给出两种构造方式：

方法一：首先，一阶为四个点构成一个人字形，然后二阶三个人字形共用一个结点（一共 $10$ 个点），问两次后变为一阶，一直构造到 $10$ 阶，一共 $3^{10}+1$ 个结点，需要询问至少 $21$ 次。这种构造方式需要的询问次数理论上为 $2{\log }_3(n)={\log }_{\sqrt{3}}(n)$ 。

方法二：斐波那契树，即每次新的树 $T_i$ 的左子树为 $T_{i-1}$ ，右子树为 $T_{i-2}$ 。这样每次只能切掉 $T_{i-2}+1$ 那部分，输出 $T_{21}$ 就可以了，大约三万多个点。理论 bound 是 ${\log }_x(n)$，$x=\frac{\sqrt{5}+1}{2}$ 。可以证明这个 bound 就是确界，另外对于$d$叉树可能也有类似的构造以及 bound，有兴趣的同学可以私下讨论。（有可能会拿这个发 paper，而且写起来比较麻烦，所以就不在这里证了）

Comments

oxx1108 ：这个问题背景来源于 SIGMOD 2019 Interactive Graph Search 这篇 paper，有兴趣的同学可以看一下，不过作者的方法可能有一些问题，或者说不是最优的。提出的 bound 也不够精确，只是拿了满 $d$ 叉树作为最坏情况。另外，我最近在研究这个问题以及多 target 情况下的问题，不过难很多，有兴趣可以讨论一下。

Problem C 最简边集

First Solved：0xfaner

可以用反证法证明对于任意一条边，删了它之后如果这两个点之间依然有一条路的话，那么它可以删掉。（其实就是哈斯图。有环的情况下不成立，是个 np-hard 问题）

方法一：最简单的就是跑一遍弗洛伊德，然后每条边 check 一下。但是数据范围不允许三方，因此用 bitset 优化一下即可。

方法二：对于每个点出发跑 dfs ，其实也很简单。对于每一次跑 dfs ，将初始点连的点的 vis 全部标为 false，然后跑完之后如果 vis 变为 true 了就说明这条边可以删。

Comments

oxx1108 ：可能是个 well-known 的问题，详见 transitive reduction。

Problem D 对称关系

First Solved：Renatus

对于两个数可以互换，分为两种情况，一种是没有他们乘积这一项，另一种是有乘积这一项。

对于没有乘积的，将每个数所乘的数全部看作二进制哈希，然后判断等价类；对于有乘积的，枚举所有乘积项后将这一项去掉后的哈希比较一下。

注意平方项要特殊判断，有无平方项要分成两类。

可能会卡掉部分姿势不正确的哈希（单哈希以及自然溢出）。

Comments

oxx1108 ：这个原来也是图论题，被我强行改成了不含图论的题。另外原来是没有系数为$1$的限制的，由于标程写得太丑懒得改就强行降低难度了。

Problem E 数的变幻

First Solved：57

首先需要考虑 $x$ -变幻序列的生成方式，在二进制的意义下，无非就是：

• 末尾为 $1$ ，则变成 $0$ ;
• 末尾为 $0$ ，则直接去掉。

于是考虑一个数 $x$ 在多少变幻序列中出现的时候，可以发现：

• 如果 $x$ 是奇数，就是前缀匹配，之后的位数任意；
• 如果 $x$ 是偶数，就是前缀匹配或者最后一位变 $1$ 后前缀匹配（可以先逆向执行 $x-1$ 操作），之后的位数任意。

这样一来，如果我们已知了数 $x$ ，就可以在 $O(lo{g}_{2}x)$ 的时间内求得 $x$ 在 $[1,n]$ 变幻序列中出现的次数了。

因为是前缀匹配，所以可以很容易的发现，如果将奇数和偶数独立开来考虑的话，是满足单调性的。

于是我们考虑对奇数和偶数分别二分确定最大值，然后取两者中的较大值作为答案即可。

Comments

Xiejiadong ：这题之前十月份被我出在了某小学生编程比赛中，导致了 gap 过大。

Xiejiadong ：这好像是 codeforces 首页一场比赛的 div2 e 题。dbq 我好久没打 codeforces 了。

Comments