寒假作业：COCI 2014/2015题选 题目与题解
smarthehe
·
·
个人记录
T1 MAFIJA
题目
给定 n 个点，每个点向另一个点连一条有向边，求一个最大的点集使得点集内部点间没有连边。
n \leq 5 * 10^5
题解
就是 [ZJOI2008] 骑士。
基环内向树森林上的dp。
枚举断边后dp可以做；找到环后对每棵环上树分别dp，再在环上dp一遍也可以做。
复杂度 O(n)。
T2 ZABAVA
题目
给定一个长 m 的数列（初始全为 0），n 次操作，每次操作选择一个位置 +1 后使总代价加上那个位置的值。你有 k 次机会随时将一个位置清零。最小化总代价。
n \leq 10^6$，$m \leq 100$，$k \leq 500
题解
容易发现可以对每个位置分别考虑。
如果确定给某位置分配多少次清零，可以很快地算出最优代价。
这样就变成了一个 m 个组的分组背包，正常dp即可。
复杂度 O(n + mk^2)。
T3 KAMP
题目
给定一棵有边权，n 个点的树，以及 m 个目的地（在树上，不重复）。
对于每个点，你要确定以当前点作为起点的一条连续，可重复经过边的路径，使得遍历完所有目的地且边权和最小。（通过同一条边多次则计算多次）
m \leq n \leq 5 * 10^5
题解
换根树形dp。
对于每个点计算出从当前点到它子树中所有目标点且 回来/不回来 的最小边权和。用一遍树形dp可解。
然后跑一遍换根dp就完事了。
细节很恶心。总复杂度 O(n)。
T4 BOB
题目
给定一个 n * m 的矩阵，求值全相等的子矩阵个数。
n,m \leq 1000$，$V \leq 10^9
题解
预处理出每个位置向上的最大长度。
对于每行单调栈扫一遍统计答案。
复杂度 O(n^2)。
T5 SUMA
题目
给定一个 n * n 的矩阵，每个位置有一个初始值和一个增长速率。问在所有时刻中，值全相等的最大连通块大小最大是多少？
n\leq 700$，$V \leq 10^6
题解
使用可撤销并查集实现。只考虑相邻两位置何时相等。
先将恒相等关系合并。
然后枚举可能产生相等的时刻，对于每个时刻将所有相等关系合并，统计答案，然后撤销。
总复杂度 O(n^2\log n)。
T6 NORMA
题目
给定一个长为 n 的序列，一个连续子序列的权值定义为：
子序列最大值 * 子序列最小值 * 子序列长度
求所有连续子序列权值和。答案对 10^9 取模。
n \leq 5 * 10^5
题解
考虑分治处理。
对于 [l,r] 内所有子序列的贡献，可以拆为：
这样，为了分治处理只需考虑如何计算过定点的所有子序列的贡献和。
我们作出如下定义：
$lmax_i$：$[i,mid]$ 中的最大值
$lmin_i$：$[i,mid]$ 中的最小值
$rmax_i$：$[mid+1,i]$ 中的最大值
$rmin_i$：$[mid+1,i]$ 中的最小值
$mxsum_i$：$\sum_{j=mid+1}^{i} rmax_j
mnsum_i$：$\sum_{j=mid+1}^{i} rmin_j
m2sum_i$：$\sum_{j=mid+1}^{i} rmax_j * rmin_j
mxLsum_i$：$\sum_{j=mid+1}^{i} j * rmax_j
mnLsum_i$：$\sum_{j=mid+1}^{i} j * rmin_j
m2Lsum_i$：$\sum_{j=mid+1}^{i} j * rmax_j * rmin_j
每次处理一段区间 [l,r] 时，一遍扫计算如上 10 个数组。
那么在计算贡献时，从 l 到 mid 枚举左端点，得到 lmin_i 与 lmax_i ，并同时开单调队列找到 [mid+1,r] 前缀最值数组中从左到右第一个 rmin < lmin_i 与第一个 rmax > lmax_i 的位置，记作 minlim 与 maxlim。
这样的话，我们可以分类讨论右端点的位置来得出贡献。此处令左端点为 i。
- 右端点 < \min(minlim,maxlim)
那么可以直接调用 lmin_i 和 lmax_i 计算贡献。
可以用如下公式描述这些子段的总贡献：
ans = \sum_{j=mid+1}^{\min(minlim,maxlim)-1} (j-i+1) * lmin_i * lmax_i
提出后，用等差数列公式可以化简。
-
\min(minlim,maxlim) \leq$ 右端点 $< \max(minlim,maxlim)
若 minlim \leq maxlim ，那么这段的最小值在变化，而最大值可以调用 lmax_i。
ans = \sum_{j=minlim}^{maxlim-1} (j-i+1) * rmin_j * lmax_i
提出化简为已知得
ans = lmax_i (mnLsum_{maxlim-1}-mnLsum_{minlim-1}-(i-1)(mnsum_{maxlim-1}-mnsum_{minlim-1}))
反之，则这段的最大值在变化，而最小值可以调用 lmin_i。
ans = \sum_{j=maxlim}^{minlim-1} (j-i+1) * lmin_i * rmax_j
提出化简为已知得
ans = lmin_i (mxLsum_{minlim-1}-mxLsum_{maxlim-1}-(i-1)(mxsum_{minlim-1}-mxsum_{maxlim-1}))
-
这段的最大值与最小值和 lmax_i 与 lmin_i 没有关系。
ans = \sum_{j=\max(minlim,maxlim)}^{r} (j-i+1) * rmin_j * rmax_j
简单化简得
ans = m2Lsum_{r}-m2Lsum_{\max(minlim,maxlim)-1}-(i-1)(m2sum_{r}-m2sum_{\max(minlim,maxlim)-1})
这样我们就能对于每个左端点 O(1) 算出答案。
分治总复杂度：O(n\log n)。
T7 COCI
题目
给定 n 个人，每个人有三个得分 x，y，z，但是每个人的 z 并不确定，只有 x，y 已知。如果一个人的 x 与 y 均严格大于另一个人的 x 与 y（即成二维偏序），则我们可以认为这个人的 z 大于等于那个人的 z。现在请确定在满足如上假设的最极限情况下，每个人最高与最低的 x+y+z 值的排名。
n \leq 5 * 10^5$，$0 \leq x,y,z \leq 650
题解
如果一个人 i 的 x,y 均大于另一个人 j，我们称 i 限制 j。
首先考虑最高排名，对于每个人 i 可以假设除限制其的所有人以外 z=0，而 i 及限制 i 的人的 z=650。
那么我们具体需要知道：
-
- 限制 i 的人数
稍加思索，发现 2 类包含 1 类。所以我们只需要知道 2 类的人数。这是经典二维偏序问题。
然后考虑最低排名，对于每个人 i 可以假设除 i 限制的所有人以外 z=650，而 i 及 i 限制的人的 z=0。
我们反着考虑，考虑一定排在 i 之后的人有多少个。
那么我们具体需要知道：
-
- 被 i 限制的人数
这样就类似最高排名的情况了，有 2 类包含 1 类。有一些不同的地方是，当 x,y 至少有一个为 650 时要特判。
同样是经典二维偏序问题。总复杂度 O(n\log n)。
启示： 对于最低排名，如果正着考虑，就只能按总和排序后使用二维树状数组维护，时间变成 O (n\log^2 n)，无法通过。所以，科学地反着考虑问题有时能很好地起到优化复杂度的作用。
再启示： 不必要纠结用树状数组维护偏序。考虑值域只有 650，可以提前使用二维前缀和直接预处理出来所有正向与反向的偏序关系。复杂度 O(V^2 + n)。要充分利用题目的性质！！！
T8 STOGOVI
题目
初始给定一个空栈，编号为 1。共 q 次操作，第 i 次编号为 i。每次操作前，先选定编号为 x 的栈并将其复制，新栈编号为操作编号；然后对新栈进行如下操作的一种：
- 在栈顶压入一个元素，值为操作编号
- 弹出栈顶，输出弹出的值
- 选择另一个栈，输出两栈交集大小
你要实现一种数据结构，实现如上的操作。
q \leq 3 * 10^5
题解
可以从构建树形结构的方向上考虑。
每个栈视为一个点，存一个值记录栈顶元素。同时用并查集处理栈间相等关系。
对于 1 操作，从原栈向新栈连边，使原栈成为新栈父亲。
对于 2 操作，输出原栈处所存的值。新栈必定和原栈的父亲相同，将两者合并。
对于 3 操作，即为求两栈 LCA 深度。新栈必然和第一原栈相同，将两者合并。
每次在调用“原栈”时，应该调用其在并查集上的根。
离线预建出整棵树是可行的，在线的话就用 LCT 大力维护 LCA 或者连到每个点的时候处理一遍倍增数组。
复杂度 O(q\log q)。
T9 KAMIONI
题目
数个城市依次排列位于一个数轴上，编号为 i 的城市位于数轴坐标为 i 处，可见编号相邻的两城市之间距离为 1。
$$ A_1 < A_2 > A_3 < A_4 > \cdots \ \text{或} \ A_1 > A_2 < A_3 > A_4 < \cdots $$
显然路径上每个点都可被称作一个“拐点”。
所有卡车同时出发，起始点为其路径第 $1$ 个点，速率都为 $1$。当一辆卡车到达它路径的终点的瞬间，它就会消失。当两辆卡车同时位于某一处（不一定必须是某个城市）时，我们称它们相遇。
$m$ 次询问，每次选择两辆卡车 $x,y$，问它们相遇的次数。
读入保证询问的两辆卡车不会在其中任意一辆卡车达到路径上某一拐点时相遇。
$n,m \leq 10^5$，$\sum k \leq 3 * 10^5$， $A_i \leq 10^9
题解
首先把所有卡车的所有拐点合在一起，按达到的时间排序。
把所有询问离线下来。对于每个询问，找到两卡车中拐点较少者，绑定在该车上。对于重复的询问，直接记忆化判掉。
可以发现，任意一车的两拐点之间两车最多相遇一次，并且在这道题目中不存在追及。
在被绑定车的两拐点之间，我们画出原询问的两辆车的 x-t 图。
容易发现，被绑定车的图像一定是一条单调直线，而另一车的图像是分段单调的折线。（图来源：Mr_Wu 手绘）
那么如果这两辆车有交，就只能是两辆车的相对左右关系在两拐点处不同。
又考虑，每个询问只会考虑被绑定车的所有拐点，所以我们在得出当前这个拐点处询问的两车的左右关系时，可以将这个关系连带存在询问上。这样，在到达绑定车的下一个拐点时，就容易判断了。
那么，枚举所有拐点，动态设定一辆车的位置和方向。每枚举到一个拐点，枚举和拐点所属车绑定的所有询问，处理即可。
另外，对于在到达某一拐点前除绑定车以外的另一辆询问车消失的情况，也是有可能相遇的。处理比较恶心，需要特判。（并且样例里面没有这个情况，如果你样例全过却 wa 声一片，可以看看是不是这个原因）
时间复杂度分析：
考虑可能发生的所有询问以及其对应绑定的卡车路径长度。从大到小排序后前 q 项和就是最大枚举复杂度。
我们令每辆卡车的路径长度从大到小为 k_1,k_2,\cdots,k_n。
那么最大的枚举复杂度显然为 1 * k_2 + 2 * k_3 + \cdots（系数和为 q）
随意放缩简化一下，令上述式子没有包含的 k_i = 0，并假定式子即为 \sum_{i=1}^x i * k_i 的形式。
基于等差数列求和公式，可得 x 在 \sqrt{q} 左右。不妨令 x=\sqrt{q}。
那我们的问题转化为：
已知 \sum_{i=1}^{\sqrt{q}} k_i = k，求 \max \{ \sum_{i=1}^{\sqrt{q}} i * k_i \}。
根据大小关系，易得 k_i \leq \frac{k}{i}，因此时间复杂度 O (k \sqrt{q})。
启示： 有时候，看上去毫无道理的暴力却有很优秀的复杂度，还是要多详细分析。
代码大全
T1-MAFIJA（由于代码复杂度不正确，暂缓放出）
T2-ZABAVA
T3-KAMP
T4-BOB
T5-SUMA
T6-NORMA
T7-COCI
T8-STOGOVI
T9-KAMIONI