A.我爱机电

每次读入字符串，判断是否是 zume 或 zime，不是就直接输出，是就前面加个 520 。

所以对于判断 $n$ 个字符串的时间复杂度是 $O(n)$。

B.寻径指津

从题目可以看出来，这是一个经典的搜索问题，但是因为 $n\times m$ 过大，以及出现的特殊点最多才 $1000$ 个点，所以我们直接去暴力枚举每个特殊点去搜索当前点可以到达的下一个位置，这样就可以避免搜索无意义的位置了。

同时因为步数不能超过 $6$，那么枚举所有可能的时间复杂度会很低，因此我们可以在搜索时通过数组记住当前状态每个点是墙还是机关，然后去枚举每个当前为墙的点，确定当前点上下左右可以到达的位置就行了。

还有就是题目要求字典序最小，所以我们可以通过 $BFS$ 以及 $D→L→R→U$ 的顺序搜索即可。

时间复杂度为 $O(4096\cdot k)$。

C.胡闹搬家

首先，看到题目要求的是所有搬运者花费的力气最少值是多少，我们可以想到用二分去找这个值。

对于每一个二分中的搬运者花费力气 $M$，我们就可以通过题目的信息得到一个边权单向图：

• 从起点 $S$ 出发到达每个搬运者都有一个值为 $M$ 的单向边。
• 每个家具有两个边是从两名指定的搬运者指向它的，值为 $x_i$。
• 所有家具都有指向向终点 $T$ 的值为 $x_i$ 单向边。

根据这个图我们可以通过去求它的最大流去得到最后的总力气，然后去判断总力气是否达到家具总重量就行了。

时间复杂度为 $O(\log(S)\cdot (m+n+2)^2\cdot(m+3n))$。

D.塔尖乐园

题目给定一个单向图，每次查询 $x$ 有两个子问题：

1. 可以通过传送门到达塔 $x$ 的编号最小的塔是哪个塔。
2. 从塔 $x$ 出发能够到达编号最大的塔是哪个塔。

第一个子问题我们可以贪心的从编号最小的塔开始 $DFS$ 暴搜，这样可以保证搜到的塔编号不小于初始搜的点，也就是搜到的塔的第一个问题就是搜索的初始塔，可以用一个数组记录下来，顺便标记防止重复。

第二个子问题同理，只不过要把边反一下（$u\to v$ 变成 $v\to u$），然后贪心的从编号最大的开始搜就行了。

这两个预处理时间复杂度都是 $O(n)$，最后的查询就可以 $O(1)$ 了。 (也可以通过SCC解决)

E.机电迎新

根据题目内容，我们可以得到一个 $BFS$ 暴搜的代码，每次放入一个点，然后依次把它能到的所有点都丢到队列里，再加上标记数组。这样的时间复杂度是 $O(n^2)$。

我们发现搜过的点会出现被询问好几次的情况，而且每次的跳跃都是一个区间。

于是我们可以加一个跳跃指针 $\operatorname{Next}[i]$ 来优化广搜，用来记录从位置 $i$ 开始下一个未被当前区间覆盖的位置。

比如当处理节点 $now$ 的范围 $[L[now], R[now]]$ 时：

• 对于每个位置 $i$，处理完后将 $\operatorname{Next}[i]$ 设为 $R[now]+1$

• 这样后续处理可以直接跳过已覆盖区间

于是我们的时间复杂度就可以优化为 $O(n)$。 (也可以通过线段树解决)

F.子异或和

首先，$S$ 是所有满足按位或 $x$ 后还是 $x$ 的数。

因为是或运算，所以可以得到下面两个情况：

• 对于 $x$ 二进制位上为 $0$ 的数来说，我们 $y$ 对应的二进制位上只可能是 $1$

• 对于 $x$ 二进制位上为 $0$ 的数来说，我们 $y$ 对应的二进制位可以是 $0$ 或 $1$

我们设 $x$ 二进制位上 $1$ 的个数为 $b_1$

那么，对于每个二进制位上的 $1$，出现的次数为：$2^{b_1-1}$

然后因为是异或，次数为偶数的 $1$ 异或一定为 $0$。

那么最终答案可以确定：

