T1

100%

题目已经给出第 $i$ 个测试点能够通过的条件：

$$n_i\le x\quad\text{或}\quad m_i=1.$$

用一个变量记录满足条件的测试点个数。依次读入 $k$ 个测试点，若上述条件成立就把答案加一。最容易写错的是把“或”误写成“且”。

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

T2

100%

设 $r_i$ 为在第 $i$ 行游动的小鱼数量，$c_i$ 为在第 $i$ 列游动的小鱼数量。多条鱼可能位于同一行或同一列，因此这里记录的是数量而不是是否出现。

左上角为 $(x,y)$ 的区域能吃到 $R(x)+C(y)$ 条鱼，其中

$$R(x)=r_x+r_{x+1}+r_{x+2}, C(y)=c_y+c_{y+1}+c_{y+2}$$

此时如果我们枚举 $x,y$ 的值后，计算 $R(x) + C(y)$ 也可通过，时间复杂度为 $O(n^2 + m)$，以下介绍一种 $O(n+ m)$ 的做法。

$R(x)$ 只由 $x$ 决定，$C(y)$ 只由 $y$ 决定，所以可以分别求两者的最大值。若 $x_0$ 使 $R$ 最大、$y_0$ 使 $C$ 最大，那么对任意 $(x,y)$ 都有

$$R(x)+C(y)\le R(x_0)+C(y_0),$$

故 $(x_0,y_0)$ 是全局最优位置。

从小到大枚举 $x$ 和 $y$，并且只在窗口和严格变大时更新。这样出现并列最优时，会自然保留最小的 $x$ 和 $y$，满足题目的要求。

读入并统计小鱼需要 $O(m)$，枚举所有三行、三列窗口需要 $O(n)$。总时间复杂度为 $O(n+m)$。

T3

100%

假设调整后所有元素都等于 $v$。

对于每个奇数下标 $i$，有

$$a_i+x=v.$$

所有奇数位置加上的数相同，因此它们在调整前就必须全部相等。记这个公共值为 $O$。

同理，所有偶数位置在调整前也必须全部相等，记公共值为 $E$。当奇数、偶数位置都存在时，还需要

$$O+x=E-x,$$

即

$$2x=E-O.$$

于是合法解存在的条件为：

1. 所有奇数下标的值相同；
2. 所有偶数下标的值相同；
3. $E\ge O$；
4. $E-O$ 是偶数。

条件成立时，唯一可能的答案是

$$x=\frac{E-O}{2}.$$

该值既然唯一，自然也是最小合法值。

当 $n=1$ 时没有偶数位置。单个元素总是已经“全部相等”，最小答案为 $0$。

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

T4

30%

$n\le1000$，可以枚举每个 $x\in[1,n]$，再逐对检查

$$(a_i\le x)=(a_{n-i+1}\le x).$$

若所有对称位置都满足等式，则对应的二进制数组是回文数组。

共有 $n$ 个阈值，每个阈值检查 $O(n)$ 个位置，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

100%

本题有 $2$ 种实现方式，但思路上是类似的。

解法 1

子任务 1 的瓶颈是：阈值从 $x-1$ 变成 $x$ 时，绝大多数位置的 $b_i$ 没有变化，却仍然重新扫描了整个数组。

可以发现当阈值从 $x - 1$ 变成 $x$ 时，只有满足 $a_i=x$ 的位置会从 $1$ 变为 $0$，其余位置保持不变。

所以考虑记录每个值 $x$ 在数组中的全部出现位置，以及维护 $b_i \not= b_{n -i +1}$ 的对数。

当 $x$ 变化时，我们可以直接动态更新 $b$ 数组的值，从而维护出 $b_i \not= b_{n -i +1}$ 的对数，当$b_i \not= b_{n -i +1}$ 的对数为 $0$ 时，那么 $x$ 就是符合条件的，将其记录到答案中即可。

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

解法 2

考虑 $a$ 的一对值 $(a_i,a_{n -i + 1}) = (u , v)$，不妨设 $u<v$。根据二进制数组的定义：

• $x<u$ 时，两边都大于 $x$，二进制值同为 $1$；
• $u\le x<v$ 时，只有 $u\le x$，两边的二进制值不同；
• $x\ge v$ 时，两边都不大于 $x$，二进制值同为 $0$。

因此，这一对位置恰好使阈值区间

$$[u,v-1]$$

非法。若 $u=v$，它们对任意阈值都相等，不产生非法区间。

对每一对对称位置令

$$l=\min(a_i,a_{n-i+1}),r=\max(a_i,a_{n-i+1})$$

当 $l<r$ 时，使用差分数组把区间 $[l,r-1]$ 加一。

最后求差分数组的前缀和。阈值 $x$ 的覆盖次数就是在该阈值下失配的对称位置对数：覆盖次数为 $0$ 当且仅当数组 $b$ 是回文数组。

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

T5

100%

第 $t$ 秒在线的服务器恰好是满足 $a_i\ge t$ 的位置。设这些位置形成的极大连续段长度依次为

