A. 小猫转转转

题意分析

题目大意是两只猫咪位于森林内，森林是个二维有界网格图，现在需要让两只猫咪位于同一位置，求最小代价。

猫咪的行走方式是根据当前的 顺/逆 状态来决定的，以 逆 为例，在目的地不为树时，猫咪可以直走到达前方，以及 左转后 直走到达左方。

这意味着：

1. 在目的地不为墙时，猫咪可以到达前方、左方、右方，不可以到达后方。
2. 猫咪一定是转向后再直走，所以当前朝向是根据 上一个位置到当前位置 来确定的。由于本题不需要输出方案，不用回溯，我们也可以存一个 dr 变量表示方向，就不用记录上一个位置了。
3. 切换状态是任意时刻都可行的，因此我们只需要在 逆时针状态且右转，顺时针状态且左转 的时候 +1 消耗即可。这意味着 状态消耗 其实可以对应为 某只猫咪行走的消耗 。

我们不妨设某只猫咪的属性为，即位于，当前朝向为，且是否为逆时针（取代表逆时针，反之顺时针）。

此时从的代价，只能为或者，根据 是否切换状态 来确定。

因此本题变成一个 01bfs 问题，由于猫咪可以在原地等待，我们可以对两只猫咪分别跑一次 01bfs，求出到达某个位置的代价，答案就是

一些细节

如何处理方向

我们一共有四个方向，写 if 嵌套的话效率实在太低了。

事实上观察上图我们发现，只需要按照顺时针排列四个方向，分别赋值。

我们就可以通过的方式来实现转向了，当超过边界时矫正下就好。

因此只需定义一个常量字符串 const string sw = "URDL"，把输入的字符转换为其下标存储，后续的转向就很方便了。

01bfs 实现细节

01bfs 往往通过双端队列 deque 实现，新生在 01bfs 上往往容易犯一个经典的错误：

如图所示，当可以通过两种边权到达时，我们其实希望走这条边。

普通的 bfs，我们用的是数组表示是否入队，即。

对于 01bfs，如果只用一个数组可能出现：先遍历到了这条边，将入队且标记为，后续走到这条边的时候跳过了。

解决办法：

1. 最简单的就是开两个数组，来区分
2. 对于部分题目，节点的状态分布是非离散的，我们可以直接用 step[][].. 在全局上存储步数。此时也可以通过更新 step 的方式来避开上述问题。

本题比较特殊，由于状态的切换和的增大是同时进行的。

因此对于，不会有某个同时出现在队列的两头，只用一个数组也可以。

当然为了避免 std 误导选手，在这里还是强调下。

B. 把好多好多点都消掉！

简要题意

平面上有个点，问你能否使用不超过条线消掉所有的点。

题解

发现题目四条线的约束，我们猜测可以通过一些有效的枚举/随机/搜索等方法考虑所有情况，这里给出一个复杂度合适的搜索做法。我们不妨假设最终存在一种方案，也就是可以用四条线覆盖所有点，那么根据抽屉原理，前个不同的点中两两点形成的直线至少会有一条是可行方案中的一条直线，否则这个点均在不同直线上，不满足条件，因为我们考虑去枚举所有直线，并在此时删掉所有在该直线上的点，然后递归子问题即可。

时间复杂度

复杂度上界是，大约为。

验题人有给出比更快的做法，此处暂且不提。

###: 拿到该题目的几乎所有验题人，都会优先考虑求出凸包然后在凸包上乱搞的做法，实际上本题和凸包没有任何关系。

C. 走地鸡数数

简要题意

统计一个数字在数组里所有数中的出现次数。

题解

签到题，按照题意实现数字计数即可，可以直接将数组以字符串形式读入并统计数字字符出现次数，也可以除法模拟取出每个数位统计。

时间复杂度

D. 何意味

题意

给定一个字符串，统计其中出现了多少个 "hyw" 子串。

题解

直接暴力枚举所有长为的子串，判断是否为 "hyw" 即可。

时间复杂度

E. 终会再相见（二）

简要题意

一个数轴上有个点，每个点的可达范围是到该点距离的所有点，你需要选一个数轴上的任意点，使得个点中可以到达该点的数量最多，你需要求出这个数量。

题解

注意到每个点可达区间都是一个长度为的连续区间，我们可以考虑做次区间的操作，

