HDSpring4

Easy

1010 Sort

题意：

给定一个二维数组，每一行选一个值，问能否凑出一个严格递增的序列。

思路：

贪心即可，每一行找到最小的满足条件的值，即可。

1007 Turn Of A Page

题意：

给定一个序列和一个特殊值，问能否对原序列重排后，使得所有位置的某一部分前缀和等于这个特殊值。

思路：

刚开题的时候想了半天，第一个想法是降序排序，然后用滑动窗口维护。WA了之后，重新分析题目，首先序列第一个元素的前缀只有它本身，那么 $a_{1} = S$，接着考虑第二个值，分析后发现只有两种情况，$a_{2}=S$ 或者 $a_{2}=0$。豁然开朗，如果给定的序列存在 $0$ 和 $S$ 以外的元素，就是不可能的，还有一种特殊情况要特判，$S\neq0$ 但是序列全为 $0$。

1008 谁输谁洗碗

题意：

给定一组数字和匹配数，匹配数为当前数字与答案相同的个数，要求倒推答案。

思路：

先分析暴力的复杂度：$O\left( \sum n \times 10000 \right)$，大概为 $1e9$ 的规模，大概率是假的，但是这个 4s 的时限启发了我，剪枝暴力启动！

我的思路是首先按匹配数降序排序，然后优先和匹配数高的数字 check，枚举 0 ~ 9999 中的所有数，如果和前面匹配数高的都不能匹配，这个数一定不能和后面匹配数低的数匹配，直接 break 。同时由于保证有且仅有一个四位数满足猜测序列，所以找到答案就可以直接跑路 return。

从而水过去了，这就不得不感慨一句昨天的天梯赛模拟赛，那个矩阵 $n=4$ 的情况我写了 9 个 for 循环嵌套剪枝水过去了。

---

Medium

1001 布布吃地瓜

题意：

给定一个网格，网格中有数字，从左上角走到右下角，每一条路径的贡献值为当前路径中不存在的最小非负整数。找出最小的贡献值作为答案。

思路：

如果一条路径上没有 0，那么这条路线的贡献值就是 0，即为最小。因此，可以直接从 0 枚举到 $n*m$，超过 $n*m$ 的值不用统计，证明略。

连通性对偶结论：在四连通的网格中，从 $(1, 1)$ 到 $(n, m)$ 的路径被阻断，当且仅当阻断点（数值为 $k$ 的点）通过八连通的方式，形成了一条连接 “左/下边界” 和 "右/上边界" 的屏障。

因此我们可以定义两个边界集合：$A$ 表示右/上，$B$ 表示左/下。如果有一组数值为 $k$ 的连通块同时触碰到了 $A$ 和 $B$，那么所有从起点到终点的路径都必然会经过 $k$，此时 $MEX\{S\} \neq k$。

考虑到这是一个连通性问题，我们可以采用并查集这个数据结构实现。接着取出所有数值为 $k$ 的点，然后合并merge，再判断是否阻断路线即可。（ 注意特判起点和终点的数值 ）

复杂度分析，理论上每个点只访问了一次，因此为 $O(mn \cdot \alpha(mn))$， 后面那一项是并查集复杂度，通常为 $O(1)$。

补充一道我以前写过的类似题目，可以练练手：P3958 奶酪

1004 左右脑互搏

题意：

给定 n 个数，每回合可以删除一个数，A 和 B 轮流操作，操作不了的人输了。
限制条件：删除的这个数 必须大于 删除这个数后集合的异或和。

思路：

首先定性，这是一道博弈论的题目，而且是一个典型的公平组合游戏（这个词不重要），引入一个博弈论的概念，必胜状态 (P) 和必败状态 (N)。

• 必胜态：从当前的状态出发，所有能到达的后续状态都是必胜态。
• 必败态：从当前的状态出发，存在一条路径到达下一个必败态。

注：这里的必胜必败只与当前状态相关，而与玩家无关！

由于这个限制条件比较麻烦，所以不能用 Nim 游戏的 SG函数 来计算，接着注意到 $n \leq 20$，这启发我使用 $O(2^n)$ 复杂度，仔细想想，有两个算法待选：状态压缩，DFS。再动一动脑，就选择记忆化搜索了。

定义 $Memo[mask]$ 为当前状态的胜负情况：-1 尚未计算，0 必败态（Right赢），1 必胜态（Left赢）。

这个 Memo 是 memory 的缩写，一般用于记忆化搜索（DP的另一种实现方式），mask 位掩码 ( 二进制数 ) ，第 $i$ 位是 1 表示第 $i$ 位集合中，反之不在。

