本来已经写了不少,但又发现了前人造的质量上乘的轮子,就没有为难自己了。
以下文章均转载自 command-block 的洛谷博客。
本来已经写了不少,但又发现了前人造的质量上乘的轮子,就没有为难自己了。
以下文章均转载自 command-block 的洛谷博客。
中规中矩的一场模拟赛。
T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。
T2 有我喜欢的马拉车 Manacher 算法,是印象里第二次在模拟赛应用。
然后就没时间了。后两题仍然只有暴力分,但最近频繁遇到跟凸包和线性函数相关的题目,这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题,但思路是错误的。
这好像是很早以前的译名了。现在它叫《莉可丽丝》。
遇见多模式串匹配,自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana
chinanago
在任何一个文本串中最多只能匹配其中一个,且匹配位置唯一。于是简单计数 DP 转移,记录当前二者匹配数之差与目前匹配位置即可。
一些不应用就过不了的优化:
?
s
c
a
o
还有其他字符分类讨论,保证单次转移复杂度为 。时间复杂度 。 (更多…)
Atcoder ARC149D – Simultaneous Sugoroku
官方题解做法是线性的,在此不再赘述。
考虑对于纸片 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 ,在 次操作以后纸片在数轴上的坐标 ,其中 是最小的取到 的位置,则对于 :
这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 、后缀所有数符号翻转 ()。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。
时间复杂度 ,常数一般。
感冒咳嗽,头实在是太晕了,打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。
简单的 DP。记录每个节点的路径数奇偶性考虑是否翻转即可。
用 std::bitset
写的暴力大家都会。不过如果你胆子大些,不判断是否为部分分数据范围直接提交(加入随机化的)暴力,将喜提 。
命题:现有一个由 个元素构成的集合,保证 。有 个大小恰为 的子集 。则至少存在 对无序对 ,使得 。
证明(引自宋佳兴学长):记元素 在所有子集中出现的次数为 。则显然有“所有子集两两之交的大小”
考虑计算该式最小为何。不妨先考虑 在何时取最小值。
引理: 在 处取最小值。