ACGO 巅峰赛#19 题解
本场巅峰赛的所有题目的难度评级为：
题目编号 题目标题 难度 T1 变色龙 入门 T2 打印机 入门 T3 机器人 普及- T4 公告 普及+/提高- T5 登塔 普及+/提高- T6 24点 普及+/提高
题目解析
A - 变色龙
模拟
题目描述，给定两个 n×nn \times nn×n 的矩阵，求两个矩阵中的有多少个相同位置的大小为 m×mm \times mm×m 的二维矩阵是不同的,由于n,m比较小，因此可以直接枚举左上角的点，然后枚举两个矩阵相应位置的 m×mm \times mm×m 矩阵的点，如果有不同就加入统计。
时间复杂度 O(n2m2n^2m^2n2m2)
代码
B - 打印机
模拟
在处理试卷打印时，仅需考虑单面打印和双面打印这两种情形。对于双面打印，需要留意的是，若某页纸的正面或反面任意一面需要彩色打印，那么这一整张纸都要采用彩色打印。我们可以运用集合（set）来对最终结果加以统计。
时间复杂度 O(mlog(m)+nm\log(m) +nmlog(m)+n)
代码
C- 机器人
二分
首先，机器人仅能沿横坐标与纵坐标方向移动。基于这一特性，我们可以分别按横坐标和纵坐标，对柱子的信息进行存储。考虑到坐标数值可能较大，使用map进行存储较为合适。
对于横、纵坐标上每个可能出现的点，我们将其存入对应的数组。完成数据存储后，每次机器人移动时，通过二分查找的方法，就能判断机器人当前位置与目标位置之间是否存在柱子。
时间复杂度 (O((n+q)log(n)(n + q )\log(n)(n+q)log(n))
D-公告
并查集
在解决当前问题时，正向处理存在较大难度，往往需要多次断边，才能成功去除某一连通块。既然直接删边操作复杂，不妨尝试采用离线算法来简化计算。
我们可以逆向思考，将删边操作转换为加边操作。从最后一次删边开始倒序处理，这样问题就转化为：给定一个图，逐步向图中添加边，并在每次加边后确定班长能够通知到的学生集合。我们可以通过并查集解决这个问题。
时间复杂度 O(n)
E-登塔
动态规划
对于本题，我们先从常规思路入手，考虑从第 iii 层向第 i+1i + 1i+1 层的状态转移。设 f[i][j]f[i][j]f[i][j] 表示处于第 iii 层的第 jjj 个房间时所能取得的最大值。那么状态转移方程为 f[i+1][k]=max(f[i][j])+a[i+1][k]f[i + 1][k] = \max(f[i][j]) + a[i + 1][k]f[i+1][k]=max(f[i][j])+a[i+1][k]，其中 j∈{1,2,⋯ ,n}j \in \{1, 2, \cdots, n\}j∈{1,2,⋯,n} 且 j≠kj \neq kj=k。
从这个转移方程可以看出，f[i+1][j]f[i + 1][j]f[i+1][j] 的转移核心在于找出第 iii 层除第 jjj 个房间之外能取得的最大价值。假设第 iii 层价值最大的房间编号为 jjj，那么在第 i+1i + 1i+1 层中，除了第 jjj 号房间外，其他房间都可以从第 iii 层的 jjj 号房间移动过来，从而获取最大价值。而第 i+1i + 1i+1 层的 jjj 号房间，则可以从第 iii 层价值次大的房间转移到达。
基于此，我们发现只需记录每一层价值最大的两个房间的编号，就能实现向下一层的状态转移。这种方法的时间复杂度为 O(nm)O(nm)O(nm)。
注意 m == 1的状况他会被困在第一层
F-24点
抽屉原理
许多同学尝试通过模拟的方法来解决这道题，然而在模拟实现的过程中，一个明显的问题浮现出来：一旦出现错误，检查和调试都极为困难。那么，我们能否通过深入观察题目的性质，来降低模拟的复杂程度呢？
首先，让我们思考这样一个问题：给定任意两个数，我们是否能够通过一定的运算构造出一个 3 的倍数呢？
假设这两个数为 aaa 和 bbb 。如果其中一个数本身就是 3 的倍数，那么将这两个数相乘即可得到 3 的倍数，这种情况较为简单，我们暂不深入讨论。接下来考虑两个数都不是 3 的倍数的情况，此时它们除以 3 的余数（即模 3 的结果）共有 4 种组合：{1,1}\{1, 1\}{1,1}、{1,2}\{1, 2\}{1,2}、{2,1}\{2, 1\}{2,1}、{2,2}\{2, 2\}{2,2}。经过分析不难发现，对于这四种组合，我们都可以通过加法或者减法运算，使它们得到的结果成为 3 的倍数。由此，我们证明了任意两个数都能够通过适当的运算得到 3 的倍数。
已知 24÷3=824 \div 3 = 824÷3=8，此时问题就转化为：给定 4 个数，我们能否从中选取两个数，通过运算构造出 8 的倍数呢？为了简化问题，我们先排除这 4 个数中本身就包含 8 的倍数的情况。那么，当这 4 个数分别除以 8 取余数（即模 8 ）后，结果只会是 1、2、3、4、5、6、7 这 7 种情况。接下来我们思考，这 7 种余数情况中，哪些组合可以构成 8 的倍数呢？
通过计算可知，1+7=81 + 7 = 81+7=8，3+5=83 + 5 = 83+5=8，2×4=82 \times 4 = 82×4=8，2+6=82 + 6 = 82+6=8，4×6=244 \times 6 = 244×6=24（24 也是 8 的倍数）。基于这些组合，我们可以将这 7 种余数情况划分成 3 个集合：{1,7}\{1, 7\}{1,7}，{3,5}\{3, 5\}{3,5}，{2,4,6}\{2, 4, 6\}{2,4,6}。在这三个集合中，任意选取集合内的两个数，都可以通过相应的运算构成 8 的倍数。
由于我们一共有 4 个数，根据抽屉原理，这 4 个数中必然会有至少两个数的余数属于同一个集合。所以，我们可以先从这 4 个数中选取 2 个数，构造出 8 的倍数，再通过前面证明的方法构造出 3 的倍数，最后将得到的 8 的倍数和 3 的倍数相乘，就可以得到满足条件的结果。
综上所述，该算法的时间复杂度为 O(T)O(T)O(T)。