然后遍历所有点即可知道最大值，但是由于和坐标范围极大，我们实际上并不好做这个事情，接下来我们可以有两种选择。

毛毛虫背火箭，我们可以考虑一个动态开点的线段树，然后进行区间加和区间求操作即可。

：我们发现我们并不需要所有值域范围内的点，我们只需要考虑会使答案发生变化的分界点，所以我们可以考虑类似于扫描线的算法，把一个区间拆成和，然后对所有贡献点按坐标升序排序，然后在遍历过程中模拟和操作，取过程中的最大值即为答案。

时间复杂度

F. 魔法石 - 加强版

题意分析

题目大意就是在水平桌面上放个圆，尽可能使所有圆靠得最紧（即投影到轴的线段长度最短）。

两个圆的情况

不妨先讨论两个圆的情况，此时两圆必然相切。

我们研究下这个三角形，不难发现满足勾股定理

解出来有

多个圆的情况

多个圆的时候，我们不能直接比较和，这一点在样例中也有所体现。

当我们一个个往里面插入圆的时候，假设插到第个圆，则有

翻译一下就是，这是一个 dp转移式

本题只需算出所有，然后计算，答案即为

思考解法

时间复杂度

这个是最简单的，我们只需对每个，枚举可能的转移点，然后计算即可

常数较大的时间复杂度

观察上述 dp转移式，我们尝试 dp优化

首先 决策单调性 是否可行呢？手玩一下明显不行，转移点不单调

斜率优化 呢？有

由于不单调，凸壳需要用平衡树维护；由于不单调，需要在凸壳上二分

凸壳维护和凸壳二分都是，总时间复杂度，码量实现比较麻烦，且常数较大

常数较小的时间复杂度

事实上注意到可视为

定义第个圆的特征直线为，用李超树求最值即可

同样是，常数和码量小一些

注意到特征直线的截距的增长很快，实际上的直线交点数量很少

并且李超树的横坐标值域其实是，取足够了

实测耗时约为 std 时间的六倍

时间复杂度

不妨回归到问题本身，再研究研究

以数据为例

讨论的这个圆，朴素情况下我们需要比较的圆

观察式子，对于而言，如果且

显然不可能作为转移点，所以我们只需要维护一个半径递减的单调栈，在栈上找转移点即可

即图中绿色的圆对应的才需要考虑

更进一步思考，还能发现，对于的情况，我们不会取某个 作为转移点

以上图为例，假设三个圆从左往右分别是，显然在满足的情况下，和才可能相切

当时，和无限接近于同一个值

因此我们只需要单调栈从右往左扫，直到碰到第一个的圆位置

容易发现这个过程其实就是单调栈维护的过程，所以只需要在维护的同时顺便计算即可

由于单调栈的维护是的，总时间复杂度

实测 std 仅需即可跑完，开了快读只需要

因此本题时限设置为

（ 事实上实现比较好的李超树配合快读也能勉强卡过 ）

G. 括号编辑器

题解

可以发现想直接维护修改操作是比较困难的，所以我们不妨从询问操作考虑。对于一个位置的括号，如果它最后是高亮的状态，那么一定是它与跟它匹配的另一个括号 (记为) 被翻转了奇数次，记它们之中的左括号位置为，右括号位置为，那么这个括号高亮的条件就变成了在这次询问之前，有偶数次修改操作满足：。

假如没有时间的影响，那么这个问题用扫描线就非常的好做，我们可以把和看成数组的下标，就有，，然后就可以对于下标从小到大枚举，然后用树状数组维护每个权值的出现次数，那么每个下标的答案就是到之间所有权值的出现次数之和。但是由于时间的存在，导致我们这么做的时候，枚举到一个下标，可能有些值这个时候还没被加进来，导致答案不对。

如果想消除时间的影响，就必须保证在我们枚举的时候所有的值都已经被加入了，既然这样，我们可以考虑一个时间断点，然后只考虑之前的修改操作和之后的询问操作，这样就不会出现值还没被加入的情况了，就可以像我们上面说的那样去做。而对于之前的询问操作，是不受之后的修改操作的影响的；类似的，之后的部分询问操作，还会受到之后的修改操作的影响，这样我们就把剩下的两个区间化成跟原问题相同的子问题了，于是我们就可以递归地处理下去。

