yzhang 鸽鸽说 R1 - R5 比较毒瘤,就从 R6 开始做了(
其实题已经看了蛮多的了,但是没啥时间写,写做题笔记也比较耗时间,不知道什么时候能把坑填好(
Round 6
俄罗斯方块
考虑一个简单 dp,枚举第 个位置之前几个位置的几种状态,分别记录它们的答案。发现所谓的 “几种状态” 其实就这五种:
前面黑色阴影部分表示全填满
注意到转移只需要前几位的状态,用矩阵快速幂优化即可做到 的复杂度。
Code(手写了巨大的转移矩阵
三格缩进
每次询问要求的是
也即
考虑每次修改对 这个东西根号分治:若 ,则开一个数组暴力累加每个 的答案(称为第一步);否则对每一个 (有 个这样的 )修改答案(称为第二步)。
第二步可以用树状数组优化。这种方法的修改复杂度为 ,查询复杂度为 ,无法通过。
注意到修改的复杂度瓶颈在第二步,而查询时查第二步的复杂度仅仅为 。于是考虑用分块平衡第二步修改和查询的复杂度。设第二步种记录每个 的答案数组为 。对 做差分再做分块,每次修改时只需做单点修改而不需要用树状数组,复杂度降为 ;查询时对 求前缀和,复杂度升为 。
此时修改与查询的复杂度均为 ,总复杂度为 ,可以通过本题。
最佳观影
观察不横跨中间一条线的团队,它们的代价在某种程度上是相似的:设这个团队最靠近中心的一个点为 ,中心为 ,则它的代价为
我们可以把所有空位置(是指对于一整个团队而言,可以落脚的地方)的 扔到一颗线段树里维护,查询时查询长度不小于 的空位置中代价最小的那一个。关于实现细节,你需要对线段树的每个叶子节点维护一个 。
横跨中间一条线的空位置在任意时刻最多不超过 个,可以单独维护。
于是,我们在 的复杂度内解决了本题。
代码还在鸽(
Round 7
月饼
随便 dp 一下,没啥好写的(
代码也没写(
伟大的卫国战争
称一条连接 的公路线为线段 。
两条线段有冲突即代表它们在道路的异侧(显然用种类并查集维护),于是原题转化为二分图的判定,但是边数巨大。
把所有线段按左端点排序,并且按左端点从右往左扫。由于当前扫到的这条线段 的左端点在前面扫到过的所有左端点之前,所以和线段 冲突的,在线段 之前扫到的所有线段,就是之前扫到的所有覆盖 的线段。我们要找到所有这样的线段,并给它们标记“与 颜色相反”。
我们于是需要维护“覆盖某个点的线段”,这个东西比较 tricky。对值域(即 )建一颗线段树,每个节点维护覆盖了当前区间的线段编号(显然是一个 vector
),不需 lazy tag 下传。
每次区间修改(往线段树里加上某个线段 )直接暴力往所有涉及的 个节点的 vector
里面加这个节点的编号。每次单点查询(给前文说到的,所有满足条件的线段标记)线段树路径上遍历到的每个节点都扫一遍其中的 vector
更新并查集,并且在扫完之后把整个 vector
替换为该 vector
的任意一个元素,这个操作的合理性比较显然,因为原 vector
的所有元素在更新并查集之后都一定属于同一个颜色了。
最后并查集随便搞搞输出答案,时间复杂度
道路扩建
这玩意原题是 CF1163F,且这个题是 1163F 的子集,所以就直接讲 1163F 的做法了(
从 和 出发各建一颗最短路树,
懒了,不写了,洛谷上有一堆题解(
何况我自己代码都没调出来(
有没有神帮我看看啊(