练习赛153题解

A. 插入

思路

插入的 6 只可能作为子序列 2026 的最后一位。

设插入位置为 ，新增贡献等于前缀中子序列 202 的个数。

随着位置右移，前缀只会变长，贡献单调不减，因此最优位置一定是末尾，即

做法

直接输出字符串长度。

复杂度

B. 变化

原序列中 对所有前缀和总和的贡献系数为 。若删除第 个数：

• 前面的每个数贡献系数都会少 1，总损失为 ；
• 本身被删除，损失为 ；
• 后面的数虽然位置前移，但贡献系数不变。

因此删除第 个位置后的答案等于原答案减去

要让剩余前缀和总和最大，只需找到上式最小的位置。扫描时维护前缀和即可。

时间复杂度 。

C. 博弈

思路

操作只会改变奇偶性。

• 加奇数会翻转奇偶。
• 加偶数不会改变奇偶。

对区间 来说，位置 会加上 ，因此只有与 同奇偶的那些位置会翻转奇偶性，另一类位置保持不变。

记当前分差为

把同一类下标单独拿出来，并将元素映射为：

• 原数为偶数，记为 。
• 原数为奇数，记为 。

如果在这类数组中选一个连续段进行翻转，分差会变成

所以问题就变成：在奇下标数组和偶下标数组中分别求最大子段和，再取最大值。

做法

分别对两个数组跑一遍最大子段和，答案为

判断最终是否大于 即可。

复杂度

D. 异或和 I

思路

值域满足 ，因此任意一段的异或和都不超过 。

设 表示前缀异或和。定义

表示前 个数已经划分完，且最后一段异或和为 时的最优结果。

同时维护前缀最优

方便保证异或和序列单调不减。

转移

枚举最后一段的起点 ，则这一段的异或和为

于是可以从前 个数中所有“最后一段异或和不超过 ”的状态转移过来：

如果得到相同的最优值，就把方案数累加到对应状态里。

复杂度

E. 异或和 II

思路

按位计算贡献。

固定某一位，设：

• 有 个数这一位为 ；
• 有 个数这一位为 。

我们只关心这一位最终是否为 ，也就是：

当前所有长度不超过 的非空子序列中，OR 后这一位为 的方案数奇偶性。

固定长度 的贡献

若子序列长度恰好为 ，那么这一位 OR 为 ，当且仅当选出的 个数全都来自那 个这一位为 的数。

因此，长度恰好为 时，这一位为 的方案数为

所以对于“长度不超过 ”的询问，这一位为 的总方案数奇偶性为

模 下减法等于加法，因此等价于

前缀和化简

记

它表示“从 个数里选出长度不超过 的非空子集，方案数的奇偶性”。

当 时显然有

当 时，我们需要用到下面这个恒等式：

证明

由 Pascal 恒等式：

两边对 求和：

第二项换元 ，并约定越界组合数为 ，可得

所以

现在对模 来看，右边前 项中的

都各出现了两次，模 下全部抵消，只剩下

因此

证毕。

于是

代回原式：

判奇偶

由 Lucas 定理在模 下的结论可知：

也就是 的二进制每一位 ，都必须出现在 中。

因此可以 判断一个组合数模 的值，进而在 时 算出 。

做法

维护每一位当前有多少个数该位为 ，记为 cnt[b]。

对于一次询问 2 k，先算出 total = F(n,k)，再枚举每一位 ：

若 ，那么这一位对答案的贡献就是 。

修改操作只会影响一个数的二进制位，因此逐位更新 cnt[b] 即可。

复杂度

设值域二进制位数为 ，则：

• 单次修改：
• 单次查询：

总复杂度为

F. 下棋

思路

转化为连通块问题。

对于黑方：

• 删除所有黑棋。
• 在剩余图上求连通块。

如果某个连通块不接触边界，那么它就被黑棋围住；它对答案的贡献等于这个连通块中的白棋数。白方同理。

动态维护

操作是单点修改，因此图会动态变化。这里使用：

线段树分治 + 可撤销并查集

并查集维护

每个连通块维护两个信息：

• sum：目标棋子的数量。
• touch：是否接触边界。

于是该连通块的贡献可以写成

线段树分治

1. 记录每个点的存在时间区间。
2. 枚举相邻点，求出每条边的存在时间区间。
3. 将点和边挂到时间线段树上。
4. DFS 线段树，进入时加点、合并边并统计答案，离开时回滚。

黑白分别维护一套即可。

复杂度