DAMON THRONE ·岱陌存理模拟赛系列 提高组 题目名称积木整理实验观测流水线分拣系统 题目类型传统型传统型传统型传统型 目录prun watch wafer sort 可执行文件名prun watch wafer sort 输入文件名prun.in watch.in wafer.in sort.in 输出文件名prun.out watch.out wafer.out sort.out 每个测试点时限1.0 秒1.0 秒1.0 秒1.0 秒 内存限制512 MiB 512 MiB 512 MiB 512 MiB 测试点数目20 20 20 20 测试点是否等分是是是是 提交源程序文件名 对于C++ 语言prun.cpp watch.cpp wafer.cpp sort.cpp 编译选项 对于C++ 语言‐O2 ‐std=c++14 ‐static 【考生须知】 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. main 函数的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 提交的程序代码文件的放置位置请务必参照各自的具体要求。 4. 因违反上述要求而出现的错误或问题，申诉不予受理。 5. 若无特殊说明，结果的比较方式为全量比较（中间过程行不能为空格和文字符 号）。 6. 选择提交的程序源文件必须不大于100KB。 7. 程序内使用的变量命名与题目中的命名要求一致。 8. 全国统一使用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内 存32GB。以上配置以此配置为准。 9. 只提供Linux 格式附带样例文件。 10. 请确保在当前最新公布的NOI Linux 下进行，各语言的编译器版本应为标准版 本。 岱陌存理提高组积木整理(prun) 积木整理(prun) 【题目描述】 Y 同学正在整理一排共N 个积木，每个积木的高度为ai。已知所有积木的高度两 两不同。为了满足陈列要求，Y 同学需要将当前的积木序列A = (a1, a2, . . . , aN) 转化为 目标序列B = (b1, b2, . . . , bM)。 在整理过程中，Y 同学可以使用以下两种操作： 1. 机. 械. 化. 清. 理. ：消耗x 单位能量，选择序列中连续的k 个积木并将其全部移除。注 意，每次必须正好移除k 个积木。 2. 手. 工. 拆. 除. ：消耗y 单位能量，选择序列中相邻的两个积木，将其中高度较低的一 个移除。 Y 同学希望通过上述操作，以最小的能量消耗将序列A 变为序列B（B 是A 的子 序列）。如果无法达成目标，请输出−1。 【输入格式】 从文件prun.in 中读入数据。 第一行包含两个整数N 和M，分别表示原积木序列的长度和目标序列的长度。 第二行包含三个整数x, k, y，分别表示机械化清理的能量消耗、清理的范围长度以 及手工拆除的能量消耗。 第三行包含N 个整数a1, a2, . . . , aN，表示原序列中各积木的高度。 第四行包含M 个整数b1, b2, . . . , bM，表示目标序列中各积木的高度。 【输出格式】 输出到文件prun.out 中。 输出一个整数，表示完成转化所需的最小能量消耗。若无解，则输出−1。 【样例1 输入】 1 5 2 2 5 2 3 3 3 1 4 5 2 4 3 5 【样例1 输出】 1 8 第2 页共35 页 岱陌存理提高组积木整理(prun) 【样例2 输入】 1 4 4 2 5 1 4 3 4 3 1 2 4 2 4 3 1 【样例2 输出】 1 ‐1 【样例3 输入】 1 4 4 2 2 1 11 3 1 3 2 4 4 1 3 2 4 【样例3 输出】 1 0 【数据范围与约定】 对于100% 的数据，保证1 ≤ N,M ≤ 2 × 105，1 ≤ x, y ≤ 109，1 ≤ k ≤ N， 1 ≤ ai, bi ≤ N。 测试点编号分值N,M ≤ 特殊性质 1 ∼ 2 10 10 无 3 ∼ 6 20 2 × 105 特殊性质A 7 ∼ 10 20 2 × 105 特殊性质B 11 ∼ 14 20 5000 无 15 ∼ 20 30 2 × 105 无 • 特. 殊. 性. 质. A：保证x ≤ y · k。 • 特. 殊. 性. 质. B：保证k = 1。 第3 页共35 页 岱陌存理提高组积木整理(prun) 【题解】 solve 积木整理（Pruning） 这题的关键在于先把最终必须保留的积木钉死，再把问题拆成若干个互不影响的删 除区间。每一段区间只需要考虑两件事：这一段能不能只靠手工拆完，以及机械化清理 到底该用一次还是尽量多用。 • 算. 法. 1：状态压缩暴搜 适. 用. 条. 件. ：对于前2 个数据，N ≤ 10。 核. 心. 思. 路. ：直接按“当前还剩哪些位置”做状态压缩。设一个二进制状态S 表示 原序列中哪些位置还活着，那么当前序列就是把这些位置按原顺序拎出来形成的 新序列。我们从初始状态(1 << N) − 1 出发，枚举两种转移：一种是选当前序 列中相邻的两个积木，若左低右高就删左，若右低左高就删右，代价加上y；另 一种是选当前序列中连续恰好k 个活着的位置一起删掉，代价加上x。由于每次 操作都会减少活着的点数，所以这是一个天然的DAG，直接记忆化搜索或倒着 DP 都行。最后判断哪些状态对应的当前序列恰好等于B，取最小值即可。 这一做法完全不需要发现什么性质，纯靠暴力把所有合法删法搜出来。时间复杂 度O(2N · N2)，期望得分：10 分。 • 算. 法. 2：特殊性质A，先匹配保留位置，再按段贪心 适. 用. 条. 件. ：对于第3 ∼ 6 个数据，保证x ≤ y · k。 核. 心. 思. 路. ：先扫描一遍A，把B 作为子序列依次匹配出来。若某个bi 在后面找 不到，说明连保留哪些积木都做不到，直接输出−1。由于ai 两两不同，B 中每 个值在A 中的位置唯一，所以最终必须保留的位置也是唯一确定的。这样一来， 问题就被切成了若干段：每一段都是两个保留积木之间的一串“必须删掉”的连 续积木，段与段之间互不影响，答案就是各段最优值之和。 设某一段长度为s，左右边界保留积木的最大值为bd，这一段内部最大值为mx。 若mx > bd，说明这一段里存在一个“比两边保留积木都高”的积木，它不可能 只靠手工拆除。原因很简单：如果全靠手工，这个段内最大值一定会活到很后面， 但等别的小积木都删得差不多时，它左右只剩更矮的积木或边界，自然无法作为 “较低者”被删掉。所以这种段至少要用一次机械化清理；若此时s < k，连一次 长度恰好为k 的清理都塞不进去，直接无解。 在特殊性质A 下，由于x ≤ y · k，机械化清理的单位代价不比手工差，因此只要 这一段可行，显然就是能用机械就尽量用机械。于是这一段的最优代价直接是 ⌊ s k ⌋ x + (s mod k)y 危险段和安全段统一都是这个式子，只不过危险段还要额外满足s ≥ k。整题线 性扫一遍即可。时间复杂度O(N)，期望得分：20 分。 第4 页共35 页 岱陌存理提高组积木整理(prun) • 算. 法. 3：特殊性质B，也就是k = 1 适. 用. 条. 件. ：对于第7 ∼ 10 个数据，保证 k = 1。 核. 心. 思. 路. ：当k = 1 时，机械化清理等价于“花费x 删除任意一个积木”。这样 问题就好理解很多了。仍然先把B 在A 中匹配出来，然后逐段处理。设某段长 度为s，边界最大值为bd，内部最大值为mx。 如果mx ≤ bd，这段是安全的，说明完全可以靠手工从两边往中间一点点删掉； 但既然机械化现在也能单点删除，那每个元素直接选更便宜的方式即可，因此这 一段代价就是s · min(x, y)。 如果mx > bd，这一段中那个最大值必须用机械化清掉一次，否则最终删不掉； 而除了它以外的其他元素，都可以在它还活着的时候作为“较低者”被手工删掉。 所以这一段的最优代价就是二者取小： min(sx, x + (s − 1)y) 前者表示全用机械化，后者表示只把那一个“危险最大值”用机械化删掉，其余 都手工。整题仍然线性可做。时间复杂度O(N)，期望得分：20 分。 • 算. 法. 4：正解，分段讨论+ 两种费用公式取最小值 适. 用. 条. 件. ：对于第11 ∼ 20 个数据，以及全部数据。 核. 心. 思. 路. ：还是先把最终要保留的积木位置全部找出来。由于所有高度两两不同， B 中每个值在A 中至多出现一次，因此如果B 是A 的子序列，那么这些保留位 置是唯一确定的。设它们依次为p1, p2, . . . , pM。那么要删除的部分正好分成以下 几段： – 开头一段(1 ∼ p1 − 1)； – 中间若干段(pi + 1 ∼ pi+1 − 1)； – 结尾一段(pM + 1 ∼ N)。 这些段互不干扰，因为机械化清理不能跨过我们必须保留的积木，手工拆除也只 会在当前相邻元素之间发生。所以总答案就是每一段的最优代价之和。 下面只考虑一段。设这段左右边界下标为l, r，表示真正要删除的是(l, r) 中间这 s = r − l − 1 个积木。若某一侧不存在边界，就把该侧边界高度视作0，因为所 有高度都至少是1。记 – bd = max(al, ar)，表示两侧保留积木的较大值； – mx 表示这段内部的最大值。 先看“什么时候必须用机械化清理”。若mx > bd，则这一段的最大值比两边保 留积木都大。它如果不被机械化清掉，就永远不可能作为某对相邻积木中的较小 者被手工删除，因此这一段至少要有一次机械化清理；若同时s < k，那么连一 次长度恰为k 的机械化清理都做不了，直接无解。 接下来考虑费用。设 c1 = ⌊ s k ⌋ x + (s mod k)y 第5 页共35 页 岱陌存理提高组积木整理(prun) 这表示“尽量多用机械化清理”，即能拆成多少个长度为k 的整块就拆多少块， 剩下不足k 的再手工删。再设 c2 = x + (s − k)y 这表示“只用一次机械化清理”，并且这一次一定拿去清掉那一个必须被清掉的 段内最大值；剩下的所有积木都在它还活着的时候手工删掉。这个策略之所以可 行，是因为除了段内最大值外，其余所有元素总能在某个时刻挨着一个更大的邻 居，于是可以作为较小者被手工删去。 于是分两类讨论： – 若mx ≤ bd，这一段是安全段，不需要被强制机械化。此时要么全手工，费 用为sy；要么大量用机械化，费用为c1。取最小即可。 – 若mx > bd，这一段是危险段，至少要有一次机械化。此时答案为min(c1, c2)； 若s < k 则无解。 换句话说，单段最优值就是 safe : min(c1, sy) danger :   −1, s < k min(c1, c2), s ≥ k 这里为什么只需要在“尽量多用机械化”和“只用一次机械化”之间二选一，而 不用枚举机械化次数？因为如果某一段决定用了至少一次机械化，那么其中有一 次是被“危险最大值”强制出来的；除此之外，每多用一次机械化，本质上就是 拿一次代价为x 的操作去替换掉k 次总代价为ky 的手工删除。所以： – 如果x < ky，那额外机械化越多越赚，最优就是一路用到不能用，也就是 c1； – 如果x ≥ ky，那额外机械化不赚甚至亏，最优就是只保留那一次必须的机 械化，也就是c2。 最后把所有段的代价累加即可。实现时完全不需要什么复杂数据结构，按你给出 的标准程序那样扫一遍匹配位置，再对每一段顺手扫出最大值就行，总复杂度已 经是线性的。时间复杂度O(N)，期望得分：100 分。 • 实. 现. 细. 节. 1. 先用双指针扫描A 和B，找出每个bi 在A 中的位置pi。若有任何一个没 找到，直接输出−1。 2. 写一个函数处理单段cal(l, r)，这里删除的是(l, r) 中间的元素；令不存在 的边界高度视作0。 3. 在函数里先求这段长度s、边界最大值bd、段内最大值mx。 4. 按上面的分类公式返回这一段最小代价；若无解返回−1。 第6 页共35 页 岱陌存理提高组积木整理(prun) 5. 主程序里依次处理前缀段、中间段、后缀段，只要某一段返回−1，整题 就是−1。 第7 页共35 页 岱陌存理提高组实验观测(watch) 实验观测(watch) 【题目描述】 Y 同学正在参与一项深空探测计划，负责观测分布在一条直线轨道上的N 个精密 传感器。这条轨道被划分为109 个连续的观测区段，从左到右依次编号为1, 2, . . . , 109。 第i 个传感器位于编号为Ai 的区段中。为了收集所有传感器的数据，Y 同学准备 了P 台小型无线摄像机和Q 台大型无线摄像机。 在开始观测前，Y 同学需要设定一个正整数w 作为摄像机的基准拍摄跨度。设定 后，摄像机的功能如下：* 一台小型摄像机可以覆盖最. 多. 连续的w 个区段。* 一台大型 摄像机可以覆盖最. 多. 连续的2w 个区段。 由于任务要求，所有摄像机在观测开始后位置必须固定，不可移动。Y 同学希望仅 使用这P + Q 台摄像机就覆盖所有传感器所在的区段。 为了降低设备损耗，基准拍摄跨度w 越小越好。请你帮助Y 同学计算出能够覆盖 所有传感器所在区段的最小w 值。 【输入格式】 从文件watch.in 中读入数据。 第一行包含三个整数N, P,Q，分别表示传感器的数量、小型摄像机的数量和大型 摄像机的数量。 接下来的N 行，每行包含一个整数Ai，表示第i 个传感器所在的区段编号。 【输出格式】 输出到文件watch.out 中。 输出一行一个整数，表示能够覆盖所有传感器所在区段所需的最小w 值。 【样例1 输入】 1 3 1 1 2 2 3 11 4 17 【样例1 输出】 1 4 第8 页共35 页 岱陌存理提高组实验观测(watch) 【样例2 输入】 1 13 3 2 2 33 3 66 4 99 5 10 6 83 7 68 8 19 9 83 10 93 11 53 12 15 13 66 14 75 【样例2 输出】 1 9 【数据范围与约定】 对于100% 的数据，保证1 ≤ N ≤ 2000，1 ≤ P,Q ≤ 105，1 ≤ Ai ≤ 109。 测试点编号分值N ≤ 特殊性质 1 ∼ 4 20 20 无 5 ∼ 8 20 2000 特殊性质A 9 ∼ 12 20 2000 特殊性质B 13 ∼ 16 10 500 无 17 ∼ 20 30 2000 无 • 特. 殊. 性. 质. A：保证Q = 0，即仅使用小型摄像机。 • 特. 殊. 性. 质. B：保证P = 0，即仅使用大型摄像机。 第9 页共35 页 岱陌存理提高组实验观测(watch) 【题解】 solve 题意概括 给出N 个传感器所在的位置Ai。现在有P 台小型摄像机和Q 台大型摄像机，先 选一个正整数w，之后每台小型摄像机最多覆盖连续的w 个区段，每台大型摄像机最 多覆盖连续的2w 个区段。所有摄像机位置固定，要求把所有传感器都覆盖到，求最小 的w。 输入规模里，N ≤ 2000，但P,Q 可以达到105，所以真正麻烦的地方不在点数，而 在于如何把“摄像机数量很多、长度有两种、答案要求最小”这三件事拼到一起。 保留样例： 1 3 1 1 2 2 3 11 4 17 1 4 这组数据里答案是4。当w = 4 时，小型摄像机覆盖4 个区段，大型摄像机覆盖8 个区段，已经能把三个点全部拍到；再小就不行了。 样例分析 先把位置排好序，得到2, 11, 17。 如果取w = 4，那么： • 小型摄像机最多覆盖连续4 个区段，可以放在[2, 5]，拍到位置2。 • 大型摄像机最多覆盖连续8 个区段，可以放在[11, 18]，同时拍到位置11 和17。 这样一共正好用掉一台小型和一台大型，把所有传感器都覆盖了，所以w = 4 可 行。 再看w = 3。这时大型摄像机最多只能覆盖连续6 个区段。位置11 和17 之间相差 6，想同时拍到这两个点，至少需要覆盖从11 到17 这7 个区段，因此一台大型摄像机 做不到。小型摄像机更不可能把这两个点接起来，所以w = 3 不可行。 于是最小答案就是4。 题目分析 先抓住一个单调性：如果某个w 能完成覆盖，那么更大的w 也一定能完成。所以 外层可以二分答案，问题就变成： 第10 页共35 页 岱陌存理提高组实验观测(watch) 给定一个固定的w，能不能用不超过P 台小型摄像机和不超过Q 台大型摄 像机覆盖全部点？ 接下来所有算法，都是在做这个可行性判定。 还有一个很关键的小性质：把传感器位置排好序后，假设当前最左边还没被覆盖的 点是ai，那么下一台摄像机一定可以把左端点贴到ai 这里。因为你把摄像机再往右放， 只会让它左边浪费；往左贴住当前最左未覆盖点，不会少覆盖任何需要的点，还可能让 右边多吃一点。 于是，对固定的w，每个位置i 的选择其实只有两种： • 用一台小型摄像机，覆盖掉从ai 开始、长度不超过w 的这一段，跳到下一个没 覆盖的位置。 • 用一台大型摄像机，覆盖掉从ai 开始、长度不超过2w 的这一段，跳到下一个没 覆盖的位置。 记： • s1[i] 表示从第i 个点开始放一台小型摄像机后，下一个没有被覆盖的点编号； • s2[i] 表示从第i 个点开始放一台大型摄像机后，下一个没有被覆盖的点编号。 这样一来，原题就被转成了“在有向跳跃图上能不能从1 跳到n + 1”。 • 算. 法. 1： 先说最朴素的想法，适用于前四个点那种很小的数据。对固定的w，从当前最左 未覆盖点出发，枚举下一台摄像机是小型还是大型，然后递归下去。状态可以写 成“当前处理到第几个点、还剩多少台小型、还剩多少台大型”。因为每一步都 只分两叉，写起来不复杂，拿来验证思路很方便。 这套做法的问题也很直接：状态树会爆得很快。哪怕加上一点剪枝，只要N 和摄 像机数量上来，分支数就扛不住了。实现时最容易出错的是区间长度的含义—— 覆盖连续k 个区段，右端点应当是左端点加上k − 1。时间复杂度最坏接近指数 级。时间复杂度：O(2P+Q) 量级。期望得分：20 分。 • 算. 法. 2： 特殊性质A 和B 其实都很规整：如果只有一种摄像机，那就只剩一个固定长度 的覆盖问题。此时对固定的w，永远从当前最左未覆盖点开始，放一台摄像机把 它能覆盖的最远范围吃掉，再继续处理下一个没覆盖点。 这个贪心是对的，因为每一台摄像机都必须先把当前最左未覆盖点照到，而把左 端点贴住这个点时，向右覆盖到的点数已经是最多的。既然每一步都不吃亏，整 体就不会吃亏。 所以当Q = 0 时，用小型摄像机一直跳s1；当P = 0 时，用大型摄像机一直跳 s2。如果在摄像机数量用完前跳到了n+1，说明当前w 可行。实现时记得把P,Q 先截成不超过N，因为超过N 的摄像机根本没有意义。时间复杂度：O(N)。期 望得分：40 分。 第11 页共35 页 岱陌存理提高组实验观测(watch) • 算. 法. 3： 一般情况里，两种摄像机都能用，最直接的做法是二维动态规划。设dp[x][y] 表 示用了x 台小型摄像机、y 台大型摄像机后，最远能处理到的“第一个未覆盖点” 的编号。初始dp[0][0] = 1。 如果当前是i = dp[x][y]，那么： – 再用一台小型摄像机，就转移到dp[x + 1][y] = max(dp[x + 1][y], s1[i])； – 再用一台大型摄像机，就转移到dp[x][y + 1] = max(dp[x][y + 1], s2[i])。 因为一个状态只需要记住“当前最左未覆盖点在哪里”，后面怎么选只和这个信 息有关，所以这个状态设计是够用的。 这版写法已经相当扎实了，但状态数是O(PQ)。虽然P,Q 可以先截成不超过 N，可满数据下还是会变成O(N2) 个状态，再乘上二分答案，常数不算小。用 在N ≤ 500 的普通数据上很稳，往大了跑就有点发紧。实现时注意数组里存的 是“下一个未覆盖点”，不是“已经覆盖了多少个点”，两者很接近，但边界不一 样。时间复杂度：O(PQ)，结合二分后为O(PQlog 109)。期望得分：50 分左右。 • 算. 法. 4： 继续观察算法3，会发现二维表里很多信息是重复的。比如如果大型摄像机数量 很少，那我们没有必要把整张P ×Q 的表都铺开；只要枚举“大型摄像机用了多 少台”，同时在这一层里维护“达到每个位置至少要用多少台小型摄像机”就够 了。 假设Q ≤ P，我们把“大型摄像机使用次数”当作层数。定义f[i] 表示：在已经 固定使用了若干台大型摄像机的前提下，把第一个未覆盖点推进到i，最少需要 多少台小型摄像机。初始时一台大型都没用，f[1] = 0。 现在分两步处理： 1. 在当前层内，只继续使用小型摄像机。 如果当前到达了位置i，且用了f[i] 台小型摄像机，那么再加一台小型摄 像机后就能到达s1[i]，于是有f[s1[i]] = min(f[s1[i]], f[i] + 1)。 由于s1[i] > i，这是一个从左往右的DAG 式转移，顺着扫一遍就能把这 一层补全。 2. 再额外使用一台大型摄像机，跳到下一层。 设新的数组是g，那么g[s2[i]] = min(g[s2[i]], f[i])。 这里小型摄像机数量不增加，只是多用了一台大型摄像机。 每做完一层，都检查一下能否已经到达n + 1 且小型摄像机数量不超过P。如果 可以，这个w 就合法。 如果反过来是P < Q，完全对称处理即可：枚举小型摄像机层数，层内用大型摄 像机做最小值转移。 这版的核心想法是：把数量更少的那一类摄像机拿来做“层数”，把数量更多的 那一类摄像机压成“这一层里的最小代价”。这样二维DP 被压成了一维滚动数 第12 页共35 页 岱陌存理提高组实验观测(watch) 组。 正确性来自两点： – 当前最左未覆盖点确定后，下一台摄像机的最优放法是确定的，只会跳到 s1[i] 或s2[i]。 – 对固定层数，f[i] 维护的是到达位置i 的最小代价，层内转移始终只会从更 左的位置走到更右的位置，因此单次顺扫不会漏。 实现时有三个地方最容易写错： 第一，s1, s2 都要基于排好序的点来做； 第二，覆盖长度为w 或2w 时，右端应当写成ai + w − 1 或ai + 2w − 1； 第三，P,Q 都应先截成不超过N，否则会白白多做很多层。 时间复杂度：单次判定为O(N min(N, P,Q))，结合二分后为O(N min(N, P,Q) log 109)。 期望得分：100 分。 参考实现 1 #include<bits/stdc++.h> 2 using namespace std; 3 using ll = long long; 4 5 const int N = 2005; 6 const int I = 1e9; 7 8 int n, p, q, mp, mq; 9 ll a[N]; 10 int s1[N], s2[N]; 11 int f[N], g[N]; 12 13 bool chk(ll w) { 14 int j1 = 1, j2 = 1; 15 for (int i = 1; i <= n; i++) { 16 if (j1 < i) j1 = i; 17 while (j1 <= n && a[j1] <= a[i] + w ‐ 1) j1++; 18 s1[i] = j1; 19 20 if (j2 < i) j2 = i; 21 while (j2 <= n && a[j2] <= a[i] + 2 * w ‐ 1) j2++; 22 s2[i] = j2; 23 } 第13 页共35 页 岱陌存理提高组实验观测(watch) 24 25 mp = min(p, n); 26 mq = min(q, n); 27 28 if (!mq) { 29 int c = 0, i = 1; 30 while (i <= n && c < mp) { 31 i = s1[i]; 32 c++; 33 } 34 return i == n + 1; 35 } 36 37 if (!mp) { 38 int c = 0, i = 1; 39 while (i <= n && c < mq) { 40 i = s2[i]; 41 c++; 42 } 43 return i == n + 1; 44 } 45 46 if (mq <= mp) { 47 for (int i = 1; i <= n + 1; i++) f[i] = I; 48 f[1] = 0; 49 50 for (int b = 0; b <= mq; b++) { 51 for (int i = 1; i <= n; i++) { 52 if (f[i] >= mp) continue; 53 int j = s1[i]; 54 if (f[j] > f[i] + 1) f[j] = f[i] + 1; 55 } 56 57 if (f[n + 1] <= mp) return 1; 58 if (b == mq) break; 59 60 for (int i = 1; i <= n + 1; i++) g[i] = I; 第14 页共35 页 岱陌存理提高组实验观测(watch) 61 for (int i = 1; i <= n; i++) { 62 if (f[i] > mp) continue; 63 int j = s2[i]; 64 if (g[j] > f[i]) g[j] = f[i]; 65 } 66 67 for (int i = 1; i <= n + 1; i++) f[i] = g[i]; 68 } 69 } else { 70 for (int i = 1; i <= n + 1; i++) f[i] = I; 71 f[1] = 0; 72 73 for (int b = 0; b <= mp; b++) { 74 for (int i = 1; i <= n; i++) { 75 if (f[i] >= mq) continue; 76 int j = s2[i]; 77 if (f[j] > f[i] + 1) f[j] = f[i] + 1; 78 } 79 80 if (f[n + 1] <= mq) return 1; 81 if (b == mp) break; 82 83 for (int i = 1; i <= n + 1; i++) g[i] = I; 84 for (int i = 1; i <= n; i++) { 85 if (f[i] > mq) continue; 86 int j = s1[i]; 87 if (g[j] > f[i]) g[j] = f[i]; 88 } 89 90 for (int i = 1; i <= n + 1; i++) f[i] = g[i]; 91 } 92 } 93 94 return 0; 95 } 96 97 int main() { 第15 页共35 页 岱陌存理提高组实验观测(watch) 98 ios::sync_with_stdio(0); 99 cin.tie(0); 100 cout.tie(0); 101 102 cin >> n >> p >> q; 103 for (int i = 1; i <= n; i++) cin >> a[i]; 104 sort(a + 1, a + n + 1); 105 106 ll l = 1, r = 1000000000LL; 107 while (l < r) { 108 ll m = (l + r) >> 1; 109 if (chk(m)) r = m; 110 else l = m + 1; 111 } 112 113 cout << l << "\n"; 114 return 0; 115 } 复杂度分析 最终正解的时间复杂度为O(N min(N, P,Q) log 109)，空间复杂度为O(N)。 第16 页共35 页 岱陌存理提高组流水线(wafer) 流水线(wafer) 【题目描述】 Y 同学正在设计一套半导体自动化生产流水线。该系统包含N 条平行的传送带，每 条传送带上有M 个加工站。我们将第i 条传送带的第j 个加工站记为(i, j)。 在系统运行过程中，存在K 条特殊的跨. 带. 快. 速. 通. 道. 。第i 条快速通道允许晶圆从 传送带ai 的加工站bi 直接传输至传送带ci 的加工站di。由于跨带传输会经过能量补偿 器，每通过一次这样的通道，晶圆携带的能量值会增. 加. hi 个单位。已知所有快速通道均 满足ai < ci。 在同一条传送带i 上，晶圆可以在相邻的加工站之间双向移动。每当晶圆在同带内 从站点(i, j) 移动到站点(i, k) 时，由于摩擦损耗，能量值会减. 少. |j −k|×xi 个单位，其 中xi 为该传送带的单位损耗系数。 晶圆初始位于(1, 1) 站点，最终需要被送往(N,M) 站点进行封装。请计算在整个 流程中，晶圆能. 量. 损. 耗. 的最小值（能量损耗= 总损耗值- 总增加值）。如果晶圆由于路 径断裂无法到达终点，请输出QAQ。 【输入格式】 从文件wafer.in 中读入数据。 第一行包含一个整数T，表示测试用例的数量。 对于每个测试用例：第一行包含三个整数N,M,K，分别表示传送带数量、每条带 上的站点数和快速通道数量。第二行包含N 个整数x1, x2, . . . , xN，表示各条传送带的 损耗系数。接下来的K 行，每行包含五个整数ai, bi, ci, di, hi，描述一个快速通道的起 始站点、目标站点和能量增益。 【输出格式】 输出到文件wafer.out 中。 对于每个测试用例，输出一行一个整数，表示最小能量损耗。如果无法送达，输出 QAQ。 【样例1 输入】 1 4 2 5 3 3 3 5 17 8 1 4 4 1 3 3 3 4 5 3 1 5 2 5 第17 页共35 页 岱陌存理提高组流水线(wafer) 6 3 2 5 1 6 7 6 3 3 8 5 17 8 1 4 2 9 1 3 3 3 4 10 3 1 5 2 5 11 3 2 5 1 6 12 5 3 1 13 5 17 8 1 4 14 1 3 5 3 100 15 5 5 5 16 3 2 3 7 5 17 3 5 4 2 1 18 2 2 5 4 5 19 4 4 5 2 3 20 1 2 4 2 2 21 3 3 5 2 4 【样例1 输出】 1 16 2 QAQ 3 ‐90 4 27 【数据范围与约定】 对于100% 的数据，保证2 ≤ N,M ≤ 105，1 ≤ K ≤ 105，1 ≤ xi ≤ 106，1 ≤ hi ≤ 106。 所有测试用例的 Σ N, Σ M, Σ K ≤ 105。 测试点编号分值N,M ≤ K ≤ 特殊性质 1 ∼ 4 20 100 100 无 5 ∼ 8 20 105 105 特殊性质A 9 ∼ 12 20 105 105 特殊性质B 13 ∼ 16 20 2000 2000 无 17 ∼ 20 20 105 105 无 • 特. 殊. 性. 质. A：保证对于所有通道i，均有ci = ai + 1。 • 特. 殊. 性. 质. B：保证所有的xi 均相等。 第18 页共35 页 岱陌存理提高组流水线(wafer) 【题解】 solve 题意概括 有N 条传送带，每条传送带有M 个站点。晶圆一开始在(1, 1)，目标是到达(N,M)。 在同一条传送带内，横向移动的代价是距离乘上这一行的损耗系数xi；此外还有K 条快速通道，可以从(ai, bi) 直接跳到(ci, di)，并获得hi 的收益，也就是总损耗会减少 hi。所有通道都满足ai < ci，所以只会往更靠后的传送带跳。 题目要我们求从起点到终点的最小总损耗，如果到不了就输出QAQ。单组数据里 N,M,K 都能到105，但所有测试点的 Σ N, Σ M, Σ K ≤ 105，所以可以做线性或线性 对数级别的算法，不能碰整张N ×M 网格。 下面只保留第一组样例： 1 5 3 3 2 5 17 8 1 4 3 1 3 3 3 4 4 3 1 5 2 5 5 3 2 5 1 6 对应输出是： 1 16 样例分析 起点在(1, 1)，终点在(5, 3)。 一种走法是先在第1 条传送带上从站点1 走到站点3，代价是2 × 5 = 10。然后使 用第一条快速通道，从(1, 3) 跳到(3, 3)，收益是4，当前总损耗变成10 − 4 = 6。 到了第3 条传送带之后，如果走到站点2，还要再付出1 × 8 = 8 的代价，总损耗 变成14。接着使用第三条快速通道，从(3, 2) 跳到(5, 1)，收益是6，总损耗降到8。 最后在第5 条传送带上从站点1 走到站点3，代价是2 × 4 = 8，总损耗变成16。 另一条通道(3, 1) → (5, 2) 也能走，但要先在第3 行多走一步到站点1，这条路线 会更差，所以答案是16。 题目分析 • 算. 法. 1： 先按最朴素的思路想，把每个站点(i, j) 都看成图上的一个点。同行相邻站点之 间连边，边权是对应的移动代价；每条快速通道也是一条边，边权是−hi。因为所 有快速通道都只会从小行号跳到大行号，图里不会出现由快速通道构成的回路， 第19 页共35 页 岱陌存理提高组流水线(wafer) 再配合同行移动，整张图依然可以跑最短路。 这个做法只适合最小的测试点。因为点数是N ×M，边数同样是这个级别，哪怕 一组数据只有100 × 100 也已经有一万级别的点了；一旦上到满数据，图大小直 接爆炸。 真正写的时候，快速通道收益要转成负边权，最短路模型本身没问题，但图根本 建不出来。时间复杂度是O(NM log(NM) + K)。期望得分：20 分。 • 算. 法. 2： 第一种做法的问题不在“最短路”这件事本身，而在于我们傻乎乎把所有站点都 建出来了。事实上，一条传送带上真正有意义的位置很少：只需要保留所有快速 通道的出发点、到达点，再额外保留起点(1, 1) 和终点(N,M)。 原因很简单。假设我们已经到达第i 行上的某个位置，这一行里除了横着走和走 传送门，没有别的操作。你如果在同一行中间停了几次，最后的总代价和直接从 起点位置走到终点位置是一样的，中间停靠不会带来额外收益。所以一条最优路 径在某一行里，真正值得作为“状态”记录的，只可能是准备走传送门的位置， 或者这一行本身就是起点/终点。 这样我们给每一行做坐标压缩，设这一行保留下来的位置个数是si，定义状态 fi,j 表示到达第i 行第j 个保留位置的最小损耗。 对于小规模数据，可以直接在一行内部暴力转移：如果这一行的保留位置是 p1, p2, . . . , psi，那么 fi,v = min u (fi,u + |pu − pv| · xi) 然后再把能走的快速通道全部松弛出去。 这样做已经不需要碰整张网格了，状态数变成所有保留点总数，数量级是O(K)。 但如果一行上的保留点很多，同行内部两两转移会变成平方级。对于N,M,K ≤ 2000 的测试点，这个做法已经够用。 实现时要注意，同一行内同一个列坐标可能被多个通道重复出现，压缩前要去重， 否则状态会重复。时间复杂度是O( Σ s2i + K logK)。期望得分：40 分。 • 算. 法. 3： 再往前走一步，先看特殊性质A：所有快速通道都满足ci = ai + 1。这意味着状 态只会从第i 行流向第i + 1 行，整件事就是一个非常标准的“按行递推”的分 层DP。 这时候第二种做法里最慢的部分，其实就是这一句： min u (fi,u + |pu − pv| · xi) 这在一维数轴上是很好处理的。把这一行的保留位置按列坐标从小到大排序。 如果最优来源在左边，那么从左往右扫一遍就够了，因为从pj−1 走到pj 多付出 的代价只是(pj − pj−1) · xi，于是可以做转移 fi,j = min (fi,j , fi,j−1 + (pj − pj−1) · xi) 第20 页共35 页 岱陌存理提高组流水线(wafer) 同理，再从右往左扫一遍，就把最优来源在右边的情况也补全了。 这样，同一行内部不再需要两两枚举，做两次线性扫描就能把这一行所有横向移 动的最优值算出来。然后再把这一行的所有传送门向下一行转移。 这个版本已经能把特殊性质A 跑满，而且它其实已经很接近正解了。时间复杂 度是O(( Σ si) + K logK)。期望得分：60 分。 • 算. 法. 4： 满分做法和上一个版本的状态设计一模一样，只是把“只能跳到下一行”的限制 去掉。 关键点在于：虽然现在快速通道可以一下跳过很多行，但题目仍然保证ai < ci。 也就是说，状态永远只会从小行号流向大行号，整张状态图按行号天然就是一个 DAG。 这件事非常重要。它说明我们仍然可以按1, 2, . . . ,N 的顺序处理每一行： – 先把这一行当前已经收到的状态值做两次扫描，补全这一行内部横向移动的 最优值； – 再把这一行所有快速通道拿出来，用它们去松弛未来某些行上的状态。 因为不会有回边，所以一行一旦处理完，就再也不需要回头修改它。 于是最终算法就是： 1. 每一行收集所有有用列坐标：这一行作为快速通道起点的列、作为快速通 道终点的列，再加上起点行的1 和终点行的M。 2. 每一行排序、去重，建立压缩后的状态数组。 3. 初始化f(1, 1) = 0，别的状态设成无穷大。 4. 按行从小到大处理： – 左扫一遍； – 右扫一遍； – 枚举这一行发出的每条快速通道，设它从(i, b) 到(r, d)，收益是h，那 么做 f(r, d) = min (f(r, d), f(i, b) − h) 5. 最后看(N,M) 对应的压缩状态是否可达。 这个做法能通过全部数据。 实现时最容易出错的地方有三个： 第21 页共35 页 岱陌存理提高组流水线(wafer) 第一，起点(1, 1) 和终点(N,M) 一定要手动塞进压缩坐标里，不然最 后连答案状态都不存在。 第二，某些行可能完全没有有用位置，这种行直接跳过即可，不需要 开状态。 第三，无穷大要开成long long 级别，快速通道会带来负贡献，不能 用int。 时间复杂度是O(( Σ si) + K logK)，而 Σ si = O(K)，所以整体就是 O(K logK)。期望得分：100 分。 参考实现 1 #include<bits/stdc++.h> 2 using namespace std; 3 using ll = long long; 4 5 const int N = 100005; 6 const ll inf = (ll)4e18; 7 8 struct Ed { 9 int a, b, c, d, h; 10 }; 11 12 int t, n, m, k; 13 int x[N]; 14 Ed e[N]; 15 vector<int> ps[N], eg[N]; 16 vector<ll> dp[N]; 17 18 int fd(int r, int v) { 19 return lower_bound(ps[r].begin(), ps[r].end(), v) ‐ ps[r].begin(); 20 } 21 22 int main() { 23 ios::sync_with_stdio(0); 24 cin.tie(0); 25 cout.tie(0); 26 第22 页共35 页 岱陌存理提高组流水线(wafer) 27 cin >> t; 28 while (t‐‐) { 29 cin >> n >> m >> k; 30 31 for (int i = 1; i <= n; i++) { 32 cin >> x[i]; 33 ps[i].clear(); 34 eg[i].clear(); 35 dp[i].clear(); 36 } 37 38 ps[1].push_back(1); 39 ps[n].push_back(m); 40 41 for (int i = 1; i <= k; i++) { 42 cin >> e[i].a >> e[i].b >> e[i].c >> e[i].d >> e[i].h; 43 ps[e[i].a].push_back(e[i].b); 44 ps[e[i].c].push_back(e[i].d); 45 eg[e[i].a].push_back(i); 46 } 47 48 for (int i = 1; i <= n; i++) { 49 if (ps[i].empty()) continue; 50 51 sort(ps[i].begin(), ps[i].end()); 52 ps[i].erase(unique(ps[i].begin(), ps[i].end()), ps[i].end()); 53 54 dp[i].assign(ps[i].size(), inf); 55 } 56 57 dp[1][fd(1, 1)] = 0; 58 59 for (int i = 1; i <= n; i++) { 60 if (ps[i].empty()) continue; 61 62 int s = ps[i].size(); 第23 页共35 页 岱陌存理提高组流水线(wafer) 63 64 for (int j = 1; j < s; j++) { 65 ll v = dp[i][j ‐ 1] + 1ll * (ps[i][j] ‐ ps[i][j ‐ 1]) * x[i]; 66 if (v < dp[i][j]) dp[i][j] = v; 67 } 68 69 for (int j = s ‐ 2; j >= 0; j‐‐) { 70 ll v = dp[i][j + 1] + 1ll * (ps[i][j + 1] ‐ ps[i][j]) * x[i]; 71 if (v < dp[i][j]) dp[i][j] = v; 72 } 73 74 for (int id : eg[i]) { 75 int p = fd(i, e[id].b); 76 ll v = dp[i][p] ‐ e[id].h; 77 78 int r = e[id].c; 79 int q = fd(r, e[id].d); 80 81 if (v < dp[r][q]) dp[r][q] = v; 82 } 83 } 84 85 ll ans = dp[n][fd(n, m)]; 86 87 if (ans >= inf / 2) cout << "QAQ\n"; 88 else cout << ans << '\n'; 89 } 90 91 return 0; 92 } 复杂度分析 最终正解的时间复杂度是O(K logK)，空间复杂度是O(K + N)。 第24 页共35 页 岱陌存理提高组分拣系统(sort) 分拣系统(sort) 【题目描述】 Y 同学正在设计一套自动化物流分拣系统。该系统包含n 条并行的传送带，编号为 1, 2, . . . , n。 每条传送带被划分为m+1 个工位。我们将第a 条传送带的第b 个工位记为(a, b)。 初始状态下，每条传送带内部的工位是连通的，即对于所有的1 ≤ a ≤ n 和1 ≤ b ≤ m， 工位(a, b) 与(a, b + 1) 之间由一条垂直的传送轨道相连。 为了实现跨轨道分拣，Y 同学需要执行q 次操作。操作分为以下两类： 1. 安. 装. 分. 流. 器. ：在相邻两条传送带的相同高度处安装一个分流器。具体地，在工位 (a, b) 与(a + 1, b) 之间建立一条双向水平连接轨道，其中1 ≤ a < n, 1 ≤ b ≤ m。 系统要求在任何时刻，每. 个. 工. 位. 最. 多. 只. 能. 连. 接. 一. 个. 分. 流. 器. 。 2. 分. 拣. 路. 径. 模. 拟. ：一个待分拣的包裹从起点(a, 1) 进入系统。包裹的移动逻辑如下： • 如果当前工位连接了一个在. 本. 次. 分. 拣. 任. 务. 中. 尚. 未. 经. 过. 的分流器，包裹将通 过该分流器移动到相邻传送带的对应工位（即从(a, b) 移动到(a ± 1, b)）； • 否则，包裹将沿着垂直轨道移动到当前传送带的下一个工位(a, b + 1)； • 当包裹到达任何一条传送带的第m + 1 个工位时，分拣过程结束。 需要注意的是，分流器是否被“经过”在每次查询中是独立判定的。Y 同学希望对 于每次类型2 的查询，你能告诉他包裹最终会停留在哪一条传送带上。 【输入格式】 从文件sort.in 中读入数据。 第一行包含三个正整数n, m, q，分别表示传送带数量、分拣工位长度以及操作总数。 接下来q 行，每行描述一个操作：1 a b：表示在工位(a, b) 与(a + 1, b) 之间安装 一个分流器。 2 a：表示一个包裹从(a, 1) 开始分拣，询问其最终到达的传送带编号。 【输出格式】 输出到文件sort.out 中。 对于每个类型2 的查询，输出一行一个整数，表示包裹最终停留的传送带编号。 【样例1 输入】 1 3 4 13 2 2 2 3 1 1 3 第25 页共35 页 岱陌存理提高组分拣系统(sort) 4 2 1 5 2 2 6 2 3 7 1 2 4 8 2 1 9 2 2 10 2 3 11 1 2 1 12 2 1 13 2 2 14 2 3 【样例1 输出】 1 2 2 2 3 1 4 3 5 3 6 1 7 2 8 3 9 2 10 1 【数据范围与约定】 对于100% 的数据，保证1 ≤ n, m, q ≤ 105，1 ≤ a ≤ n，1 ≤ b ≤ m。对于所有的类 型1 操作，满足1 ≤ a < n 且不会在同一工位重复安装分流器。 测试点编号分值n ≤ m ≤ q ≤ 特殊性质 1 ∼ 2 10 100 100 100 无 3 ∼ 6 20 105 105 105 特殊性质A 7 ∼ 10 20 105 105 105 特殊性质B 11 ∼ 14 20 2000 2000 2000 无 15 ∼ 20 30 105 105 105 无 第26 页共35 页 岱陌存理提高组分拣系统(sort) • 特. 殊. 性. 质. A：所有的类型1 操作（安装分流器）均发生在任何类型2 操作（分拣 模拟）之前。 • 特. 殊. 性. 质. B：保证所有安装的分流器其高度b 均满足b ≤ 100。 第27 页共35 页 岱陌存理提高组分拣系统(sort) 【题解】 solve 题意概括 有n 条传送带，每条传送带有m+1 个工位。初始时每条传送带内部上下连通；之 后会不断安装一些横向分流器，它们只会连在相邻两条传送带的同一高度上，而且同一 个工位至多连一条分流器。 查询时，一个包裹从(a, 1) 出发，从上往下走。到达某个工位时，如果这里连着一 个本次还没走过的分流器，就先横着过去；否则就继续往下走到下一层。问包裹最后会 落在哪条传送带。 输入包含两类操作：安装分流器，或者立刻询问某个起点的最终落点。数据范围是 n, m, q ≤ 105，所以不能按一次查询跑完整条路径。 保留样例： • 初始没有分流器时，查询2，答案就是2。 • 加入(1, 3) 这一条分流器后，1 和2 会在第3 层交换，3 不受影响。 • 再加入(2, 4) 后，路径会继续在第4 层发生一次交换。 • 最后加入(2, 1) 后，最前面又多了一次交换，路径结果再次改变。 样例分析 样例一开始没有任何分流器，所以第一条询问2 2 的答案就是2。 接着安装(1, 3)，也就是第3 层把第1 条和第2 条传送带连起来。 这时： • 从1 出发，前两层都只能往下走，到第3 层横跳到2，之后一路到底，所以答案 是2。 • 从2 出发，到第3 层会跳到1，答案是1。 • 从3 出发根本碰不到这条分流器，答案还是3。 再安装(2, 4)，也就是第4 层把第2 条和第3 条传送带连起来。 这时从1 出发，会先在第3 层从1 跳到2，再在第4 层从2 跳到3，所以答案变成3。 从2 出发会先跳到1，之后第4 层碰不到新的分流器，所以答案是1。 从3 出发只会在第4 层跳到2，答案是2。 最后安装(2, 1)，也就是第1 层把第2 条和第3 条传送带连起来。 这时： • 从1 出发，第1 层不动，第3 层跳到2，第4 层再跳到3，答案是3。 • 从2 出发，第1 层先跳到3，第3 层不动，第4 层再跳回2，答案是2。 • 从3 出发，第1 层先跳到2，第3 层再跳到1，答案是1。 样例里的所有输出就是按这个过程一步一步得到的。 第28 页共35 页 岱陌存理提高组分拣系统(sort) 题目分析 • 算. 法. 1： 先说最直接的做法。我们把每一层的横向连接关系存下来，安装操作就是修改这 一层的信息；查询时从起点传送带开始，从第1 层一路往下模拟到第m 层：如 果这一层当前所在位置有分流器，就横跳，否则继续下走。因为题目保证同一个 工位至多连一条分流器，所以一次查询里不会在同一层来回乱跳，这样直接写就 行。这个做法能过前1 ∼ 2 点和前11 ∼ 14 点的小数据，因为单次查询只要扫完 全部高度。真正写的时候要注意同一层的分流器是连在(a, b) 和(a + 1, b) 之间， 所以查询时只会发生相邻两条传送带的交换。时间复杂度是每次安装O(1)、每 次查询O(m)，总复杂度O(qm)。期望得分：30 分。 • 算. 法. 2： 特殊性质A 里，所有安装都在所有询问之前。这样时间这条轴就没意义了，整套 系统在回答查询前已经完全固定。于是每一层对传送带编号的影响，就是若干个 互不相交的相邻交换；从第1 层到第m 层依次作用下去，整套系统最后等价于 一个固定置换。我们可以先令pi = i，然后按高度从小到大处理所有分流器：如 果这一层有(a, b)，就交换当前的pa 和pa+1。全部处理完后，任意查询2 a 的答 案就是最终的pa。这个做法能吃掉特殊性质A 的20 分，因为没有在线变化，只 要预处理一次。实现时要记住：同一高度的分流器互不相交，所以这一层内部怎 么枚举都不会打架。时间复杂度是O(n + m + q)。期望得分：20 分。 • 算. 法. 3： 特殊性质B 说得更直接：所有分流器的高度都满足b ≤ 100。这意味着无论m 有 多大，真正会影响路径的只有前100 层，后面全是空的。于是安装照常维护，查 询时也不再扫到m，只模拟前100 层即可。这样就把原来的O(m) 查询压成了 O(100)，对q ≤ 105 完全够用。这一档的关键点在于：虽然操作顺序还是在线的， 但“有效高度”已经变成常数，所以根本不需要更复杂的数据结构。时间复杂度 是O(q · 100)。期望得分：20 分。 • 算. 法. 4： 满分做法要同时处理两个麻烦：一是操作是在线的，二是高度m 很大，不能每 次都从头扫到尾。先抓住一个很关键的事实：查询时，包裹从上到下经过每一层， 本质上就是“按高度顺序执行一串相邻交换”。也就是说，整道题可以看成一张 动态增加横边的竖直交换网络。 直接在线维护整张网络很难，但时间轴是可以分块的。设块长为B，按操作顺序 每B 个操作分成一块。处理当前块时，前面所有块里的分流器都已经确定存在， 它们对本块内的所有查询来说都是“老分流器”；当前块里的分流器则是“新分 流器”，它们对不同查询是否生效，要看安装时间是否早于这条查询。 这就把问题拆成了两部分： 1. 老分流器的作用对当前块内所有查询都是固定的。 第29 页共35 页 岱陌存理提高组分拣系统(sort) 2. 新分流器只有至多B 条，它们才是每条查询之间真正不同的地方。 接下来需要把“老分流器的固定作用”压成若干段映射。 我们给每条传送带的起点编号贴一个标签。标签只表示“这个起点来的包裹”，它 跟着交换往下走。对当前块里的所有查询，我们只关心一小撮标签： – 每个查询的起点标签一定要关心； – 当前块里每条新分流器，在它出现的位置上可能接触到两个标签，这两个标 签也要关心。 这一撮标签的数量是块内查询数加上块内分流器数的两倍，总共不超过2B。 然后做两遍扫描。 第. 一. 遍. 扫. 描. ：收. 集. 要. 追. 踪. 的. 标. 签. 。 只把已经读到的分流器全部按高度从小到大扫一遍，维护当前每条传送带上是什 么标签。遇到当前块里的新分流器时，看看它两端此刻分别是哪两个标签，把它 们加入追踪集合。这样一来，当前块里所有查询在整条路径上可能碰到的关键标 签，就都被我们抓到了。 第. 二. 遍. 扫. 描. ：把. 老. 分. 流. 器. 压. 成. 若. 干. 段. 映. 射. 。 仍然按高度从小到大扫。我们同时维护两套位置： – pos：所有“已读到的分流器”都算上时，每个被追踪标签当前在哪条传送 带上； – tp：只把当前块里的新分流器算上时，每个被追踪标签当前在哪条传送带 上。 当扫描到一条当前块里的新分流器时，说明在它和上一条新分流器之间，只有老 分流器在起作用。于是此时tp ‐> pos 这组对应关系，正好就是这一段老分流 器对传送带编号造成的固定映射。把这个映射记下来。然后继续往下扫。 这样整块会被切成若干段： 老映射0 → 新分流器0 → 老映射1 → 新分流器1 → · · · → 老映射k 对于当前块里的一条查询，只要从起点开始依次做这些事： – 先经过一段老映射； – 如果这一条新分流器的安装时间早于查询时间，就再做一次相邻交换； – 再经过下一段老映射； – 重复直到结束。 因为一块里新分流器最多B 条，所以一条查询只需要做O(B) 次转移。 这个做法真正成立的原因有两点： 1. 当前块外的分流器对本块内查询的状态完全一致，所以它们可以被整体打 包成固定映射； 第30 页共35 页 岱陌存理提高组分拣系统(sort) 2. 我们只在被追踪的那一小撮标签上建映射就够了，因为查询从头到尾只会 落在这些标签当前所在的位置上，不会跑到别的标签上去。 实现时有几个地方最容易写错： – 按块处理时，只能扫描“已经读到”的分流器，后面的块还没出现，不能提 前算进去； – 查询时，新分流器是否生效要判断它的时间是否满足“安装操作编号< 查 询操作编号”； – 同一高度上的分流器互不相交，所以把它们按读入顺序扫过去没有问题，结 果和同时交换一致； – 记录段映射时，映射的定义是“只过当前块新分流器得到的位置”到“把老 分流器也算上后的位置”，这一点别反了。 若块长取B ≈ 320，总复杂度能稳稳压进范围。时间复杂度是O ( q(n + m + q) B + qB ) 。 期望得分：100 分。 参考实现 1 #include<bits/stdc++.h> 2 using namespace std; 3 using ll = long long; 4 5 const int N = 100005; 6 const int B = 320; 7 const int C = B * 2 + 10; 8 const int H = 1031; 9 10 struct Tab { 11 int hd[H], nx[C], ky[C], vl[C], ct; 12 13 int hs(int x) { 14 x ^= x >> 16; 15 x ^= x << 5; 16 if (x < 0) x = ‐x; 17 return x % H; 18 } 19 20 void clr() { 21 memset(hd, 0, sizeof hd); 22 ct = 0; 第31 页共35 页 岱陌存理提高组分拣系统(sort) 23 } 24 25 void ins(int k, int v) { 26 int h = hs(k); 27 ++ct; 28 ky[ct] = k; 29 vl[ct] = v; 30 nx[ct] = hd[h]; 31 hd[h] = ct; 32 } 33 34 int get(int k) { 35 int h = hs(k); 36 for (int i = hd[h]; i; i = nx[i]) { 37 if (ky[i] == k) return vl[i]; 38 } 39 return ‐1; 40 } 41 }; 42 43 int n, m, q; 44 vector<pair<int,int>> sw[N]; 45 46 int cur[N], pos[N], vis[N]; 47 int tp[C], at[B + 5], bt[B + 5]; 48 Tab mp[B + 5]; 49 50 int main() { 51 ios::sync_with_stdio(0); 52 cin.tie(0); 53 cout.tie(0); 54 55 cin >> n >> m >> q; 56 57 for (int st = 0; st < q; st += B) { 58 int ed = min(q, st + B); 59 第32 页共35 页 岱陌存理提高组分拣系统(sort) 60 vector<pair<int,int>> qu; 61 for (int i = st; i < ed; i++) { 62 int op, a, b; 63 cin >> op >> a; 64 ‐‐a; 65 if (op == 1) { 66 cin >> b; 67 ‐‐b; 68 sw[b].push_back({i, a}); 69 } else { 70 qu.push_back({i, a}); 71 } 72 } 73 74 for (int i = 0; i < n; i++) vis[i] = ‐1; 75 76 vector<int> vc; 77 for (auto t : qu) { 78 int x = t.second; 79 if (vis[x] == ‐1) { 80 vis[x] = 1; 81 vc.push_back(x); 82 } 83 } 84 85 iota(cur, cur + n, 0); 86 for (int i = 0; i < m; i++) { 87 for (auto e : sw[i]) { 88 int a = e.second; 89 if (e.first >= st) { 90 int x = cur[a]; 91 int y = cur[a + 1]; 92 93 if (vis[x] == ‐1) { 94 vis[x] = 1; 95 vc.push_back(x); 96 } 第33 页共35 页 岱陌存理提高组分拣系统(sort) 97 if (vis[y] == ‐1) { 98 vis[y] = 1; 99 vc.push_back(y); 100 } 101 } 102 swap(cur[a], cur[a + 1]); 103 } 104 } 105 106 int c = (int)vc.size(); 107 108 iota(cur, cur + n, 0); 109 iota(pos, pos + n, 0); 110 for (int i = 0; i < c; i++) tp[i] = vc[i]; 111 112 int sz = 0; 113 114 for (int i = 0; i < m; i++) { 115 for (auto e : sw[i]) { 116 int tm = e.first; 117 int a = e.second; 118 119 if (tm >= st) { 120 mp[sz].clr(); 121 for (int j = 0; j < c; j++) { 122 mp[sz].ins(tp[j], pos[vc[j]]); 123 } 124 at[sz] = tm; 125 bt[sz] = a; 126 sz++; 127 } 128 129 int x = cur[a]; 130 int y = cur[a + 1]; 131 132 swap(cur[a], cur[a + 1]); 133 swap(pos[x], pos[y]); 第34 页共35 页 岱陌存理提高组分拣系统(sort) 134 135 if (tm >= st) { 136 for (int j = 0; j < c; j++) tp[j] = pos[vc[j]]; 137 } 138 } 139 } 140 141 mp[sz].clr(); 142 for (int i = 0; i < c; i++) { 143 mp[sz].ins(tp[i], pos[vc[i]]); 144 } 145 146 for (auto t : qu) { 147 int tm = t.first; 148 int x = t.second; 149 150 for (int i = 0; i < sz; i++) { 151 x = mp[i].get(x); 152 if (at[i] < tm) { 153 if (x == bt[i]) x++; 154 else if (x == bt[i] + 1) x‐‐; 155 } 156 } 157 158 x = mp[sz].get(x); 159 cout << x + 1 << '\n'; 160 } 161 } 162 163 return 0; 164 } 复杂度分析 最终正解设块长为B，时间复杂度为O ( q(n + m + q) B + qB ) ，取B ≈ 320 时可以 通过本题。 空间复杂度为O(n + m + q)。 第35 页共35 页