T1

100%

用循环枚举 $i=1\sim n-2$，判断 $A_i>A_{i+1}$ 与 $A_{i+1}>A_{i+2}$ 是否同时成立，如果同时成立那么答案增加 $1$。

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

T2

100%

最优策略为让高位的数字尽可能大。

从高位到低位确定答案的每一位，维护剩余位的数位和 $now$，初始 $now=m$：

• 如果 $now\geq 9$，那么这一位最多选 $9$：先输出 $9$，然后 $now-=9$；
• 否则这一位最多选 $now$：先输出$now$，然后 $now=0$。

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

T3

100%

用一个 $\text{char}$ 数组来模拟队列。用一个 $\text{bool}$ 数组 $f[i]$ 表示字母 $i$ 是否在队列中：$f[i]=1$ 表示字母 $i$ 在队列中，$f[i]=0$ 表示字母 $i$ 不在队列中。

循环枚举 $i=1\sim n$：

• 如果 $f[s[i]]=0$，说明队列中没有字母 $s[i]$，将 $s[i]$ 添加到队列尾部；
• 如果 $f[s[i]]=1$，说明队列中有字母 $s[i]$，需要将这两个 $s[i]$ 以及中间的字母都消除：从队尾开始不断删除元素，直到删除了一个字母 $s[i]$ 后停止。

将队列中的元素按从队首到队尾的顺序输出。

每个字母最多被添加一次，被删除一次。

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

T4

100%

将 $a_i$ 按从大到小的顺序排序后，最优方案即为：第 $1$ 个支架用长度为 $a_1$ 和 $a_{2\times m}$ 的木棍制作，第 $2$ 个支架用长度为 $a_2$ 和 $a_{2\times m-1}$ 的木棍制作，以此类推。

因此枚举 $i=1\sim m$，答案为 $\min\{a_{i}\times a_{2\times m+1-i}\}$。

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

T5

20%

每个球有 $k$ 种颜色可选，因此初始情况共有 $k^n$ 种。

只要初始情况中存在至少一个颜色为 $1$ 的球，最终就能够合成出颜色为 $1$ 的球。

反过来，只有当初始情况中所有球的颜色都不为 $1$ 时，最终不能够合成出颜色为 $1$ 的球。此时每个球只有 $2\sim k$ 这 $k-1$ 种颜色可选，因此这类初始情况共有 $(k-1)^n$ 种。

用循环分别求出 $k^n$ 和 $(k-1)^n$，答案即为 $k^n-(k-1)^n$。

注意取模。

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

60%

用快速幂分别求出 $k^n$ 和 $(k-1)^n$ 即可。

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

100%

因为模数 $P=998244353$ 是一个质数，根据费马小定理，$a^{P-1}\mod P=1$，其中 $a$ 是任意和 $P$ 互质的整数。

$k$ 和 $k-1$ 都与 $998244353$ 互质，因此 $k^n\mod P=k^{n\mod (P-1)}\mod P$，$(k-1)^n\mod P=(k-1)^{n\mod (P-1)}\mod P$。

先求出 $y=n\mod (P-1)$，再用快速幂分别求出 $k^y$ 和 $(k-1)^y$，答案即为 $k^y-(k-1)^y$。

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

T6

20%

定义 $dp[i][j]$ 表示只考虑前 $i$ 道题，共回答了 $j$ 道题且其中包括了第 $i$ 道题的最大总得分。初始时只有 $dp[0][0]=0$，其余都为负无穷。

定义函数 $f(i)$ 表示连续跳过 $i$ 道题会扣多少分：

• 如果 $i\leq k$，那么每道题扣 $b$ 分，$f(i)=b\times i$；
• 否则前 $k$ 道题每道扣 $b$ 分，剩余 $i-k$ 道题每道扣 $c$ 分，$f(i)=b\times k+c\times (i-k)$。

考虑如何计算 $dp[i][j]$，假设上一次回答的问题是第 $x$ 道题，三重循环进行转移：

