oxx1108 edited 4 年，11 月前
由于比赛期间出现了网络问题，比赛延长了半小时。也因此问题，我们决定本场月赛 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 |
签到题。
字符串或者用数字枚举一下所有回文串然后 check 一下就行。
如果用数字的话输出有个小技巧， printf 可以用 %0xd 自动补前置 $0$ ， $x$ 是位数。
给出两种构造方式：
方法一：首先，一阶为四个点构成一个人字形，然后二阶三个人字形共用一个结点（一共 $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，而且写起来比较麻烦，所以就不在这里证了）
oxx1108 ：这个问题背景来源于 SIGMOD 2019 Interactive Graph Search 这篇 paper，有兴趣的同学可以看一下，不过作者的方法可能有一些问题，或者说不是最优的。提出的 bound 也不够精确，只是拿了满 $d$ 叉树作为最坏情况。另外，我最近在研究这个问题以及多 target 情况下的问题，不过难很多，有兴趣可以讨论一下。
可以用反证法证明对于任意一条边，删了它之后如果这两个点之间依然有一条路的话，那么它可以删掉。（其实就是哈斯图。有环的情况下不成立，是个 np-hard 问题）
方法一：最简单的就是跑一遍弗洛伊德，然后每条边 check 一下。但是数据范围不允许三方，因此用 bitset 优化一下即可。
方法二：对于每个点出发跑 dfs ，其实也很简单。对于每一次跑 dfs ，将初始点连的点的 vis 全部标为 false，然后跑完之后如果 vis 变为 true 了就说明这条边可以删。
oxx1108 ：可能是个 well-known 的问题，详见 transitive reduction。
对于两个数可以互换，分为两种情况，一种是没有他们乘积这一项，另一种是有乘积这一项。
对于没有乘积的，将每个数所乘的数全部看作二进制哈希，然后判断等价类；对于有乘积的，枚举所有乘积项后将这一项去掉后的哈希比较一下。
注意平方项要特殊判断，有无平方项要分成两类。
可能会卡掉部分姿势不正确的哈希（单哈希以及自然溢出）。
oxx1108 ：这个原来也是图论题，被我强行改成了不含图论的题。另外原来是没有系数为$1$的限制的，由于标程写得太丑懒得改就强行降低难度了。
首先需要考虑 $x$ -变幻序列的生成方式，在二进制的意义下，无非就是：
于是考虑一个数 $x$ 在多少变幻序列中出现的时候，可以发现：
这样一来，如果我们已知了数 $x$ ，就可以在 $O(log_2x)$ 的时间内求得 $x$ 在 $[1,n]$ 变幻序列中出现的次数了。
因为是前缀匹配，所以可以很容易的发现，如果将奇数和偶数独立开来考虑的话，是满足单调性的。
于是我们考虑对奇数和偶数分别二分确定最大值，然后取两者中的较大值作为答案即可。
Xiejiadong ：这题之前十月份被我出在了某小学生编程比赛中，导致了 gap 过大。
Xiejiadong ：这好像是 codeforces 首页一场比赛的 div2 e 题。dbq 我好久没打 codeforces 了。