2020.1 月赛题解

oxx1108 edited 2 年,10 月前

申明

由于比赛期间出现了网络问题,比赛延长了半小时。也因此问题,我们决定本场月赛 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$ -变幻序列的生成方式,在二进制的意义下,无非就是:

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

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

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

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

Comments

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

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

Comments