2018.12 月赛题解

Xiejiadong edited 3 年,5 月前

祝贺 EOJ 提交数量破百万

祝贺 EOJ 月赛举办一周年

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

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

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

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

两分钟比赛结束的选手:??????

# Tag Idea Developer Tester
A 小学数学 Xiejiadong Xiejiadong oxx1108
B 蒙特卡洛模拟 ultmaster ultmaster Xiejiadong oxx1108
C 组合数学 DP Xiejiadong Xiejiadong oxx1108
D 想法 乱搞 oxx1108 Xiejiadong ultmaster
E 二分答案 贪心 Xiejiadong Xiejiadong oxx1108
F 后缀平衡树 Xiejiadong Xiejiadong zerol

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$ ,则他对答案的贡献就是 $\binom{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$ 我们可以贪心的求解,我们来大力讨论一下。

Comments

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

Problem F

First Solved:-o..o-

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

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

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

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

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

恭喜 Clarisappleseillusory 喜提冠亚季军。

Comments

DreamerKadars

为啥没有人评论

Lucien

那就来评论一下吧~