题解 | #ICPC North Central NA Contest 2020#

ICPC North Central NA Contest 2020

兰州大学版题解

2021.08.12

A. LogDB

给定一组类似于函数调用的 $facts$ 和一组查询，根据指定的匹配规则确定每个查询可以匹配多少 $fact$ ，需要注意数据的读入与处理。

每个 $fact$ 都有一个名称，并包含若干变量，每次查询也有一个名称包含若干变量，当且仅当查询的名称与 $fact$ 名称相同，且两者包含的变量全部成功匹配时，两者才能算成功匹配。

变量的匹配规则如下：

变量 "_" 可以匹配 $fact$ 中任意名称的变量。
以 "_" 开头且长度大于 $1$ 的变量也可以匹配 $fact$ 中任意名称的变量，但是如果在一次查询中该变量出现超过一次，那么其必须匹配 $fact$ 中名称相同的变量。
其余情况下，只能匹配名称完全相同的变量。

例如，如下输入：

test(arg1, arg1)
test(arg1, arg2)

test(__arg2, __arg2)
test(__arg1, __arg2)
test2(_, __)
test(_, __)
test(_, __)

相应输出为：

对于每次查询，暴力枚举所有 $fact$ ，逐一判断是否能够成功匹配。

时间复杂度 $O(200^{3})$ ，可以进行字符串 $Hash$ ，将时间复杂度降至 $O(200^{2})$ 。

B. Ride-Hailing

给定一个 $n$ 个点， $m$ 条边的有向图，同时给出图上的若干条“出租车线路”，第 $i$ 条线路由从 $t_{i}$ 时刻出发，从 $u_{i}$ 到达 $v_{i}$ ，现在询问最少要多少出租车司机就可以完成所有线路。

我们可以以 $n^{3}$ 的代价求出两两点之间的最短路。在这样的情况下，我们可以得知一名司机如果接下了第 $i$ 个任务，最早能在哪个时刻到达 $v_{i}$ 完成任务。接下来以 $k^{2}$ 的时间两两枚举，我们也能知道一名司机在接下了第 $i$ 个任务后，来不来得及去做第 $j$ 个任务。

我们把任务之间的关系表示成一张有向图 $G$ 。 $u$ 向 $v$ 有边当且仅当完成第 $i$ 项任务后，可以接着去完成第 $j$ 个任务。可以发现，我们要求的答案就是“在这张图里，最少用多少条链可以覆盖所有的点”，也就是最小链覆盖问题。

完成最小链覆盖问题可以用二分图匹配。注意到有向图 $G$ 中每有一条边被链覆盖，总链数就少了 $1$ 。同时注意到，一个点最多只有一条出边与入边被链覆盖。于是我们构造二分图，将每个点拆成出点与入点,出点与入点各自构成一个集合。对于 $G$ 中一条 $u$ 向 $v$ 的边，就让 $u$ 的出点连向 $v$ 的入点。这样情况下，每一种二分图的匹配方案就对应了一种链覆盖方案，并且可以发现，最小链覆盖 $=n-$ 二分图最大匹配数。

求出二分图最大匹配可以用 $dinic$ 最大流算法，复杂度 $O(k^2 \sqrt{k})$ .

时间复杂度 $O(n^3+k^2+k^2 \sqrt{k})$ 。

C. Redundant Binary Notation

给定两个数 $N,t$ ，将十进制数 $N$ 转化为二进制数，且二进制数的每一位范围从传统的 $[0,1]$ 变为 $[0,t]$ ，求合法转化的不同方案数。

考虑进行 $DP$ ，定义 $dp(i,j)$ 表示用 $i$ 位去构成数字 $j$ 的方案数，那么有 $dp(i,j)=\displaystyle \sum_{k=0}^{t}dp(i-1,j-k \times 2^{i-1})$ ，可以考虑进行记忆化搜索，最后的答案即为 $\displaystyle \sum_{i=1}^{\log_{2}{N}+1}dp(i,N)$ 。

时间复杂度 $O(t \log{N})$ 。

D. Substring Characters

对于一个字符串 $s$ ，找出所有不同的最短连续子串，其中任一子串都完整包含 $s$ 所包含的所有字符。

注意，连续子串不能是原字符串 $s$ 自身。

例如 104001144，共有三种这样的子串 104，4001，0114。而 1040 或 04001 都不可以，因为它们不是各自位置最短的。

