2018.12 月赛题解

Xiejiadong edited 6 年，4 月前

祝贺 EOJ 提交数量破百万

祝贺 EOJ 月赛举办一周年

【硬广】欢迎访问 Xiejiadong‘s Blog

ultmaster: 难度顺序又反了。难度顺序与题目顺序不怎么有关，已经成为月赛特色了。

Xiejiadong: 三个 C 题，一致通过还是我的最签到。

Claris: 怎么这么简单啊？难度顺序递减的啊？

两分钟比赛结束的选手：？？？？？？

Problem A

First Solved：SqwrIwy

温暖的签到。

已知最大的和最小的，那么和最大的情况一定是除了一个最小的，其余全部是最大的；相反地，和最小的情况一定是除了一个最大的，其余全部都是最小的。

显然，我们可以通过一些调整，取到从和的最小到最大这整个区间里所有的数。

Problem B

First Solved：UoA_ZQC

题面有误导性（向 Xuzhou 学习的）。这个题是「C 语言程序设计基础常见期末考题」之「蒙特卡洛模拟」。

精度要求只有 ${10}^{-3}$，显然大的时候可以直接输出 0。

对不是 0 的部分，显然 $n$ 越大答案的方差越小，所以 $n$ 越大需要的生成次数就越小，所以可以直接控制复杂度 1E8 或者运行时间。

那么 $n$ 要多大才可以输出 0 了呢？可以试一试：好像 700 多一点点就可以输出 0 了……

Comments

出题人：听说大家都不会做随机题啊？得加强随机题训练啊？

野鸡验题人：随机试了发，发现样例一误差有点大，误以为是因为 rand() 是假随机所以过不了……

ultmaster：看样子，大家随机确实不大行啊。

Problem C

First Solved：SqwrIwy

可以发现，询问很多，但是主串 $S$ 的长度并不长。考虑预处理所有的结尾情况。

我们可以枚举第一个位置 $X$ ，预处理出 $X$ 后面分别接 $10$ 个数字的时候，可以组成字符串的数量。

假设当前枚举到的一个位置 $i$ 满足 $S_i=X$ 。题目需要组成新字符串的长度为 $N$ ，假设位置 $i$ 后面有 $A_y$ 个 $Y$ ，则他对答案的贡献就是 $(\genfrac{}{}{0ex}{}{i-1}{n-2})A_y$ 。

显然，$A_y$ 是可以先处理掉的，然后再继续暴力预处理所有结尾情况下新字符串的数量。

预处理完成以后，对于所有的询问都可以 $\mathcal{O}(1)$ 出结果。

但是我们发现询问给出的 $N$ 很大，但可以显然地发现，当 $N>|S|$ 很大的时候是没有解的。

Comments

std 写的又丑又长，常数还巨大，为了避免卡常，可能把暴力也放过去了。

ultmaster：写了个复杂度 $2000\times 2000\times 100$ 的也跑过去了，甚至还比 std 快。

Problem D

First Solved：2653457495

存在多解是骗人的。

显然，如果存在平方项，那么这个项一定两边都出现了，将出现的平方项所包含的数全部标记添加到两边。

剩余的数一定属于且尽属于一边，那么用 DFS 或者并查集乱搞一下，把他们分开就可以了。

如果没想清楚可能会很难写，想清楚了就很水了。（其实难度和 $B$ 也差不多）

如果写得不优雅去掉平方项后一边为空的可能会错。

Problem E

First Solved：UoA_ZQC

要求包含关键点的最大联通块最小，自然考虑二分答案。

假设我们现在二分的值为 $mid$ ，考虑如何判定最大的联通块大小是否 $\le m$ 。

我们假设 $f_{x,0/1}$ 为只考虑 $x$ 的子树， $x$ 所在的联通块最小是多少（ $0$ 和 $1$ 表示包不包含关键点，显然如果可以包含关键点一定让它包含，所以可以用 $f_x$ 的正负来代替两个状态的记录）。

这个 $f$ 我们可以贪心的求解，我们来大力讨论一下。

• 如果结点 $x$ 本身是关键点，那么对于本身包含关键点的子结点 $y$ ，即满足 $f_y>0$ 的子节点就不用包含在含有 $x$ 的联通块中了，那么对于其他剩下的本身不包含关键点的子结点 $y$ ，即满足 $f_y<0$ 的子节点显然是包含在含有 $x$ 的联通块中是最优的。

• 如果结点 $x$ 本身不是关键点，我们一定会选择本身包含关键点的子结点 $y$ 中 $f$ 最小的结点，让 $x$ 和满足 $f_y<0$ 的所有子节点所构成的子树都包含在其中，如果大小超过 $mid$ 的话就只能让 $x$ 和满足 $f_y<0$ 的所有子节点所构成的子树在一个联通块，并使 $f_x<0$，让结点 $x$ 可以向上合并。

Comments

野鸡验题人：二分答案后， DFS 维护当前子树最大可以再放容量/当前子树未被覆盖的总和即可。

Problem F

First Solved：-o..o-

我们把这个问题拆分成两个问题解决。

首先考虑一个字符串的不同子串个数怎么计算，这个应该算是模板题了。

• 显然每一个子串一定是一个后缀的前缀，那么我们就计算所有的后缀中有多少个不同的前缀就好了。
• 我们先把这个串倒过来，预处理出后缀数组。
• 每次插入一个后缀，求出与前后的 LCP 即可。

其次就是一个字符串重复多次的时候怎么计算。

• 如果一个串是循环串比较好处理，我们直接考虑循环节就行。
• 那我们假设这个串不是循环串，那么当子串的长度大于等于 $n$ 以后不同的位置位置对应的必定不同。
• 也就是说，只需要统计子串长度小于 $n$ 的结果。
• 而算前 $k$ 个字符的本质不同子串数，用后缀平衡树可以解决。
• 后缀平衡树可以去看看 wjmzbmr 的论文。

这样一来，我们就可以结合这两部分的算法，得出总的解法了。

• 如果长度超过 $2n$ ，那么每个长度不超过 $n$ 的串都已经出现过，所以每次向后增加一位，多增加的就是以它为结尾的整个串作为子串，即每次答案都增加 $n$ 。
• 而对于长度不超过的 $2n$ 的部分，直接后缀数组求解即可。

或者直接计算前 $3n$ 项，后边的直接按照等差数列计算。

恭喜 Claris，applese，illusory 喜提冠亚季军。

Comments

DreamerKadars

6 年，4 月前

为啥没有人评论

回复 3 0

Lucien

6 年，4 月前

那就来评论一下吧～

回复 0 0