ICPC 2019 World Finals 部分题解

Wallbreaker5th大约 5 分钟

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

比赛链接：Codeforces Gymopen in new window

A. Azulejos

题意

有两排各 $n$ 个商品，各有价格和高度。分别排列前排、后排的商品，满足两行价格各自都单调不降，且对应位置的前排商品高度小于后排，或判断无解。 $n\leq 5\times 10^5$ 。

题解

先对前后两排排序，从左往右扫，每次会考虑上下各自一段相同价格的商品。取出数量较少的一段，不妨设其为前排，则将其按照高度从大到小排序，依次找到高度大于它最小的后排商品（把高的商品保留到后面）；最后会剩下后排的一段相同价格的商品，接下来再取新的一段的前排的相同价格的商品。

有一段从左到右的折线作为地面。现希望修一座桥，距海平面高度为 $h$ ，从左端到右端。桥分为若干段，段的切换点必须是折线的折点，有连向地面的柱子。每段桥会有一个半圆形拱，直径为段的宽度，顶端抵到桥面，地形不能到达拱的上方。一段桥面有 $\beta$ 乘以桥面长度平方的代价，一个柱子有 $\alpha$ 乘以柱子高度的代价。求最小代价。 $n\leq 10^4$ ，坐标范围 $10^5$ 。10 s。

题解

$n^2$ ，考虑一个右端点可以从哪些左端点转移来。一个左端点合法，要求在右端点之前的所有折点合法。合法有两种可能：在拱的范围之外（即折点在一个 $r\times 2r$ 的矩形之外）（对应 $r$ 的一个后缀）、与圆心的距离平方小于等于半径（解一元二次不等式，得到一个 $r$ 的区间）；每个点得到合法 $r$ 的两个区间，可以转化为合法左端点的两个区间（由于坐标范围足够小，可以 $O(V)$ 预处理代替每次 lower_bound/upper_bound）。为了判断哪些左端点合法，要求这个左端点符合所有折点给出的要求，从而对于每个折点做两个区间加，最后查询哪些点结果为 $i$ ，即被所有折点允许。

D. Circular DNA

题意

给定一个环状序列，每个元素是某种括号的左/右括号。求一个断开序列的位置，最大化满足【这种括号对应的子序列合法】的括号的数量，若有多个最优答案输出最靠前的一个位置。 $n\leq 10^6$

题解

首先只考虑左右括号数量相等的种类。通过先求一遍各个括号的前缀和最小值，可以知道位置 $0$ 对应每个括号的第几层。再以这个层数为初始数，对于每种括号求前缀和，前缀和为 $0$ 时在此处断开就可以使得这种括号合法。从而可以一边扫，一边维护每种括号的前缀和，同时统计为 $0$ 的括号数，从而比较得到答案。

E. Dead-End Detector

题意

给定一无向简单图。定义从 $u$ 到 $v$ 的路口为死路，当且仅当从 $u$ 出发，往 $v$ 走，之后不通过原地掉头无法回到 $u$ 。一个死路要立标牌，当且仅当不存在另一个死路，使得这个死路出发不能到达另一个死路。求有哪些死路要立标牌。 $n\leq 5\times 10^5$ 。

题解

~~致敬传奇签到题。~~

一个路口是死路，当且仅当它不能到达一个边双。先做边双缩点，设原本有大于一个点的边双缩成黑点。则若一颗树全是白点，其只需要在每个叶子向上立标牌；否则，以黑色点为根 DFS，如果一个点子树里面包含黑色点，且其连向一个全是白色点的子树，则这个边也要立标牌。

G. First of Her Name

题意

有 $n$ 个字符串，每个串都是之前某个串在开头添加一个字符得到。有 $k$ 个查询，每次给一个串，问有多少串以这个查询开头。 $10^6$ 。

题解

将给定串当作在后缀添加字符，查询倒转。对查询建 AC 自动机，对给定串建树；在给定串的树上 DFS 的同时，在 AC 自动机上走；搜到给定串后，在 AC 自动机的结点上加一；最后在 fail 树上求子树和。

H. Hobsons' trains

题意

给定一张图，每个点恰有一出边。对于每个点，求有多少点不超过 $k$ 步可以到达该点。 $n\leq 5\times 10^5$ 。

题解

题述为基环树森林。对于每个基环树，把环断掉；对于每个点，其要对其到祖先的链 $k+1$ 个结点做 $+1$ ；对于树，朴素树上差分即可；对于环，链加可能会被拆成两段。

J. Miniature Golf

题意

$p$ 个人， $n$ 轮游戏，每人每轮游戏有得分。考虑一个正整数 $i$ ，将所有得分对 $i$ 取 $\min$ ，随后对所有人得分排序，一个人的排名定义为分数小于等于他的人的数量。求 $i$ 变化时，每人的排名的最小值。 $p\leq 500,n\leq 50$ 。6 s。

题解

考虑每个人的得分随 $i$ 的变化，其是一条折线，折线之间有至多 $p^2 n$ 级别的交点。为了找到所有交点，扫描线，每遇到一个左端点就枚举所有还存活的线段。两条线段交在一起，会让其中一者排名下降；两条线段从交点分开，会让其中一者排名上升；需要讨论亿些边界情况。从而可以求出所有人各个时刻的排名变化，从而得到答案。