T1

100%

读入字符串 $S$，枚举字符串 $S$ 的第 $i$ 位，如果 $S[i]$ 等于 ?，那么将 $S[i]$ 修改为 !。

全部修改完后再输出 $S$ 即可。

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

T2

100%

两重循环：

• 第一层循环枚举 $i=2\sim n$；
• 第二层循环枚举 $j=1\sim i-1$，如果 $h[j]>h[i]$，将 $h[j]$ 与 $h[i]$ 进行交换，并使用 $\text{break}$ 语句结束本次循环。

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

T3

50%

维护当前等级 $x$ 和当前经验 $y$，初始时 $x=1,y=0$。

用一个循环枚举刷题过程：

• 先增加 $x$ 点经验：$y+=x$；
• 判断当前经验是否能升级，如果 $y\geq k\times x^2$ 说明能升级，那么消耗 $k\times x^2$ 点经验升级：$y-=k\times x^2$，$x++$。

注意消耗经验和升级这两条语句的顺序。

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

100%

当你为 $x$ 级 $0$ 经验时，你刷 $k\times x$ 道题正好获得 $k\times x^2$ 经验，升到 $x+1$ 级 $0$ 经验。

所以我们维护剩余题数 $now$，初始 $now=n$，用一个 $\text{while}$ 循环来模拟这个过程：

• 如果 $now\geq k\times x$，那么我们刷 $k\times x$ 道题然后升一级：$now-=k\times x$，$x++$；
• 否则我们刷完这 $now$ 道题也不能升级：$y+=now\times x$，$now=0$；
• 当 $now$ 变为 $0$ 时结束循环，所以 $\text{while}$ 的循环条件为 $now>0$。

升到 $v$ 级需要刷 $k \times (1+2+3+\dots+(v-1))= k \times \frac{v\times (v-1)}{2}$ 道题，因此最终等级不会超过 $2\times\sqrt{n}$，也就是说循环最多运行 $2\times \sqrt{n}$ 次。

时间复杂度 $O(\sqrt{n})$。

T4

40%

维护二维数组 $a[i][j]$ 表示位于第 $i$ 行第 $j$ 列的同学的编号，初始 $a[i][j]=(i-1)\times m+j$。

按顺序执行每条训练指令，对于第 $i$ 条训练指令：

• $1$ 类指令，用一个循环枚举 $i=1\sim m$，交换 $a[x][i]$ 和 $a[y][i]$；
• $2$ 类指令，用一个循环枚举 $i=1\sim n$，交换 $a[i][x]$ 和 $a[i][y]$；
• $3$ 类指令，输出 $a[x][y]$。

时间复杂度 $O(nm+q(n+m))$。

60%

对于测试点#5~6，因为不存在 $2$ 类指令，所以每一行的内部不发生交换，交换只发生在行与行之间。

维护数组 $r[i]$ 表示现在位于方阵第 $i$ 行的同学初始时位于方阵的哪一行，初始 $r[i]=i$。

按顺序执行每条训练指令，对于第 $i$ 条训练指令：

• $1$ 类指令，交换 $r[x]$ 和 $r[y]$；
• $3$ 类指令，现在位于第 $x$ 行第 $y$ 列的同学，初始时位于方阵的第 $r[x]$ 行第 $y$ 列，输出 $(r[x]-1)\times m+y$。

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

100%

行的交换与列的交换是互相独立的：一个同学最终位于哪一行只和 $1$ 类指令有关，最终位于哪一列只和 $2$ 类指令有关。

维护数组 $r[i]$ 表示现在位于方阵第 $i$ 行的同学初始时位于方阵的哪一行，数组 $c[i]$ 表示现在位于方阵第 $i$ 列的同学初始时位于方阵的哪一列，初始 $r[i]=i,c[i]=i$。

按顺序执行每条训练指令，对于第 $i$ 条训练指令：

