T1

100%

直接尽量多做“包装 $x$ 瓶”的操作即可。设做了 $\left\lfloor \frac{n}{x} \right\rfloor$ 次这种操作后，还剩下 $n \bmod x$ 瓶；剩余的每一瓶都只能单独包装，因此还需要 $n \bmod x$ 次操作。

所以答案就是：

$$\left\lfloor \frac{n}{x} \right\rfloor + n \bmod x $$

时间复杂度 $O(1)$。

T2

100%

规则是：

• P 得分为 $300+combo$，然后连击数加 $1$；
• G 得分为 $100+combo$，然后连击数加 $1$；
• M 不得分，连击数清零。

因此只需要从左到右模拟一遍，记录当前连击数 combo、累计总分 ans 和历史最大连击数 mx：

• 遇到 P 时，ans += combo + 300，再令 combo++；
• 遇到 G 时，ans += combo + 100，再令 combo++；
• 遇到 M 时，combo = 0。

每次更新后用 mx = max(mx, combo) 维护最大连击数即可。

最后输出 ans 和 mx。

时间复杂度 $O(n)$。

T3

100%

给定一个 $01$ 串 $s$ 和整数 $k$，统计满足 $i<j$、$s_i=0$、$s_j=1$、且 $j-i\le k$ 的数对个数。

可以把它看成在长度不超过 $k+1$ 的窗口内，统计每个 1 左边有多少个 0。

我们可以从左到右扫描字符串时，维护当前窗口内 0 的个数 cnt：

• 当前字符是 0，就把 cnt++；
• 当前字符是 1，就把当前窗口内的所有 0 都与它配对，因此答案加上 cnt。
• 当右端点在位置 $i$ 时，当前窗口为 $[i-k,i]$，下一个窗口为 $[i-k+1,i+1]$，因此需要位于 $i-k$ 的字符：如 果 $i-k$ 位置是 0，那么 cnt--，否则 cnt 不变。

这样每个字符只进出窗口一次，整体就是一个长度为 $k+1$ 的滑动窗口统计。

时间复杂度 $O(n)$。

T4

100%

由于强化牌会将后续所有的伤害牌进行强化，因此选出若干张手牌后，出牌的顺序一定是先打出所有强化牌，然后再打出所有伤害牌。

然后思考如何计算最终总伤害：设选中的强化牌的 $x_i$ 之和为 $S$，选中的伤害牌的 $x_i$ 之和为 $D$，每张伤害牌的伤害为 $x_i \times (1+S)$，因此打出的总伤害为：

$$\sum_{\text{伤害牌}} x_i \times (1+S) = D \times (1+S) $$

问题转化为我们需要在费用 $C$ 内，选择一组强化牌（总费用 $c_S$，总加成 $S$），和一组伤害牌（总费用 $c_D$，总基础伤害和 $D$），最大化 $D \times (1+S)$，且 $c_S + c_D \leq C$。两类牌的选择是独立的，只有费用共享。

由于 $n,C \leq 1000$，我们可以对两类牌分别做 0/1 背包，再枚举费用分配求最优解。

设：

• f[j] 表示花费不超过 $j$ 的前提下，所有伤害牌能获得的最大基础伤害和；
• g[j] 表示花费不超过 $j$ 的前提下，所有强化牌能获得的最大法术强度和。

两类牌分别做一次 0/1 背包：

• 若是伤害牌，就更新 f；
• 若是强化牌，就更新 g。

最后枚举总费用分配：假设给强化牌分配了 $i$ 点费用，那么伤害牌就分配 $C-i$ 点费用，答案为：

$$\max_{0\le i\le C} (g[i]+1) \times f[C-i]$$

需要注意乘积可能超过 32 位整型范围。

时间复杂度 $O(nC)$，空间复杂度 $O(C)$。

T5

100%

由于 $n \leq 10^4$，我们可以 $n^2$ 枚举所有连续子串并统计答案，但需要快速计算当前子串的 $f$ 值。