定义完状态，考虑转移：对于当前的 mask，我们需要遍历每一个二进制位 1 的位置 $i$，然后判断删完之后是否存在一条路径到达必败态，如果没有，就说明当前是必胜态。

接着考虑优化异或运算，作为位运算，它具有一些良好的性质，比如 “自反性”：$A \oplus B \oplus A = B$，所以只需要记录当前状态的 xorSum 异或和，然后下一级状态的异或和就可以简单的写为：xorSum ^ a[i]。从而优化了遍历集合的复杂度。

吐槽一下，这题我MLE了好几次，int memo[1 << maxn] 死了，short int memo[1 << maxn] 也死，检查发现是因为 $maxn = 25$，把 $maxn = 21$ 就行了（流汗）。启示我们跟指数相关就不能乱开数组大小了。

1002 通行证-Easy

题意：

给定一个二维数组，每次给定一个值 $card$，计算所有元素的最近的敌人的距离之和。敌人的定义为：$x | card \neq card$（ 其中 $|$ 为按位或 ）。

$T \leq 10, n \leq 300, q \leq 5e4, a < 2^{15}, card < 10^9$

思路：

对坏人定义的取反可以得到：好人的定义为：$x \& card = x$，即 $x$ 是 $card$ 的子集（其中 $\&$ 为按位与）。

发现 $n$ 的规模很小，考虑直接暴力，但是 $q$ 的规模很大，或许需要一些优化，考虑从直接求距离到统计贡献。

这里借用题解的图片，定义 $S[i][j][k]$ 为以 $(i,j)$ 为中心，在四个方向上步长 $\leq k$ 的所有格子的按位或，如果 $S[i][j][k] \& card = S[i][j][k]$，就说明改区域内都是好人。

因此，我们第一步先预处理这个 $S$ 数组，复杂度为 $o(n^3)$ ，当前限制条件下能满足。具体操作步骤如下：初始化 $cur = a[i][j]$，表示 $k = 0$ 时的 OR 和，f[cur]++，然后计算到四个边界的最小距离 $edge = min(i-1,n-i,j-1,n-j)$，接着从 $k=1$ 到 $edge$ 循环，更新 当前 OR 和，以及 $f$ 数组。

跑完后 $f[mask]$ 就记录了有多少对 ( 格子，距离 ) 的覆盖区域 OR和 恰好为 mask。

接着分析，我们需要查询的是所有满足条件 $mask \subseteq card$ 的 $f[mask]$ 之和，由于 $a < 2^{15}$，我们这里可以采用 SOSDP（高维前缀和）在 $O( 15 \cdot 2^{15})$ 时间内预处理出所有答案。

for( int i = 0; i < 15; ++ i )
{
	for( int mask = 0; mask < (1 << 15); ++ mask )
	{
		if( mask & ( 1 << i ) ) 
			f[mask] += f[ mask ^ (1 << i) ]
	}
}

最后应对查询，直接在线回答即可，注意 $a < 2^{15}$ ，所以有效的 $card$ 最大也只需要这么大即可，取有效位 card &= (1 << 15) - 1，然后输出答案 $f[card]$ 即可。

分析复杂度：预处理 $O(n^3)$，SOSDP $O(L \cdot 2^L)$，查询 $O(q)$，过了。

---

Hard

1003 通行证-Hard

题意：

同上不再赘述。

$T \leq 2, n \leq 1500, q \leq 5e4, a < 2^{15}, card < 1e9$

思路：

前述应对思路不变，发现瓶颈在预处理的 $O(n^3)$，考虑对这一步进行优化，观察到 $a$ 只有 15 位，随着距离增加，十字区域内的 OR和 是单调不减的，所以，即便 $k$ 可以从 $0$ 变到 $750$，但 OR和 最多只会发生 15 次跳变。

于是我们就有了优化方向：不再逐个枚举 $k$，而是直接去找到这几个跳变距离，再开一个数组 dist[i][j][bit]，记录使 $S[i][j][k]$ 的第 $bit$ 位变为 1 所需的最小距离。

这一步可以通过四次线性扫描完成：行方向，左扫右扫，求出行内最近的点，然后列方向，左扫右扫，求出列内最近的点，接着合并。

接着再计算区间贡献，开一个 vector 存该格子的 15 个 $dist[i][j][bit]$，并加入边界限制，然后排个序去重，可以得到一组跳变点 $0 = k_{0} < k_{1} < k_{2} < k_{3} < \cdots < k_{m}$。