• $1$ 类指令，交换 $r[x]$ 和 $r[y]$；
• $2$ 类指令，交换 $c[x]$ 和 $c[y]$；
• $3$ 类指令，现在位于第 $x$ 行第 $y$ 列的同学，初始时位于方阵的第 $r[x]$ 行第 $c[y]$ 列，输出 $(r[x]-1)\times m+c[y]$。

时间复杂度 $O(n+m+q)$。

T5

20%

当 $k=2$，合法密码即为相邻位不同的密码。

那么合法密码仅有两种：①形如 $121212\dots$，即奇数位为 $1$ 偶数位为 $2$；②形如 $212121\dots$，即奇数位为 $2$ 偶数位为 $1$。

对于第一种情况，奇数位只能是 $1$ 或 $0$，偶数位只能是 $2$ 或 $0$。枚举 $S$ 的每一位进行判断，都满足则答案增加 $1$。

对于第二种情况，奇数位只能是 $2$ 或 $0$，偶数位只能是 $1$ 或 $0$。枚举 $S$ 的每一位进行判断，都满足则答案增加 $1$。

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

60%

定义 $dp[i][j][len]$ 表示只考虑前 $i$ 位，其中的最后一段为 $len$ 个 $j$ 的合法密码的数量。

• 如果 $S_1\neq 0$，初值为 $dp[1][S_1][1]=1$；
• 否则枚举 $j=1\sim k$，初值为 $dp[1][j][1]=1$。

考虑当 $i>1$ 时的转移：

• 第一重循环枚举第 $i-1$ 位的数字 $y=1\sim k$；
• 第二重循环枚举前 $i-1$ 位的最后一段的长度 $len=1\sim k-1$；
• 如果 $S_i=0$ 则第三重循环枚举第 $i$ 位的数字 $x=1\sim k$，否则第 $i$ 位的数字 $x=S_i$；
• 如果 $x\neq y$，那么此时前 $i$ 位数字的最后一段为 $1$ 个 $x$，转移为 $dp[i][x][1]+=dp[i-1][y][len]$；
• 如果 $x=y$ 且 $len<k-1$，那么此时前 $i$ 位数字的最后一段为 $len+1$ 个 $x$，转移为 $dp[i][x][len+1]+=dp[i-1][x][len]$。

时间复杂度 $O(nk^3)$。

100%

观察第二部分，我们发现：

• $dp[i][x][1]=\sum_{y\neq x}\sum_{z=0}^{k-1}dp[i-1][y][z]$；
• 对于 $len>1$，$dp[i][x][len]=dp[i-1][x][len-1]$。

其中 $dp[i][x][1]$ 的部分是复杂度的瓶颈。

定义 $f[i][j]$ 表示只考虑前 $i$ 位，第 $i$ 位为 $j$ 的合法密码的总数量。$f[i][j]=\sum_{len=1}^{k-1} dp[i][j][len]$。

定义 $g[i]$ 表示只考虑前 $i$ 位，合法密码的总数量。$g[i]=\sum_{x=1}^k f[i][x]$。

$dp[i][x][1]=\sum_{y\neq x}\sum_{z=0}^{k-1}dp[i-1][y][z]=g[i-1]-f[i-1][x]$，这样就可以把单个状态转移的复杂度降低到 $O(1)$。

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

可以使用滚动数组的技巧来降低空间复杂度。

T6

10%

将学生按照分数从大到小排序，然后分为四类，用四个数组分别处理：

• 语文数学都好的同学称为 $A$ 类学生，用数组 $A$ 储存他们的分数，计算其中分数前 $i$ 大的学生的总分 $sA[i]=A[1]+A[2]+\dots+A[i]$；
• 只有语文好的同学称为 $B$ 类学生，用数组 $B$ 储存他们的分数，计算其中分数前 $i$ 大的学生的总分 $sB[i]=B[1]+B[2]+\dots+B[i]$；
• 只有数学好的同学称为 $C$ 类学生，用数组 $C$ 储存他们的分数，计算其中分数前 $i$ 大的学生的总分 $sC[i]=C[1]+C[2]+\dots+C[i]$；
• 语文数学都不好的同学称为 $D$ 类学生，用数组 $D$ 储存他们的分数，计算其中分数前 $i$ 大的学生的总分 $sD[i]=D[1]+D[2]+\dots+D[i]$。