注意到字符串长度最多只有 $80$ ，字符集大小只有 $26+26+10=62$ 。

对于每个左端点 $i$ ，暴力找到满足条件的最小右端点 $end(i)$ ，使得子串 $[i,end(i)]$ 能够完整包含 $s$ 所包含的所有字符，由于 $end(i+1) \geq end(i)$ ，因此复杂度为 $O(62 \times 80)$ 。

如果 $end(i)$ 存在且 $end(i) \neq end(i+1)$ ，则 $[i,end(i)]$ 就是一种答案，注意其不能是原字符串 $s$ 自身，且相同的子串只计算一次。

单次时间复杂度 $O(62 \times 80)$ ，总时间复杂度 $O(100 \times 62 \times 80)$ 。

E. Curve Speed

按要求计算 $V=\sqrt{(R*(S+.16))/.067}$ ，四舍五入取整，需要注意数据的读入。

单次时间复杂度 $O(1)$ ，总时间复杂度 $O(100)$ 。

F. Agamemnon’s Odyssey

给定一棵 $N$ 个点的带边权树，可以任选一点作为起点，每条边最多经过 $k$ 次，但只有在首次经过时才会贡献大小等于边权的价值，求价值和最大的一条路径。

不难发现，当 $k \geq 2$ 时，每条边都可以访问到，最大价值和为整棵树的边权和。

当 $k=1$ 时，相当于求树的直径，可以使用两次 $DFS$ 或者树形 $DP$ 等方法。

时间复杂度 $O(N)$ 。

G. Safest Taxi

给定了一个 $N$ 条纵线， $M$ 条横线组成的方格网络，方格中的每一条边都是一条路，题目给定其中的 $D$ 条路，每条路都有双向道，每个道有 $K$ 个车道。要求在题目规定的车辆行驶准则下，一辆车从给定的起点到终点，用不多余 $X$ 次左转和不多于 $Y$ 次的变道可以实现的最短路。

发现 $N,M,K,X,Y$ 其实都很小，而题目所求的是起点到终点的最短路，因此考虑分层图最短路(基于状态图的最短路)。结合题目所要求的的条件，可以找出以下几个条件来规定点的状态：所处街道，所面向方向(双向车道的哪一车道)，所在车道(共 $K$ 条)，已经使用的左转次数 $X$ ，已经使用的变道次数 $Y$ 。这样建图的点数量级是 $O(NMKXY)$ ，也即 $O(NMKXY)$ 的状态，边数略多一点。按照题目中的给定条件建完边跑最短路即可。

时间复杂度 $O(NMKXY \log{(NMKXY)})$ 。

H. Digital Speedometer

给出一个浮点数序列，按要求进行取整，需要注意数据的读入。

若当前的数为 $s$ ，取 $i=\lfloor s \rfloor$ ，使得 $i \leq s \lt i+1$ ，按照如下规则对 $s$ 进行取整，得到 $s'$ ：

$s=0$ ，那么 $s'=0$ 。
$s \in (0,1]$ ，那么 $s'=1$ 。
$s \in [i,i+t_{f})$ ，那么 $s'=\lfloor s \rfloor$ 。 $(i \gt 0)$
$s \in (i+t_{r},i+1)$ ，那么 $s'=\lceil s \rceil$ 。 $(i \gt 0)$
$s \in [i+t_{f},i+t_{r}]$ ，若 $s$ 比上一个 $s'$ 小，那么新的 $s'=\lceil s \rceil$ ，否则 $s'=\lfloor s \rfloor$ 。 $(i \gt 0)$

时间复杂度 $O(1000)$ 。

I. Staggering to the Finish

给出一个椭圆形跑步场地的各种参数，在不同的跑步距离 $D$ 下，求出各跑道运动员的起点位置，使得所有运动员沿自己的跑道到终点，运动的路程都等于 $D$ 。

很容易理解的计算几何问题，不过实现起来并不容易，细节较多。

预先计算出每条跑道的弯道长度，从终点开始反方向(顺时针)推导出起点落在弯道还是直道。

如果落在直道，很容易直接得出结果；如果落在弯道，需要借助弧长公式 $l=\alpha R$ ，求出对应圆心角 $\alpha$ ，然后得出其相对于圆心的坐标，进而得出结果。

时间复杂度 $O(100N)$ 。

J. Ada Loveslaces