$$ans=\left\{\begin{matrix}n&b_1\le1\\0&b_1>1\end{matrix}\right.$$

总时间复杂度为 $O(\log(n))$。

G.数字计次

由于 $n$ 和 $q$ 都是 $2\times10^5$，并且 $a_i$ 的数据量我们不能用数组直接统计次数。

所以我们可以用 map 去统计每个数出现的次数，然后 $O(\log(n))$ 查询次数就行了。

H.阿兔种树

根据题目我们知道一共有两个修改操作和一个查询操作：

1. 在高度大于 $x$ 的位置上种 $k$ 棵树。
2. 在高度小于 $x$ 的位置上种 $k$ 棵树。
3. 输出位置 $p$ 上有几棵树。

因为给的高度是乱序的，所以我们可以把位置通过高度先排序，再排序高度。之后就会变成(区间修改+单点查询)线段树板子。

时间复杂度是 $O(n\log(n))$。

I.右移弑夫

初始时，网格中有最多 $N$ 个蟑螂（即 $1$ 的个数不超过 $2\times10^5$）。

• 设每次添加操作遍历的格子数为 $k$（即从 $t$ 开始连续 $1$ 的个数）。那么，这次操作会清除 $k$ 个 $1$，并最多设置一个 $1$（如果没有超过最大值）。

• 初始 $1$ 的个数为 $C_0≤N$，每次添加操作可能设置一个 $1$（最多 $Q$ 次），因此设置 $1$ 的总次数不超过 $C_0+Q$。

• 整个操作过程中，网格中 1 的数量变化满足：初始 $1$ 的数量 + 设置的 $1$ 的数量 - 清除的 $1$ 的数量 = 最终 $1$ 的数量。即：

$$C_0+\sum_{i=1}^QI_i-\sum_{i=1}^Qk_i=C_f\ge0$$

其中 $I_i=1$ 表示第 $i$ 次添加操作设置了一个 $1$，否则 $I_i=0$。因此：

$$\sum_{i=1}^Qk_i=C_0+\sum_{i=1}^QI_i-C_f\le C_0+Q\le N+Q$$

所以，所有添加操作遍历的格子总数 $\sum_{i=1}^Qk_i\le N+Q$。每个添加操作的其他工作（如检查和设置）为常数时间，因此总时间复杂度为 $O(N+Q)$。

所以我们可以直接暴力做，但同样其他方法也可以做。 (也可以通过分块或线段树解决)

J.公约数距

根据题目可以得到原式为：

$$\sum^n_{i=1}\sum^{i-1}_{j=1}2^{i-j-1}\cdot\gcd(A_i,A_j)$$

由于欧拉函数知道 $n=\sum_{d\mid n}\varphi(d)$ 可以得到：

$$\gcd(A_i,A_j)=\sum_{d\mid\gcd(A_i,A_j)}\varphi(d)$$

原式就可以优化为：

$$\sum^n_{i=1}\sum_{d\mid A_i}\varphi(d)\cdot2^{i-1}\cdot\sum_{j=1}^{i-1}2^{-j}[d\mid A_j]$$

此时，这个公式已经优化完成了，剩下就是代码上的优化了。

首先设 $F(i)=\sum_{j=1}^{i-1}2^{-j}[d\mid A_j]$ ，$F(i)$ 在数组的最后面，明显是和前面的 $\sum_{i=1}^n2^{i-1}[d\mid A_i]$ 类似的样子。在形式上，前面的 $i$ 每次加 $1$ ，后面的 $F(i)$ 都会在原来的基础上增加一部分，公式可以表达为：

$$F(i+1)=F(i)+2^i\cdot[d\mid A_j]$$

那么我们就可以预处理 $F(i)$ 。

然后主要代码的时间复杂度就可以变成 $O(n\cdot\sqrt{A_{max}})$ 也就是下面的样子：

$$\sum^n_{i=1}\sum_{d\mid A_i}\varphi(d)\cdot2^{i-1}\cdot F(x)$$

为了防止 $TLE$ 我们发现 $n$ 的范围在 $10^5$ 内，那么可以通过预处理 $\gcd$ 来降低复杂度。

处理完主要代码的时间复杂度为 $O(n\cdot\log{A_{max}})$ ，这样就可以轻松通过了。

K.机电标语

由于题目说明要求出包含至少一个子串 ZUME 同时不包含子串 ZIME。我们可以使用补集思想把包含一个不包含另一个变成，不包含后者减去两个都不包含的情况。

我们可以得到以下6个状态：·

1. 空状态（未匹配任何有效前缀）
2. 已匹配 'Z'
3. 已匹配 "ZI"
4. 已匹配 "ZIM"（对于矩阵 $A$，允许后续接 'E'；对于矩阵 $B$，不允许）
5. 已匹配 "ZU"
6. 已匹配 "ZUM"

然后我们就可以构造出两个状态转移矩阵：

• 不包含 ZIME：

$$A=\begin{vmatrix}25&1&0&0&0&0\\23&1&1&0&1&0\\24&1&0&1&0&0\\25&1&0&0&0&0\\24&1&0&0&0&1\\24&1&0&0&0&0\end{vmatrix}$$

• 既不包含 ZIME 也不包含 ZUME：

$$B=\begin{vmatrix}25&1&0&0&0&0\\23&1&1&0&1&0\\24&1&0&1&0&0\\24&1&0&0&0&0\\24&1&0&0&0&1\\24&1&0&0&0&0\end{vmatrix}$$

然后就可以通过矩阵快速幂直接求解，时间复杂度为 $O(T\cdot 36\log(n))$。 (也可以通过AC自动机解决)

L.平衡书架

由于 $x$ 的范围很大，但操作次数最多 $2\times10^5$，我们可以将所有出现的 $x$ 映射到 $[1,n]$ 的范围。

然后用树状数组维护每个离散化后的值出现的次数，实现：

• 区间求和：计算小于某个值的书有多少本
• 单点更新：插入或删除书
• 二分查找：找到第 k 小的值

对于每一个编号相同的，我们可以维护一个有序集合去存储该值所有出现的位置。这里在插入新的值后，该值后面的书位置都需要 $+1$。

时间复杂度 $O(n\log(n))$。 (也可以通过平衡树或分块解决)

M.携药下凡

根据题目我们可以先判断碗是否包括原点 $(0,0)$，如果是直接返回 $0$。

再用点积判断指向方向和碗的方向是不是同向，如果方向相反，返回 $-1$。

然后就可以通过碗与面朝方向射线的距离和 $r$ 判断面朝方向射线是否经过碗。

最后剩下的必定是经过碗的，所以我们可以通过勾股定理计算从原点到碗的切线点的距离，方法如下：

设原点到碗心的距离为 $L$，碗心到射线的垂直距离为 $d$ ，那么原点到切点的距离为：

$$\sqrt{L^2-d^2}-\sqrt{r^2-d^2}$$

这样就可以 $O(1)$ 求出答案。