（本题实际上存在五种以上解法，可参考标程压缩包的代码）

时间复杂度

H. 那只鸡能活下来吗

简要题意

签到题

题解

我们按排序即可，注意排序过程中应该避免浮点数的运算，且需要考虑相等的特殊情况。

时间复杂度

I. 区间之和

简要题意

给定一个正整数构成的数组，问有多少个子段和小于某个值。

题解

经典的双指针问题，我们可以建立两个指针和，表示被选中的子段，初始时都指向数组开头。

考虑从左到右枚举的位置，然后对于每个，不断重复的进行尝试将向右侧移动，直到当前段的和将要超过限制。此时的区间长度就是这个左端点对答案产生的贡献。

可以保证和都只会遍历每个位置一次。

时间复杂度

J. 逃离鸭科夫

题解

首先考虑二分答案，二分最短助跑距离的取值。接下来考虑如何去使用一个最短助跑距离能否成功到达出口。我们发现这是一个类似最长路的问题，因为在到达某个点时我们当然希望此时的已有助跑距离能更长。

方法一 拓扑排序

由于鸭科夫是一个有向无环图，可以对其进行拓扑排序。我们定义为到达点时能获得的最长助跑长度，随后发现，对于一个点，可能使其值变得更大的只可能是它的前驱，也就是拓扑排序中在它之前的点，于是直接按照拓扑排序进行更新即可。

需要注意的是，在进行拓扑排序之前要先从起点进行一轮搜索，以排除所有无效的点，否则可能会被这样的点锁死导致答案更新不完全。

另一处需要注意的是，对于那些有鸭兵的节点，我们也需要对它们进行拓扑排序的更新，但在节点信息更新时要打上特殊标记。

方法二 反向建边DFS

考虑方法一的实质其实是在一个点被处理时，我们必须已经确定了所有其他可能引起该点值变优的节点的信息，这样才能保证该点不会被多次更新或更新不完全。

于是可以考虑将所有边反着建，然后直接从终点开始，先搜到底为止，然后在回溯的时候我们就可以保证，如果轮到了一个点被处理结算，那么意味着它的子节点，也就是原图中它的前驱节点，已经全部被结算完毕了，这就更简洁的实现了拓扑排序一样的效果。

时间复杂度

K. 积木坐飞机

_

题解

有两种构造方法，但是都需要正着卡一遍范围，倒着取一遍可行值，令前缀和数组为，：

1. 由的范围和的范围，卡出的范围，保证了对的范围中的每一个数都存在至少一个合法的，能够使在的范围内；最后从范围中随意取一个值，不断往前找出一个合法的使得落在卡出的区间即可 。
2. 由的范围和的范围，卡出的范围，保证了从的范围中的每一个数都存在至少一个合法的，能够使在的范围内；最后从开始，不断往后找出一个合法的使得落在卡出的区间即可。

时间复杂度

L. 城市旅行

题解

本题要求解两点间的最少移动次数。由于每个城市可以到达一个完整的区间，若将问题建模为图，其边数可能达到级别，导致朴素的广度优先搜索（BFS）无法在规定时间内求解。因此，我们需要寻找一种更高效的算法结构。

问题的核心在于，一次移动后，我们的状态不再是一个点，而是一个可达区间的集合。如果我们能维护这个集合，并快速计算多次移动后的结果，问题就能解决。

我们定义一个“状态”为当前所有可达城市构成的连续区间。初始时，我们只在起点，状态为。考虑这个状态如何转移：从内的任意一个城市出发，都可以到达。那么，从整个区间出发走一步，能到达的新区间就是所有这些的并集，这个并集仍然是一个连续区间，其范围是。

同时我们可以证明，只要终点尚未被到达且可达，那么每移动一步，可达的城市集合必然会严格增大。因为如果集合不再扩张，我们就会被困在当前集合内，永远无法到达集合外的终点，这与终点可达的前提矛盾。由于总城市数只有，这个扩张过程最多持续步。

这个“区间单步转移”操作的计算本身就需要一个区间最值查询（RMQ）。如果我们一步步模拟转移，效率依然很低。为了加速这个过程，我们采用倍增的思想。

我们预处理和，分别表示从单个城市（即初始区间）出发，经过次移动后，能到达的区间的左、右端点。