在一个二维平面上有 $2N$ 个洞，分为两排。两排间隔为 $s$ ，同一排中相邻两洞的距离为 $d$ ，每个洞的深度为 $t$ 。给定一条鞋带，长度为 $L$ ，要求确定符合题目穿线规定的穿完点后线头所剩余长度在 $[f_{\min},f_{\max}]$ 范围之间的穿线方案数。

因为从洞 $0$ 出来的鞋带必须进入 $1$ (或者可以看作洞 $1$ 出来必须进入洞 $0$ )，并且鞋带一定从 $2N-2,2N-1$ 两个洞穿出，此外，题目还要求穿线需要对称。因此我们可以只考虑某一边，另一边视为对称即可。

发现 $N$ 范围很小，所有洞的经过顺序方案数一共也只有 $(N-2)!$ 个，同时算上各个穿孔的方式，总的方案数上限也只有 $3^{N-1} \times (N-2)!$ ，当 $N$ 开满到 $9$ 时，这个数也只有 $33000000$ 而已，完全可以爆搜。所以直接暴力遍历所有可能方式，然后统计有串到最后一个洞所需的鞋带长度。对于询问处理一下长度在 $[L-2f_{\max},L-2f_{\min}]$ 区间内的方案数即可。

单次时间复杂度 $O(3^{N-1} \times (N-2)!)$ ，但不会跑满，复杂度远小于预期。

K. ICPC Record Matching

给出两张表，用空行分割。每张表中包含若干条信息，每条信息包含名字、姓氏、邮箱，需要注意数据的读入。

现在需要找出两张表之间无法匹配的信息，然后按要求输出。

一条信息无法匹配当且仅当在另一张表中不存在至少满足如下要求之一的信息(忽略大小写)：

名字和姓氏对应相同
邮箱相同

例如 Freya Campbell Freya_Campbell9926@ubusive.com 和 freya Campbell campbellf@deavo.net 可以成功匹配，因为名字和姓氏对应相同。

又例如 Danny West Danny_West6110@twipet.com 和 Daniel West Danny_West6110@twipet.com 可以成功匹配，因为邮箱相同。

这样，对于一张表中的每条信息，在另一张表中进行查询即可。

暴力时间复杂度 $O(102 \times 2000^{2})$ ，可以进行字符串 $Hash$ 并使用 $STL$ 容器优化存储与查询，将时间复杂度降至 $O(2000 \log{2000})$ 。

L. Codenames

给出桌游“Codenames”的玩法：

玩家分为两队，有 $n$ 张牌和 $m$ 个线索，这 $n$ 张牌各属于一个线索中。
这 $n$ 张牌有 $4$ 种类别：清白者，红队特工，蓝队特工，刺客。
双方轮流操作。每个回合，行动方选定一个线索与次数 $k$ ，重复 $k$ 次从该线索中选出一张牌，每次进行以下判断：

如果选中刺客，游戏结束，行动方输掉游戏。
如果选中己方特工，继续下一次选取取。
如果选中对方特工或清白者，直接结束这一回合，轮到对方行动。

当有一方特工被全部选出后，该方获胜。

现在询问，如果双方都采取最优策略，谁会获胜。

我们考虑设计一个状压 $dp$ 状态。 $f[S][t][v][k]$ 表示在剩余牌的状压状态为 $S$ ，目前行动方为 $t$ ，选取了线索 $v$ ，准备选取 $k$ 次时的获胜概率。另外同样设计一个 $dp$ ， $g[S][t]$ 表示在剩余牌的状压状态为S，目前行动方为 $t$ 时，该方最优状态下的获胜概率。

转移 $f$ 时枚举选的是线索 $v$ 中的哪一张牌，当 $k$ 等于零或者未选中己方特工时直接从 $g[S'][1-t]$ 转移( $S'$ 表示选取该牌后的状态)，剩余情况从 $f[S'][t][v][k-1]$ 转移。转移 $g$ 时直接枚举选择的线索 $v$ 与选择的次数 $k$ ，从对应的 $f[S][t][v][k]$ 中选取一个最大值。

$f$ 的总状态数为 $2^n \times m \times n$ ，每种状态转移方案为 $n$ ， $g$ 总状态数为 $2 \times 2^n$ ，每种状态转移方案为 $n \times m$ 。总复杂度 $O(2^n \times n^2 \times m)$ ，在该数据范围下大概为 $700 000 000$ ，考虑这题的时限与不满的状态数，可以通过。

注意 $dp$ 的状态转移不太好写，建议使用记忆化搜索。