在距离区间 $[k_{i}, k_{i+1}-1]$ 内，所有的 $k$ 对应的 OR和 mask 是相同的，该 mask 可以通过所有 $dist[i][j][bit] \leq k$ 的位 $bit$ 组成。更新答案 fa[maxk] += k[r+1] - k[r]。

最后就是 SOSDP 处理子集贡献，然后 $O(1)$ 回答。

总复杂度为 $O(n^2 \log V)$。

注：本题卡常... 所以需要优化很多常数，我尝试了快读 + dist 数组改用 short 才过。具体原因在讨论区里也有提到，我就不赘述了。

1005 列车停放站

题意：

给一堆长方形方块，然后给定一系列查询，问某个区间 $[l,r]$ 能塞下最多几个方块。

思路：

本题的本质是 “区间不相交覆盖问题”，根据结论，为了在有限的区间 $[x,y]$ 内放置更多的方块，我们应该贪心选择 结束时间最早 且 起始时间不早于当前 的方块。

但是一次贪心的复杂度是 $O(N)$，无法应对这种大规模的查询，我们需要考虑优化方案。在贪心中，我们需要的是找到从每个位置 $i$ 出发，只选一个方块最早的结束时间，因此我们可以尝试预处理来优化复杂度，定义 nxt[i] 表示左端点 $\geq i$ 的所有长方块中，最小的右端点。

这一步预处理可以通过 nxt[i] = min( nxt[i], nxt[i+1] )，同时倒序扫描，从而保证 nxt[i] 存储的是位置 $i$ 及右侧所有可选的方块的最小的右端点。

当然，这里的值域很大，所以需要提前离散化一下。

但是这样的复杂度从本质上还是没有降下来，进一步思考，由于贪心的决策是固定的，每次 都跳到最早结束点，既然是相同的，我们可以试试倍增 的思想。

定义 $dp[i][j]$：从位置 $i$ 出发，选择 $2^j$ 个方块能到达的最小右端点。

接着考虑状态转移，这里就直接采用 ST 表的转移即可。

$$dp[i][j] = dp[\, dp[i][j-1] \,][j-1]$$

注：跳 $2^j$ 步等同于先跳 $2^{j-1}$ 步，再从那个位置跳 $2^{j-1}$ 步。

最后我们来考虑如何处理查询，当然这里不难，对于每个查询区间 $[l, r]$，我们需要在离散化后的数组中找到 $l$ 对应的左端点 ll 和 $r$ 对应的右端点 rr。然后从 $2^{19}$ 开始尝试往下跳，如果从当前位置跳 $2^j$ 步后的结束位置仍然 $\leq rr$，那么就可以接着跳，然后累计答案 ans += ( 1 << j )。

最后来评估一下复杂度：

• 离散化与预处理：$O((N+M) \log(N+M))$。
• 倍增表预处理：$O(V \log V)$，其中 $V$ 为离散化后的点数。
• 单次查询：$O(\log N)$。
• 总复杂度：$O((N+M) \log(N+M))$，非常稳健。

留一个思考题：如果题目要求列车之间必须留出至少 $k$ 的空隙，应该怎么处理呢？

1009 GCD

题意：

给定两个长度为 $n$ 的数组 $a$ 和 $b$，你可以进行如下操作。在当前数组中选择一个下标 $i$，计算 $g_{i} = gcd( a_{i}, a_{i+1}, \dots, a_{m} )$，将 $b$ 数组中下标从 $i$ 到 $m$ 的所有元素都减去 $g_{i}$。

多次询问，每次给出区间 $[l, r]$，你需要考虑至少操作几次将 $b$ 数组都变为非正数。

思路：

注意到 $g_{i}$ 是一个后缀函数，随着 $i$ 的增大，参与 gcd 计算的元素会变少，根据定义，发现最后的 gcd 只会单调不减。

接着分析问题，要求操作次数最少，我们肯定会选择更大的 gcd 去减。因此我们可以从左往右贪心（因为每次操作都会影响 $j > i$ 的所有 $b_{j}$，所以只要满足左边的，右边的自动会被带上），而对于 $b_{i}$ 来说，所有能影响到它的操作位置 $k$ 都必须满足 $k \leq i$，而在这所有 $k$ 中，$g_{i}$ 是最大的，参考前一段的单调不减。

然后我们就得到了这题的朴素解法，复杂度是 $O(Q \cdot N)$，因为是一个一个点处理，所以会假。考虑优化，切入点是区间，这里从后缀 gcd 的性质入手。