设当前固定左端点为 $i$，向右枚举右端点 $j$。固定左端点后，先令 now = -1（当子串只有一个字符时 $now=0$），并将每个字符第一次出现的位置数组清空。用 now 表示子串 $s[i..j-1]$ 的答案，当我们把右端点从 $j-1$ 扩展到 $j$ 时，有两种选择：

• 直接删除新字符 s[j]，那么当前子串答案为 now + 1；
• 如果新字符 s[j] 之前在子串 $s[i..j-1]$ 中出现过，则可以保留 s[j]，设第一次出现位置是 p，那么可以保留从 $p$ 到 $j$ 的这一段，让首尾字符相同，此时需要删除的只有 p 前面那部分字符，答案为 p - i。

于是新的答案可以更新为：

$$now = \min(now+1,\, p-i)$$

其中若当前字符 $s[j]$ 从未出现过，就只能删除该字符，令 $now=now+1$。每个字符第一次出现的位置可以通过一个数组来记录：每次枚举一个左端点 $i$ 时创建该数组，枚举 $j$ 并更新 now 后，若 $s[j]$ 第一次出现，则更新数组。

每次更新后把 now 累加到答案中，就得到了所有子串的总和。

时间复杂度 $O(n^2)$。

T6

100%

我们首先分析两种操作：

对 $A$ 的操作会同时给相邻两个位置加上同一个数，因此 $A$ 的“奇偶位交替和”不变。设：

$$Sum_A = a_1-a_2+a_3-a_4+\cdots$$

并且由于 $k$ 可以取任意整数，且这种操作只会给相邻两个位置同时加上同一个值，所以它保留了交替和不变；反过来，也可以通过逐步调整相邻差分，把任意交替和等于 $Sum_A$ 的序列互相变换，因此 $A$ 可以通过操作变成任意一个交替和等于 $Sum_A$ 的序列。

而对 $B$ 的操作只是交换相邻元素，可以把 $B$ 变成任意排列，并且总和不变，记为：

$$Sum_B = \sum_{i=1}^n b_i$$

所以原问题等价于：是否存在一个 $B$ 的排列，使得它的交替和恰好等于 $Sum_A$。

当序列长度为 $n$ 时，奇数位置有 $\left\lceil {\frac{n}{2}} \right\rceil$ 个，如果我们从 $B$ 中选出 $\left\lceil {\frac{n}{2}} \right\rceil$ 个数放在奇数位置，它们的和为 $X$，那么放在偶数位置的数的和就是 $Sum_B - X$。

此时整个序列的交替和为:

$$X-(Sum_B - X) = 2X-Sum_B$$

我们需要让交替和等于 $Sum_A$：

$$2X-Sum_B=Sum_A$$

化简得：

$$X = \frac{Sum_A + Sum_B}{2}$$

因此问题就变成：

• 从 $B$ 中选出恰好 $\left\lceil \frac{n}{2} \right\rceil$ 个数放到奇数位；
• 这些数的和是否能等于 $\frac{Sum_A + Sum_B}{2}$。

如果 $Sum_A+Sum_B$ 是奇数，显然无解，直接输出 No。

剩下就是一个“选固定个数、固定总和”的子集和问题，由于 $n \leq 40$，如果暴力枚举所有组合，最多会有 $\binom{40}{20}$ 种情况，无法通过题目，需要使用折半枚举的技巧：

• 把 $B$ 数组分成前后两半；
• 枚举前半部分的所有子集，记录当前子集选了多少个数以及总和，记录到哈希表中；
• 再枚举后半部分的所有子集，在哈希表中检查是否存在一个子集，与前半子集合并后，使得总个数恰好是 $\left\lceil \frac{n}{2} \right\rceil$，总和恰好是目标值 $X$。

只要存在一种这样的划分，就能通过相邻交换把 $B$ 排成目标顺序，再利用 $A$ 的操作把两边变成同一个数组。

时间复杂度约为 $O(2^{n/2})$：左半枚举是 $O(2^{n/2})$，右半枚举也是 $O(2^{n/2})$；如果写法不当，可能会多乘一个 $n$。每次左右合并可以做到 $O(1)$，若用 map 或二分查找，则会多一个 $\log(2^{n/2})=\frac{n}{2}$ 的因子，因此这里更适合使用哈希表。