为啥没有人评论
Xiejiadong edited 5 年,10 月前
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 |
温暖的签到。
已知最大的和最小的,那么和最大的情况一定是除了一个最小的,其余全部是最大的;相反地,和最小的情况一定是除了一个最大的,其余全部都是最小的。
显然,我们可以通过一些调整,取到从和的最小到最大这整个区间里所有的数。
题面有误导性(向 Xuzhou 学习的)。这个题是「C 语言程序设计基础常见期末考题」之「蒙特卡洛模拟」。
精度要求只有 $10^{-3}$,显然大的时候可以直接输出 0。
对不是 0 的部分,显然 $n$ 越大答案的方差越小,所以 $n$ 越大需要的生成次数就越小,所以可以直接控制复杂度 1E8 或者运行时间。
那么 $n$ 要多大才可以输出 0 了呢?可以试一试:好像 700 多一点点就可以输出 0 了……
出题人:听说大家都不会做随机题啊?得加强随机题训练啊?
野鸡验题人:随机试了发,发现样例一误差有点大,误以为是因为 rand()
是假随机所以过不了……
ultmaster:看样子,大家随机确实不大行啊。
可以发现,询问很多,但是主串 $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|$ 很大的时候是没有解的。
std 写的又丑又长,常数还巨大,为了避免卡常,可能把暴力也放过去了。
ultmaster:写了个复杂度 $2000 \times 2000 \times 100$ 的也跑过去了,甚至还比 std 快。
存在多解是骗人的。
显然,如果存在平方项,那么这个项一定两边都出现了,将出现的平方项所包含的数全部标记添加到两边。
剩余的数一定属于且尽属于一边,那么用 DFS 或者并查集乱搞一下,把他们分开就可以了。
如果没想清楚可能会很难写,想清楚了就很水了。(其实难度和 $B$ 也差不多)
如果写得不优雅去掉平方项后一边为空的可能会错。
要求包含关键点的最大联通块最小,自然考虑二分答案。
假设我们现在二分的值为 $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$ 可以向上合并。
野鸡验题人:二分答案后, DFS 维护当前子树最大可以再放容量/当前子树未被覆盖的总和即可。
我们把这个问题拆分成两个问题解决。
首先考虑一个字符串的不同子串个数怎么计算,这个应该算是模板题了。
其次就是一个字符串重复多次的时候怎么计算。
这样一来,我们就可以结合这两部分的算法,得出总的解法了。
或者直接计算前 $3n$ 项,后边的直接按照等差数列计算。
那就来评论一下吧~