• 第一重循环枚举 $i=1\sim n$，第二重循环枚举 $j=1\sim m$，求 $dp[i][j]$；
• 第三重循环枚举 $x=0\sim i-1$；
• 此时前 $x$ 道题中回答了 $j-1$ 道，然后连续跳过 $i-x-1$ 道题，再答对第 $i$ 道题得 $a_i$ 分，转移为 $dp[i][j]=\max\{dp[x][j-1]+a_i-f(i-x-1)\}$。

最后一次答题后可能还会跳过题目，为了便于计算可以虚构出第 $n+1$ 道题，$a_{n+1}=0$。答案即为 $dp[n+1][m+1]$。

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

30%

对于测试点#4，因为 $b=c$，所以 $f(i)=b\times i$。

在第一部分基础上，考虑求 $dp[i][j]$ 的转移，此时 $i,j$ 视为固定值：

• $dp[x][j-1]+a_i-f(i-x-1)=a_i-b\times (i-1)+dp[x][j-1]+c\times x$，其中 $a_i-b\times (i-1)$ 为固定值，$dp[x][j-1]+c\times x$ 只和 $x$ 有关，因此维护 $g[i][j]=\max_{y\leq i}\{dp[y][j]+c\times y\}$，转移为 $dp[i][j]=\max\{a_i-b\times (i-1)+g[i-1][j-1]\}$；
• 计算完 $dp[i][j]$ 后更新 $g[i][j]=\max(g[i-1][j],dp[i][j]+c\times i)$。

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

结合第一部分可以拿到 $30\%$ 的分数。

40%

对于测试点#3，因为 $k=1$，所以除了 $f(0)=0$ 之外，对于 $i\geq 1$ 有 $f(i)=b+c\times (i-1)$。

在第二部分基础上稍加修改：

• 如果 $x=i-1$，转移为 $dp[i][j]=\max\{dp[i-1][j-1]+a_i\}$；
• 否则，$dp[x][j-1]+a_i-f(i-x-1)=a_i-b-c\times (i-2)+dp[x][j-1]+c\times x$，其中 $a_i-b-c\times (i-2)$ 为固定值，$dp[x][j-1]+c\times x$ 只和 $x$ 有关，转移为 $dp[i][j]=\max\{a_i-b-c\times (i-2)+g[i-2][j-1]\}$。

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

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

100%

对于 $i<k$ 有 $f(i)=b\times i$，对于 $i\geq k$ 有 $f(i)=b\times k+c\times (i-k)$。

在第三部分的基础上，用单调队列处理 $i-k\leq x\leq i-1$ 的部分：

• 如果 $i-k\leq x\leq i-1$，$dp[x][j-1]+a_i-f(i-x-1)=a_i-b\times (i-1)+dp[x][j-1]+b\times x$，其中 $a_i-b\times (i-1)$ 为固定值，$dp[x][j-1]+b\times x$ 只和 $x$ 有关，但由于要求 $x\geq i-k$，所以我们用单调队列维护这一部分，具体来说：
  • 单调队列 $q[j]$ 内的元素 $x$，对应第 $j$ 次回答的问题是第 $x$ 道题；
  • 保证队列内的元素 $x$ 满足 $dp[x][j]+b\times x$ 递减；
  • 当 $x<i-k$ 时令 $x$ 出队；
  • $x$ 取 $q[j-1]$ 的队首元素 $qx$ 时 $dp[x][j-1]+b\times x$ 取到最大值，转移为 $dp[i][j]=\max\{a_i-b\times (i-1)+dp[qx][j-1]+b\times qx\}$；
• 否则，$dp[x][j-1]+a_i-f(i-x-1)=a_i-b\times k-c\times (i-k-1)+dp[x][j-1]+c\times x$，其中 $a_i-b\times k-c\times (i-k-1)$ 为固定值，$dp[x][j-1]+c\times x$ 只和 $x$ 有关，转移为 $dp[i][j]=\max\{a_i- b \times k -c\times (i- k - 1)+g[i-k-1][j-1]\}$。

注意：因为 $i-k\leq x\leq i-1$ 时的转移要用到 $q[j-1]$，如果 $j$ 是从小到大枚举，需要在计算完所有 $dp[i][j]$ 之后，再把元素 $i$ 分别加到各个优先队列中。

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