「套题泛做」NOIP 六校联考 2020

Link

yzhang 鸽鸽说 R1 - R5 比较毒瘤，就从 R6 开始做了（

其实题已经看了蛮多的了，但是没啥时间写，写做题笔记也比较耗时间，不知道什么时候能把坑填好（

Round 6

俄罗斯方块

Link

考虑一个简单 dp，枚举第 $i$ 个位置之前几个位置的几种状态，分别记录它们的答案。发现所谓的 “几种状态” 其实就这五种：

前面黑色阴影部分表示全填满

注意到转移只需要前几位的状态，用矩阵快速幂优化即可做到 $\mathcal{O(T \log n)}$ 的复杂度。

Code（手写了巨大的转移矩阵

三格缩进

Link

每次询问要求的是

$\sum\limits_{i=1}^n \left\lfloor \frac{y}{a_i} \right\rfloor + y \bmod a_i$

也即

$\sum\limits_{i=1}^n \left\lfloor \frac{y}{a_i} \right\rfloor + y - a_i \left\lfloor \frac{y}{a_i} \right\rfloor \\ = \sum\limits_{i=1}^n (- a_i + 1) \left\lfloor \frac{y}{a_i} \right\rfloor$

考虑每次修改对 $(-a_i + 1)$ 这个东西根号分治：若 $a_i \le \sqrt{W}$，则开一个数组暴力累加每个 $a_i$ 的答案（称为第一步）；否则对每一个 $y$（有 $\left\lfloor \frac{W}{a_i} \right\rfloor$ 个这样的 $y$）修改答案（称为第二步）。

第二步可以用树状数组优化。这种方法的修改复杂度为 $\mathcal{O(\log W \cdot \sqrt W)}$ ，查询复杂度为 $\mathcal{O(\sqrt W)}$，无法通过。

注意到修改的复杂度瓶颈在第二步，而查询时查第二步的复杂度仅仅为 $\mathcal{O(1)}$。于是考虑用分块平衡第二步修改和查询的复杂度。设第二步种记录每个 $y$ 的答案数组为 $s$。对 $s$ 做差分再做分块，每次修改时只需做单点修改而不需要用树状数组，复杂度降为 $\mathcal{O(\sqrt W)}$；查询时对 $s$ 求前缀和，复杂度升为 $\mathcal{O(\sqrt W)}$。

此时修改与查询的复杂度均为 $\mathcal{O(\sqrt W)}$，总复杂度为 $\mathcal{O(q \sqrt W)}$，可以通过本题。

Code

最佳观影

Link

观察不横跨中间一条线的团队，它们的代价在某种程度上是相似的：设这个团队最靠近中心的一个点为 $(x_i, y_i)$，中心为 $(a, b)$，则它的代价为

$cost_i = m_i \cdot (\ |a - x_i| + |b - y_i|\ ) + \sum\limits_{i=1}^{m_i} i - 1$

我们可以把所有空位置（是指对于一整个团队而言，可以落脚的地方）的 $|a - x_i| + |b - y_i|$ 扔到一颗线段树里维护，查询时查询长度不小于 $m_i$ 的空位置中代价最小的那一个。关于实现细节，你需要对线段树的每个叶子节点维护一个 $\texttt{set}$。

横跨中间一条线的空位置在任意时刻最多不超过 $2$ 个，可以单独维护。

于是，我们在 $\mathcal{O(n \log k)}$ 的复杂度内解决了本题。

代码还在鸽（

Round 7

月饼

随便 dp 一下，没啥好写的（

代码也没写（

伟大的卫国战争

称一条连接 $a_i, b_i$ 的公路线为线段 $i: \ [a_i, b_i]$。

两条线段有冲突即代表它们在道路的异侧（显然用种类并查集维护），于是原题转化为二分图的判定，但是边数巨大。

把所有线段按左端点排序，并且按左端点从右往左扫。由于当前扫到的这条线段 $i$ 的左端点在前面扫到过的所有左端点之前，所以和线段 $i$ 冲突的，在线段 $i$ 之前扫到的所有线段，就是之前扫到的所有覆盖 $b_i$ 的线段。我们要找到所有这样的线段，并给它们标记“与 $i$ 颜色相反”。

我们于是需要维护“覆盖某个点的线段”，这个东西比较 tricky。对值域（即 $[1, n]$）建一颗线段树，每个节点维护覆盖了当前区间的线段编号（显然是一个 vector），不需 lazy tag 下传。

每次区间修改（往线段树里加上某个线段 $[a_i, b_i]$）直接暴力往所有涉及的 $\log n$ 个节点的 vector 里面加这个节点的编号。每次单点查询（给前文说到的，所有满足条件的线段标记）线段树路径上遍历到的每个节点都扫一遍其中的 vector 更新并查集，并且在扫完之后把整个 vector 替换为该 vector 的任意一个元素，这个操作的合理性比较显然，因为原 vector 的所有元素在更新并查集之后都一定属于同一个颜色了。

最后并查集随便搞搞输出答案，时间复杂度 $O(m \log n)$

Code

道路扩建

这玩意原题是 CF1163F，且这个题是 1163F 的子集，所以就直接讲 1163F 的做法了（

从 $1$ 和 $n$ 出发各建一颗最短路树，

懒了，不写了，洛谷上有一堆题解（

何况我自己代码都没调出来（

有没有神帮我看看啊（