$$b_1,b_2,\ldots,b_k,$$

则这一秒完成的任务数为

$$F(t)=\sum_{j=1}^{k}p_{b_j}.$$

答案就是

$$\sum_{t\ge1}F(t).$$

随着 $t$ 变化，在线位置集合只会在某个 $a_i$ 处发生改变。因此，无须逐秒计算；只要按 $a_i$ 排序，在相邻事件值之间一次性累加贡献即可。

根据处理方式不同，有两种做法。

解法 1

将所有位置按 $a_i$ 从大到小排序。开始时所有位置都未激活，然后依次处理每个不同的在线时长 $v$，一次性激活所有满足 $a_i=v$ 的位置。

设当前所有连续段的单秒贡献之和为 $S$。激活位置 $i$ 时，它先单独形成长度为 $1$ 的连续段，因此令

$$S\mathrel{+}=p_1.$$

随后检查 $i-1$ 和 $i+1$。若相邻位置已经激活，就用并查集合并两个连续段。若合并前两段长度分别为 $x,y$，则更新$S-=p_x+p_y,S+=p_{x+y}$。

设处理完事件值 $v$ 后，下一个更小的事件值为 $w$；若不存在则令 $w=0$。此时已激活的位置恰好满足 $a_i\ge v$。对于所有整数秒 $t$ 满足

$$w<t\le v$$

在线位置集合都与当前状态相同，所以答案增加

$$(v-w)S$$

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

做法 2

也可以反过来维护：一开始把所有位置看作在线，令当前单秒贡献

$$S=p_n$$

将位置按 $a_i$ 从小到大排序并依次删除。用 set 维护已经删除的位置。

设上一个处理到的在线时长为 $last$。准备删除位置 $i$ 时，令 $v=a_i$。在删除之前，先累加 $(v-last)S$（表示上一个时间点到当前时间点的答案），再令 $last=v$。

接着在 set 中找到 $i$ 左右两侧最近的已删除位置 $l,r$。删除前，区间

$$[l+1,r-1]$$

是一段长度为 $r-l-1$ 的完整连续段。删除 $i$ 后，它被拆成长度分别为 $i-l-1, r-i-1$ 的两段，因此维护对应的 $S$ 的值即可。

最后把 $i$ 插入 set 即可。为了能在 set 中找到 $i$ 左右两侧最近的已删除位置，可以先在 set 中插入一个 $n + 1$ 和 $0$ 作为哨兵。

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

T6

30%

特殊性质 A 保证字符串中所有字符相同。于是任意非空集合 $A$ 都满足

$$s_{\min(A)}=s_{\max(A)}$$

问题变成求 $n$ 个有标号元素的集合划分数，即 Bell 数。具体求法可见 这里。

时间复杂度 $O(n^2)$ 即可通过。

100%

对于划分中的一个集合 $A$：

• 若 $|A|=1$，它是单元素集合，一定合法；
• 若 $|A|\ge2$，把 $\min(A)$ 视为集合的起点，$\max(A)$ 视为终点，其余元素视为内部元素。

按下标从小到大扫描时，一个非单元素集合会先在最小下标处被创建，接收若干内部元素，最后在最大下标处结束。合法条件只要求起点字符与终点字符相同。

因此，只需记录尚未结束的集合中，有多少个起点字符为 0，有多少个起点字符为 1。利用这个性质，我们考虑动态规划。

设 $f[i][x][y]$ 表示已经处理完前 $i$ 个下标，其中有 $x$ 个起点字符为 $0$ 的开放集合、$y$ 个起点字符为 $1$ 的开放集合时的方案数。已经处理的每个下标都恰好被分配到一个集合；已经关闭的集合不再需要记录。

初始时尚未处理任何下标，也没有开放集合，故$f[0][0][0]=1$。其余状态均为 $0$。处理完全部下标后不能留下开放集合，因此最终答案为 $f[n][0][0]$。

考虑转移。考虑处理下标 $i+1$，设当前字符为 $c=s_{i+1}$。这个下标有四种用途：

1. 单独构成一个单元素集合，开放集合数量不变，只有 $1$ 种选择；
2. 加入某个开放集合并作为内部元素，可以从 $x+y$ 个开放集合中选择一个，开放集合数量不变；
3. 成为一个新集合的起点，新增一个起点字符为 $c$ 的开放集合；
4. 成为某个开放集合的终点，只能选择起点字符同样为 $c$ 的开放集合。

以 $c=0$ 为例，四种用途的转移分别为：

1. $f[i][x][y]\to f[i+1][x][y]$
2. $(x+y)f[i][x][y]\to f[i+1][x][y]$
3. $f[i][x][y] \to f[i+1][x+1][y]$
4. $xf[i][x][y]\to f[i+1][x-1][y]$

所有下标越界的状态都视为 $0$。上述四种情况恰好覆盖了当前下标在所属集合中的所有可能角色，因此不会重复或遗漏任何划分。

总时间复杂度为 $O(n^3)$。使用滚动数组后空间复杂度为 $O(n^2)$。