2018 ACM-ICPC Xuzhou Regional Onsite

Replay

zerol: 来了

ultmaster:

• 只做了半道题是怎么回事啊？
• 赛后发现傻逼题还不如不要发现呢。难受 QAQ~
• WF 顺位 3，岌岌可危。（然而已经没救了
• 食堂又远又不好吃。
• 出租车坑。
• 要不是这个比赛我有可能永远都不会听说矿大这个学校。
• 回想了一下这好像是第二次有教练跟来的比赛。上一次是 16 年北京。

kblack:

• 高铁定晚了，导致来回的时间都很蛋疼，酒店虽然贵了点，但是房间大小好评。
• 刘爷爷好强啊。
• 成就：罚时担当——贡献全部六发罚时。
• 嗦不粗发，相距 364 个行星日整，上次被卡金，这次怕是要被卡 Final，而且全是因为罚时，还都是我干的。
• 没什么能多说了，自闭去了。
• 血拼 EC 2018？

Problem A

Solved by kblack. 00:50 (+3)

此处省略一万字。

Problem C

Upsolved by ultmaster.

题意：有一条折线，两端有两个人，A 要走到 B，B 要走到 A，他们的高度需要始终保持一致。求最小路程和。

题解：三维状态 (i,j,h) 表示 A 在第 i 条折线上，B 在第 j 条折线上，它们的一致高度是 h 的最小路程。然后跑 Dijkstra 即可。

此题是出题人眼中的签到题。但事实上现场过了没几个队，而且实现起来可能较为繁琐。有几个需要注意的地方（可能会好写一点）：

• 每段折线都看成是左闭右开的。没有右端点。最后一条折线只有左端点。
• 搜下一状态时，可以把某一个人看成是主动方，另一个人看成是被动方。主动方先动，动完了以后被动方要去它所在的位置左右看，有没有合适的地方能走过去。对于每个能走的位置都是合法的后继状态。
• 主动方不能不动，被动方可以不动。
• 每一步只在一条线段上走，不要因为是平的之类的情况而一步多动。
• 注意折线某一段是平的情况。在这种情况下「第 i 条折线上高度为 h 的位置」可以更精确地定义为：第 i 条折线上第一次出现高度 h 的位置。转移过状态时候，可能会需要对状态进行校正。

Problem D

Upsolved by ultmaster.

题意：给定矩阵 $M$ 是一个 $n \times n$ 的连通矩阵。对于一个长度为 $n$ 的由 $1$ 到 $n$ 组成的序列，如果相邻两个数在连通矩阵中都是连通的，则该序列是合法的。求某个序列的所有本质不同的合法子序列的出现次数的三次方的总和。

题解：一个重要的观察是：统计三次方等价于在三个序列中寻找相同序列对。令 $f(i,j,k)$ 为三个序列中结尾分别在 $i$, $j$, $k$ 的对数，显然有

$\displaystyle f(i,j,k) = [a_i=a_j=a_k] (1 + \sum_{1 \le i' < i} \sum_{1 \le j' < j} \sum_{1 \le k' < k} f(i',j',k') [M(a_{k'}, a_i) = 1] )$

可以使用按值归类的方法来优化这个 DP，可惜复杂度是四次方的。

下面的优化过程参考了网友们的做法了。

• 首先交换求和号次序变成：$\displaystyle \sum_{1 \le j' < j} \sum_{1 \le k' < k} \sum_{1 \le i' < i} f(i',j',k') [M(a_{k'}, a_i) = 1]$。
• 令 $\displaystyle h(i,j,k) = \sum_{1 \le i' < i} f(i',j,k) [M(a_k, a_i) = 1]$，那么原式变成 $\displaystyle \sum_{1 \le j' < j} \sum_{1 \le k' < k} h(i,j',k')$。
• 令 $\displaystyle g(i,j,k) = \sum_{1 \le k' < k} h(i,j,k')$，那么原式变成 $\displaystyle \sum_{1 \le j' < j} g(i,j',k)$。

注意到如果对 f, g, h 在某一维上计算前缀和后，可以很方便地在 $O(1)$ 时间内计算 f, g, h。最终复杂度是 $O(n^3)$ 的。

Problem F

Unsolved. (-11)

题意：求一个字符串 S 中的本质不同非空子串 T 的数量，满足不存在 TP 是 S 的子串且 TP 和 PT 完全一致。

题解（伪）：如果 P 的长度小于 T，那么 P 的最小循环节是 T 的循环节，否则 T 是 P 的循环节。后缀树上启发式合并得到出现位置集同时维护相邻两个位置的差 d。一个长度为 $l$ 的子串不计当且仅当存在 $d \le \frac l2$ 或 $l=d$，用 pb_ds 和 set 随便维护一下就能 T 到生活不能自理了。

Problem G

Solved by zerol. 01:14 (+)

题意：从给定的若干条路径中选取 k 条，使得路径交至少为 1 个点。

题解：枚举路径交的 LCA，设为 u。设有 s 条路径经过了 u，有 c 条路径的 LCA 恰好是 u，那么这个点上的计数是 $\binom{s}{k} - \binom{c}{k}$。LCA + 差分前缀和 + 预处理组合数就好了。

Problem H

Solved by kblack. 03:05 (+2)

题意：$n$ 个区间，$k$ 染色使得有 $k$ 种颜色的区间最长。

题解：扫描线，贪心，set 里扔缺的颜色和可用线段，每当颜色不够 $k$ 的时候才延迟区间染色。

Problem I

Upsolved by ultmaster.

题意：问有多少个 1 到 n 的排列，使得：用给定的 $k$ 个排序对子作用（使 $a_u$ 和 $a_v$ 有序）后，整个序列会变成 Almost sorted（最长上升子序列是 $n-1$）。

题解：倒推。先搜出所有上升子序列是 $n-1$ 的序列，然后依次枚举、逆转排序对子的作用，计数即可。

注意，时限其实很紧，不能太过暴力。比如把所有序列全部枚举出来暴力去重，对于每个终态序列把所有初态序列枚举出来分别暴力去重，都是不能通过的。还应注意到，不是所有 $2^k$ 种作用方案都是可行的，比如作用了第 $i$ 个之后，如果 $a_{u_i} > a_{v_i}$，那么这个对子肯定没有作用，所以是不合法的，需要去掉。不难发现，对于每个终态序列，从后往前做一个 DFS，每一步的决策（这两个数换还是不换）一旦确定下来后，这个分支和其他分支中产生的序列是没有交集的（有交集的情况都会被不合法给卡掉）。所以对于这一阶段其实是没有 log 的。

出题人说这题也是签到题，不过又过了没几个人。我觉得在赛场上神智不清的情况下，即使选择了这题，也搞不出来。

Problem M

Solved by kblack & ultmaster. 02:17 (+1)

题意：$n$ 个点的凸包，在 $m$ 个点中选最小个数个，使得凸包能被照亮。

题解：求出每个灯能照亮的区间，然后就是求最小个区间能覆盖整个凸包。据说是个经典问题。数据范围很小，暴力就行。

计算几何签到，乱换上机间不仅丢了一血，还 WA 了一发。