预处理阶段

1. 基础情况 (): 移动步。根据题目定义，从城市出发移动一步即到达区间。因此，我们初始化和。

2. 递推计算 (): 移动步可以分解为先移动步，再从得到的新区间出发，继续移动步。

   • 首先，从城市出发移动步，根据定义，我们到达了区间。
   • 然后，我们需要计算从这个整个区间出发，再统一进行步移动的结果。这相当于要计算作为新的左端点，以及作为新的右端点。
   • 这个计算是一个典型的区间最值查询（RMQ）问题。因此，为了高效计算第层的数据，我们必须先为第层的和数组分别构建ST表。这样，每次查询都可以在时间内完成。整个预处理的时间复杂度为。

查询阶段 对于每个查询，我们的目标是从初始区间开始，用最少的步数使其扩展到能覆盖。

1. 初始化答案 ans = 0，当前可达区间为。

2. 我们从大到小（从到）尝试进行步的“大跳跃”。

   • 首先，计算从当前区间出发，再跳步后的潜在新区间。这通过查询第层的ST表来完成：，。
   • 进行决策：我们检查终点是否在这个新区间内。
     • 如果没有被覆盖（即或），这说明这次大跳跃是安全的，它让我们大幅前进但仍未到达终点。因此，我们必须执行这次跳跃：更新，并将步数累加 ans += (1 << k)。
     • 如果被覆盖了，我们则不执行这次跳跃。这是因为我们的目标是最小步数，这次跳跃可能是“过量”的。我们保留当前状态，继续尝试更小的步长，以期找到一个更精确、总步数更少的路径。

3. 得出答案与处理无解情况：

   • 当上述循环结束后，ans 记录的是在不覆盖的前提下，我们能走的最大步数。此时，我们所处的区间距离覆盖只差一步。因此，最终答案是 ans + 1。
   • 无解判断：如何确定终点根本不可达？在查询的循环中，如果对于所有的，计算出的新区间都不能覆盖，这意味着无论我们怎么跳，都无法使可达区间“越过”或“到达”。我们可以使用一个标记 。在循环中，一旦发现存在区间能够覆盖，就将此标记设为 true。如果在整个查询结束后，该标记仍为 false，则说明是从不可达的，应输出 -1。

时间复杂度

每个查询的时间复杂度是，算法总复杂度为。

M. 文件资源管理器

题意

一次操作可以选择和不超过的连续区间删除，删除后剩余区间按原顺序合并，保证，问删光整个数组的最小次数。

题解

考虑区间 dp。-表示对于区间的最小删除次数。-表示对于区间，达到最小删除次数时，最后一次删除操作的文件体积的最小值。初始化：-，-，每个文件单独进行一次删除操作转移：从小到大枚举区间长度，枚举区间左端点，再枚举区间切分点。对于每个区间的结果，先处理出所有待选更新参数对：- 先不考虑最后一次删除，只考虑直接合并，那么待选更新参数对为：- 考虑最后一次删除，如果满足，那么说明左右两个区间剩余部分可以一次性取光，而不需要两次分开取，此时的待选更新参数为：在所有的待选参数对中，优先选择值最小的进行更新，如果有多个最小值并列，选取最小的进行更新。

时间复杂度

N. 走地鸡摆床

题意

给定一张大小的网格，保证是偶数，问用色，带前后方向的床铺满整个网格的方案数。

题解

设在不考虑床的颜色与朝向的情况下，方案数为，那么考虑了床的颜色与朝向后，方案数为。现在考虑如何计算，注意到特别小，考虑对进行状压dp，设表示考虑了前列，第列的覆盖情况为的方案数。

初始化： -，其中表示全集。表示第列全满的方案数为。

转移：

（和交集为空，其中表示若干竖着放的床的状态，可以用位运算暴力预处理出所有合法的）

但由于特别大，达到了级别，不能直接暴力转移，我们可以考虑使用矩阵快速幂加速这一转移过程：

在上式可以理解为，向贡献倍的构建状态转移矩阵时，只需要将置，其他位置的值置。最后跑一遍矩阵快速幂，右乘上初始状态列向量，取出结果列向量的第项即为我们要求的。由鸽巢定理，最后答案即为。

时间复杂度