2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest

菜得不行。

Problem A

Solved by ultmaster. 01:22 (+2)

题意：$a$, $b$, $c$ 是递增数列，求 $(i,j,k)$ 对数满足 $|a_i-b_j| \le d, |a_i-c_k| \le d, |b_j-c_k| \le d$。

题解：枚举 $a$ 中的元素，$b$ 中满足的显然是一个区间，对于这个区间内的数，满足的 $c$ 的右端点可以通过预处理得到。通过预处理前缀和应该不难解决。不过大概是做烦了，鉴于大家都过得飞快。

先写错了一个变量 WA 了一发，然后不知道什么地方崩了 long long（还立了个 flag 说绝对不会是这个问题的），被 zerol 全部改成 long long 过了。

另解：枚举每个数列中的元素作为最小值，然后在另两个串中统计合法个数。（把三个数列放在一起排个序会更方便。）

Problem C

Solved by ultmaster. 03:19 (+)

题意：在树上找一个点集，使得每条路径都与这个点集有交集。

题解：如果树是一条链，显然是一个经典的「丽娃河装路灯」问题（之前还讨论过它的树状数组优化）。那么放到树上，我们就按照 LCA 的深度排序，路灯肯定装在 LCA 上。同样使用树状数组优化，加个树链剖分就可以。

Problem D

Upsolved by zerol.

题意：坐电梯。给出每个人的到达时间和要去的楼层（都是从第 0 层出发）。电梯会到电梯中人要去的最高层，再回到 0 层。你可以选择电梯在 0 层停多久。求送完所有人所需要的最短时间。

题解：首先让到达楼层单调减少（否则前面的人去的楼层低的话就绑在后一个人身上）。$f[i]=\min_{j<i}\{\max\{f[j], t[i]\} + 2 h[j+1]\}$。维护这个 max 的分界线（只会右移），分界线的左边肯定是跳 j 最大的（也就是 h[j+1] 最小），分界线右边的要挑 f[j]+2h[j+1] 最小的，这部分用一个 set 维护一下。

Problem J

Upsolved by ultmaster.

题意：给一个数列。每次询问一个区间。问区间内的数组成的多重集有多少个子集的和是 $m$ 的倍数。

题解：离线。按区间分治。横跨两边的双向背包合并。否则递归。听起来很简单。

其实做的时候还是想生成函数优化就已经凉了。完全没有考虑离线。所以，划重点：离线。

Problem K

Solved by zerol. 02:56 (+3)

题意：询问一个串中某个串不重叠的最多出现次数。

题解：首先 ultmaster 观察出答案不会太大，对询问去重后最多 nlogn。然后 SAM，树上启发式合并得到每个结点的 EndPos 集合，然后暴力回答对应到该结点的所有询问（在 set 中二分找下一个、下一个）。总体复杂度 $O(n\log ^2 n)$。

zerol: 记住，SAM 空间就是要无脑开两倍。不要一些两倍一些不两倍，很不稳的。

另解：（如果我这个是标答的话应该没那么多人过，于是我去看了别人的代码，发现十分暴力。）直接哈希，考虑询问中出现的所有不同长度，求出原串中该长度的所有串的哈希对应的答案。总复杂度 $O(n \sqrt{n} \log n)$。

另：也有用自动机做的，也有用自动机+KMP做的，也有用 Trie 做的。所以其实怎么搞都可以？

Problem L

Upsolved by ultmaster.

题意：给一个无向图，问给每条边加税后，分别会有多少个点从起点出发涨价了。转化一下就是说：给一个 DAG，问删掉每条边之后，各有多少个点从 DAG 的最左端不连通。

题解：显然对于入度大于等于 2 的点，它删掉任意一条入边都是不影响的。

考虑一种增量构造一棵树的方法：DAG 拓补排序之后，一个一个点加进来。对于某个点 $v$，如果入度为 1，即只有一条边 $(u,v)$，则将 $(u,v)$ 加入树中；如果入度为 $k$ ($k > 1$)，即存在 $(u_1,v),(u_2,v),\ldots,(u_k,v)$，则将 $(LCA(u_1,u_2,\ldots,u_k), v)$ 加入树中。这种做法的正确性在于：对于有多条边进来的点，只有所有这些分支都挂了它才到达不了；那么我们不妨直接将它和「所有分支」的公共祖先相连。

这样的话删边问题就转化成了树上删边问题（也就是说只有删树上的边才是有用的），删树上边造成的损失就是子树的大小。注意树上有些边是我们自己加的，这些边不能累计入答案。

这题面向标程编程了。LCA 都能写错我是不是傻逼？