随着 $i$ 的增大，$g_{i}$ 是单调不减的，所以 $g_{i-1} = g_{i}$ 或者 $g_{i-1} < g_{i}$，关键点在这，如果 $g_{i-1} < g_{i}$，那么 $g_{i-1}$ 必须是 $g_{i}$ 的约数，那么 $g$ 函数的减少成指数型，再推广来，在一个长度为 $N$ 的数组中，从任何位置开始的后缀 GCD，其不同的取值最多只有 $\log(max(A))$ 个。

而既然后缀 gcd 是跳变的，也就是某一段是保持不变的，那为什么我不直接跳转到下一个节点呢？和上面 1005 类似的，我们会想到用倍增 ST 表来预处理。

这里说一下 ST 表的适用条件，1. 静态区间无修改；2. 幂等性，也就是 $f(x, x) = x$，gcd 和 max 都满足这个条件。

但是，我是说但是，这种区间查询，线段树也能做，注意到了吗？但是线段树的复杂度是 $O(\log N)$，在大规模查询的规模下，我们更青睐适用条件小，但是复杂度更优的 $O(1)$ ST表。

至此，我们完成了前期准备工作，来到了最终处理查询的步骤。既然我们已知从当前位置 $cl$ 到区间右端点 $r$ 的后缀 $g_{i}$ 是一个段数极少的阶梯型序列，那么我们的目标就是，找到当前 $gcd$ 值 $g$ 能维持的最远距离 $cr$。

这里插入说明一下我的变量名：cl = current_left 当前左端点， cr 同理。

这个操作步骤只需要再 ST 表上，进行二分搜索或者倍增查询了，也就是在 $[cl, r]$ 范围内，寻找最大的 $cr$，使得 $query\_gcd( cr, r ) = g$。

接下来我们会遇到第二个难点，需要执行多少次操作才能让这段区间的所有 $b$ 都满足条件呢？当然还是贪心，前面提到修改当前位置会对右边的值产生连坐效果，不妨开一个临时变量 sum 记录累计的修改量。

然后查询区间内最大的 $b$，记作 maxb，那么需要减少 diff = maxb - sum，如果 $diff > 0$，还需要补充 $cnt = \lceil diff/g \rceil$ 次操作，最后更新答案 res += cnt 以及 sum += cnt * g。

在处理完当前段之后，让 $cl$ 直接跳转到 $cr + 1$，直接处理下一个 GCD 段。

最后统计一下复杂度 $O( Q \cdot \log( max A ) \cdot \log N)$，大概是没问题的。

1006 游戏

题意：

给定 $n$ 个属性，初始为 $0$；以及 $m$ 个加成可选，每个限选一次，第 $i$ 项属性值 $a_i$ 必须满足 $L_i \le a_i \le R_i$ 才能产生伤害 $f_{i, a_i-L_i}$。

$n \le 6, m \le 30, k \le 150, L_i \ge 40$。

思路：

这里直接跟着题解思路来了，因为门槛是 40 点，所以最多只有三种情况能造成伤害。这就意味着我们不用枚举一个六维的背包，只需要枚举哪三个数学是有效的即可降维。

如果某项属性即便加上所有 $m$ 个加成，也达不到门槛，则可以直接剪枝。然后枚举所有大小为 $3$ 的子集即可（ 组合数 $\binom{n}{3} \leq 20$ ）。

状态定义：$dp[v_1][v_2][v_3]$ 表示要使选中的三项属性分别达到值 $v_1, v_2, v_3$ 时，所有 $n$ 项属性消耗的总点数的最小值。

状态转移：参考 0/1 背包，对于每一个加成，记录其对选中三项属性的增量 $(g_1, g_2, g_3)$ 和总增量 $sg$。

$$dp[v_1][v_2][v_3] = \min(dp[v_1][v_2][v_3], \ dp[v_1-g_1][v_2-g_2][v_3-g_3] + sg)$$

注：为了符合 0/1 背包的要求，需采用逆序遍历。

最后统计答案，满足 $dp[v_{1}][v_{2}][v_{3}] \leq 150$，就根据答案算出当前属性值下的伤害总和，然后更新全局最大值即可。

你以为这就结束了吗？这题还卡常数，虽然我们的复杂度没问题，但是还是会TLE，所以再次考虑优化，发现即便所有的加成总增量加起来也不会超过 150，这意味着我们根本就不需要在 DP 中记录最小的消耗点数，因为即便全选也不会超标。

此时，问题就从 “求最小消耗” 转化为 “判定是否可达”，既然如此，开一个 bool 数组就能满足了，不妨再拓展一步，都用 bool 了，为什么不用 bitset 再优化呢？于是就这么水过去了。