四重循环分别枚举：

• $A$ 类学生选 $nA$ 名，$B$ 类学生选 $nB$ 名，$C$ 类学生选 $nC$ 名，$D$ 类学生选 $nD$ 名；
• 然后判断，如果满足 $nA+nB+nC+nD=m$ 且 $nA+nB\geq k_1$ 且 $nA+nC\geq k_2$；
• 那么更新答案 $ans=\max(ans,sA[nA]+sB[nB]+sC[nC]+sD[nD])$。

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

40%

在第一部分的基础上，只枚举 $nA,nB,nC$：

• 要求 $nA+nB+nC\leq m$，此时 $nD=m-nA-nB-nC$；
• 然后判断，如果满足 $nA+nB\geq k_1$ 且 $nA+nC\geq k_2$；
• 那么更新答案 $ans=\max(ans,sA[nA]+sB[nB]+sC[nC]+sD[nD])$。

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

60%

对于测试点#5~6，因为 $l_2>r_1$，所以不存在 $A$ 类学生。

因此 $B$ 类学生至少要选 $k_1$ 名，$C$ 类学生至少要选 $k_2$ 名。

• 先选分数最大的 $k_1$ 名 $B$ 类学生和 $k_2$ 名 $C$ 类学生，要求 $k_1+k_2\leq m$；
• 从剩下的学生中选出分数最大的 $m-k_1-k_2$ 名：将剩余的 $B$ 类和 $C$ 类学生，以及所有 $D$ 类学生，一起按分数从大到小排序，选其中分数最大的 $m−k_1−k_2$ 名。

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

结合第二部分可以拿到 $60\%$ 的分数。

100%

在第三部分的基础上，从小到大枚举选择了 $nA$ 名 $A$ 类学生：

• 如果 $nA<k_1$ 那么 $B$ 类学生中必选分数最大的 $k_1-nA$ 名，要求 $B$ 类学生至少有 $k_1-nA$ 名；
• 如果 $nA<k_2$ 那么 $C$ 类学生中必选分数最大的 $k_2-nA$ 名，要求 $C$ 类学生至少有 $k_2-nA$ 名；
• 要求 $k_1+k_2-nA\leq m$；
• 剩余学生中选分数最大的 $m-(k_1+k_2-nA)$ 名，使用对顶堆的技巧来处理这个部分：
  • 用小根堆 $qL$ 和大根堆 $qR$ 来储存这些学生，分数最大的那部分储存在 $qL$ 中，分数最小的那部分储存在 $qR$ 中；
  • 在最开始把所有 $C$ 类学生放入 $qL$；
  • 因为 $nA$ 是从小到大枚举，所以 $k_1-nA$ 和 $k_2-nA$ 都是变小的，每次将不再必选的 $B$ 类或 $C$ 类学生放入对顶堆：如果分数大于 $qL$ 中分数最小的学生那么放入 $qL$，否则放入 $qR$；
  • 然后通过将 $qL$ 中分数最小的学生取出放到 $qR$ 中，或将 $qR$ 中分数最大的学生取出放到 $qL$ 中，将 $qL$ 中元素的数量调整为 $m-(k_1+k_2-nA)$，代表选剩余学生中分数最大的 $m-(k_1+k_2-nA)$ 名；
  • 过程中维护 $qL$ 中的元素之和 $sQ$;
• 更新答案 $ans=\max(ans,sA[nA]+sB[k_1-nA]+sC[k_2-nA]+sQ)$。

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