NOI 1997 Day2 算法题解

零、背景

1997 年举办的 NOI 算法比赛中，《Day1》的题解我已经分享过了。

这篇文章继续分享 1997 年 NOI Day2 的算法题解。

PS：题解代码已上传至网盘，公众号回复 NOI-1997 可获取。

一、最优乘车

题目：给你 M 条公交车路线，问从起点 1 到终点 N 的最少换乘次数。

思路：BFS。

做法：把每条公交线路当作图上的一个点；若两条线路有公共站点，则它们之间连边（表示可以在该站换乘）。同时记录哪些线路经过站点 1，以及哪些线路经过站点 N。
从所有经过站点 1 的线路作为 BFS 起点，按“换乘次数”做层序遍历；当首次到达任意一条经过站点 N 的线路时，当前层数就是最少换乘次数。
构图可以用“站点 -> 线路列表”的反向索引加速，整体复杂度可控。

二、卫星覆盖

题意：给 N 个卫星，每个卫星可以覆盖一个三维立方体空间，问 N 个卫星覆盖的总体积。

思路：离散化。

首先，为了避免负数下标带来的麻烦，可以把所有坐标整体平移一个常数，保证坐标都为非负。

然后对三个维度分别离散化，把空间切分为 X*Y*Z 个互不重叠的小长方体；每个小长方体都可以用其一个角点的离散坐标唯一表示。

最后枚举每个卫星：用离散坐标把它覆盖的立方体拆分成若干个小长方体，累计这些小长方体的体积；对被重复覆盖的部分做去重，即可得到总体积。

复杂度：O(N*R^3*log N)。其中 R 代表单个维度离散后的坐标数量级。

理论上这个式子看起来偏大，但在题目数据范围下，用数组实现可以通过。

三、文件匹配

题意：给定两组文件名：一组“应当匹配”，一组“禁止匹配”。需要构造一个通配符表达式，尽可能多地匹配“应当匹配”的文件名，同时不能匹配到任何“禁止匹配”的文件名。

通配符规则如下：

?：匹配任意一个字符。
*：匹配任意零个或多个字符。

如果存在多个答案：
优先输出能匹配“应当匹配”文件名数量最多的表达式。
若匹配数量相同，则输出长度最短的表达式。
若仍有多个，输出任意一个即可。

思路：暴力搜索 + 剪枝。

假设我们实现了一个函数，能够枚举“某个文件名”对应的所有可匹配表达式。
那么先用“禁止匹配”的文件名生成黑名单表达式集合（所有会匹配到这些文件名的表达式都算黑名单）。
再用“应当匹配”的文件名统计每个表达式能匹配的数量。
最后在所有表达式中筛选：不在黑名单里，且匹配数量最多；若并列则取长度最短。

这里唯一需要担心的是：单个文件名对应的表达式数量会不会太多，导致空间/时间爆炸。

针对这个问题，可以用两个剪枝规则：

第一，不可能存在连续的两个 *。
因此在生成表达式时，若上一个字符是 *，则不再继续放 *。

第二，*? 与 ?* 是等价的，都代表至少匹配一个字符。
因此可以约定一种规范形式：* 后面不能放 ?。

有了这两个规则，表达式的数量就被有效控制住了。
假设文件名长度为 L，很多人会先粗略估计为 3^L（例如 L=8 时是 6561 个）。

但实际上还存在一个容易忽略的情况：* 允许匹配空串，会让组合数额外膨胀。
不过可以证明最优表达式的长度不会超过 L+1。
因此可以用长度上界剪枝，把搜索空间限制在 3^(L+1) 的量级内。

注意事项：在表达式的最前面和最后面也可以插入一个 *。
我一开始没考虑到这个情况，只得了 45 分。

四、最后

这场比赛整体其实不难。

尤其是最后一题文件匹配：据洛谷题题目的说法，这题并没有被严格证明的“靠谱正解”，但用暴力搜索配合剪枝也能通过。

我的做法是先枚举出所有可能的通配符表达式，在保证空间不爆炸的前提下统计并筛选出最优答案；从实现角度看，这个思路就是正解。

《完》

-EOF-

本文公众号：天空的代码世界

个人微信号：tiankonguse

公众号ID：tiankonguse-code