T1

100%

答案为 $c_1\times n_1+c_2\times n_2+c_3\times n_3$。

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

T2

100%

提前计算编号 $i$ 的同学的通过科目数量 $num[i]$ 和所有科目总分 $sum[i]$。

用数组 $ans[i]$ 表示排在第 $i$ 名的同学的编号，初始时 $ans[i]=i$，然后按照题目所说的规则对 $ans$ 数组进行排序即可。

注意：比较通过科目数量时，应该看 $num[ans[i]]$ 和 $num[ans[j]]$，而不是 $num[i]$ 和 $num[j]$。比较所有科目总分时也一样。

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

T3

50%

对于每次点名，枚举每个同学，其中满足本次点名条件的同学记录他们被点到的次数增加了 $1$ 次。

记名字的最长长度为 $l=\max\{|S_i|\}$。

时间复杂度 $O(nl+mn)$。

100%

统计 $pre[j]$ 表示点到名字首字母为第 $j$ 个英文字母的点名有多少次，$suf[j]$ 表示点到名字末尾字母为第 $j$ 个英文字母的点名有多少次。

对于每个同学，算出他名字首字母是第 $x$ 个小写英文字母， 名字末尾字母是第 $y$ 个小写英文字母，那么他被点到的次数为 $pre[x]+suf[y]$。

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

T4

100%

定义函数 $f(x,y,m)$ 的功能为对左上角为 $(x,y)$ 且大小为 $2^m\times 2^m$ 的矩阵进行填数，函数里根据 $m$ 的大小分为两种情况：

• 当 $m>0$，依次调用 $f(x,y,m-1)$、$f(x,y+2^{m-1},m-1)$、$f(x+2^{m-1},y,m-1)$、$f(x+2^{m-1},y+2^{m-1},m-1)$，递归进行填数;
• 当 $m=0$，给 $(x,y)$ 填数。

主函数里只需调用一次 $f(1,1,n)$ 就能完成填数了。

注意：$2^{10}=1024$，数组不要开小了。

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

T5

20%

定义满足 $\text{MEX}(L,R)=i$ 的区间 $[L,R]$ 的数量为 $ans[i]$。

先用两重循环枚举区间的左端点 $L$ 和右端点 $R$，再用 $cnt[x]$ 统计区间 $[L,R]$ 内数字 $x$ 出现了几次，统计完成后再用一重循环遍历 $cnt$ 数组找到出现次数为 $0$ 的最小非负整数 $y$，即为这个区间的 $\text{MEX}$， $ans[y]$ 增加一。

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

60%

对于左端点同为 $L$ 的区间，当右端点从 $R$ 变为 $R+1$ 时，不需要重新统计一次区间 $[L,R]$ 中数字出现的情况，只需要在区间 $[L,R]$ 的基础上统计 $P_{R+1}$ 多出现了一次。所以 $cnt[x]$ 可以在改变区间右端点时顺便统计。

同时 $\text{MEX}(L,R+1)\geq\text{MEX}(L,R)$，所以当右端点从 $R$ 变为 $R+1$ 时，设 $\text{MEX}(L,R)=y$，只需要用一个 $\text{while}$ 循环在 $cnt[y]>0$ 时不断让 $y$ 自增，直到 $cnt[y]=0$ 时停止，那么此时的 $y$ 就是 $\text{MEX}(L,R+1)$。

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

100%

定义 $pos[x]$ 表示数字 $x$ 在 $P$ 中对应的下标，$pos$ 数组可以在输入时维护。

定义满足 $\text{MEX}(L,R)\geq i$ 的区间 $[L,R]$ 的数量为 $sum[i]$，其中 $sum[0]=\frac {n\times(n+1)}{2}$，即区间的总数量。

考虑当 $\text{MEX}(L,R)\geq x$ 时，则对于 $0\leq y\leq x-1$ 的每一个 $y$ 都有 $L\leq pos[y]\leq R$。

维护 $maxpos[x]$ 表示 $\max\{pos[0],pos[1],\dots,pos[x]\}$，$minpos[x]$ 表示 $\min\{pos[0],pos[1],\dots,pos[x]\}$。

那么 $sum[i]$ 即为同时满足 $L\leq minpos[i-1]$ 和 $R\geq maxpos[i-1]$ 的区间 $[L,R]$ 的数量，因此对于 $1\leq i\leq n+1$ 有 $sum[i]=(n-maxpos[i-1]+1)\times minpos[i-1]$。

满足 $\text{MEX}(L,R)= i$ 的区间 $[L,R]$ 的数量就是满足 $\text{MEX}(L,R)\geq i$ 的区间 $[L,R]$ 的数量减去满足 $\text{MEX}(L,R)\geq i+1$ 的区间 $[L,R]$ 的数量，即 $ans[i]=sum[i]-sum[i+1]$。

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

T6

30%

用二进制数表示对应子序列中每个字符是否被删除，其中为 $0$ 的位表示被删除，为 $1$ 的位表示没被删除。

为方便表示，仅在本题的第一部分中我们将字符的下标看成 $0\sim n-1$。

定义 $dp[b]$ 表示二进制数 $b$ 对应的子序列是否合法，其中 $dp[b]=1$ 表示合法，$dp[b]=0$ 表示不合法。初始时 $dp[0]=1$。

维护 $dp$ 数组，对于二进制下有偶数个 $1$ 的 $b$，设 $b$ 第一个为 $1$ 的位对应第 $L$ 个字符，最后一个为 $1$ 的位对应第 $R$ 个字符，考虑以下两类情况：

• 如果子序列的首尾两个字符是合法的并且中间的部分是合法的，即对于 $dp[2^L+2^R]=1$ 且 $dp[b-2^L-2^R]=1$，那么有 $dp[b]=1$；
• 如果子序列以第 $i$ 个字符为分界线分成两部分且两个部分都合法，即对于 $dp[b\%2^{i+1}]=1$ 且 $dp[b/2^{i+1}]=1$，那么有 $dp[b]=1$。

答案即为满足 $dp[b]=1$ 的 $b$ 的数量。

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

50%

对于测试点#4~5，字符串仅由 (、) 这两种字符组成，这种情况下一个合法的字符串，它的任意前缀中 ( 的数量都应该大于等于 ) 的数量。

将 ( 和 ) 两两配对，称没有配对的 ( 的数量为溢出。

定义 $dp[i][j]$ 表示只考虑前 $i$ 个字符时，溢出为 $j$ 的子序列的数量。初始仅有 $dp[0][0]=1$。

考虑第 $i+1$ 个字符的转移，设只考虑前 $i$ 个字符时溢出为 $j$：

• 若删除第 $i+1$ 个字符，那么溢出还是 $j$ 不变，所以 $dp[i+1][j]+=dp[i][j]$；

• 当第 $i+1$ 个字符为 (，那么若不删除第 $i+1$ 个字符则溢出增加一，所以 $dp[i+1][j+1]+=dp[i][j]$；

• 当第 $i+1$ 个字符为 ) 且 $j>0$，那么若不删除第 $i+1$ 个字符则溢出减少一，所以 $dp[i+1][j-1]+=dp[i][j]$。

答案为 $dp[n][0]$。

注意取模。

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

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

70%

对于测试点#6~7，字符串仅由 (、? 这两种字符组成。

尽量配对，称没有配对的 ( 或 ? 的数量为溢出。配对策略为：

• ( 一定会让溢出增加一；
• 如果当前溢出为 $0$，那么 ? 会让溢出增加一；
• 如果当前溢出不为 $0$，那么 ? 会和一个溢出的字符配对，让溢出减少一。

定义 $dp[i][j]$ 表示只考虑前 $i$ 个字符时，溢出为 $j$ 的子序列的数量。初始仅有 $dp[0][0]=1$。

考虑第 $i+1$ 个字符的转移，设只考虑前 $i$ 个字符时溢出为 $j$：

• 若删除第 $i+1$ 个字符，那么溢出还是 $j$ 不变，所以 $dp[i+1][j]+=dp[i][j]$；

• 当第 $i+1$ 个字符为 (，那么若不删除第 $i+1$ 个字符则溢出增加一，所以 $dp[i+1][j+1]+=dp[i][j]$；

• 当第 $i+1$ 个字符为 ? 且 $j=0$，那么若不删除第 $i+1$ 个字符则溢出增加一，所以 $dp[i+1][j+1]+=dp[i][j]$；

• 当第 $i+1$ 个字符为 ? 且 $j>0$，那么若不删除第 $i+1$ 个字符则溢出减少一，所以 $dp[i+1][j-1]+=dp[i][j]$。

答案为 $dp[n][0]$。

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

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

100%

尽量配对，但遇到 ) 时如果当前溢出为 $0$ 可以把之前已经完成的配对中的某对 (? 或 ?? 视为 $2$ 个溢出，称没有配对的 ( 或 ? 的数量为溢出，称已经配对的 (? 或 ?? 的数量为备用。配对策略为：

• ( 一定会让溢出增加一；
• 如果当前溢出为 $0$，那么 ? 会让溢出增加一；
• 如果当前溢出不为 $0$，那么 ? 会和一个溢出的字符配对，让溢出减少一，备用增加一；
• 如果当前溢出不为 $0$，那么 ) 会让溢出减少一；
• 如果当前溢出为 $0$，那么 ) 会把一个备用转化为两个溢出，并和一个溢出的字符配对，让溢出增加一，备用减少一。

定义 $dp[i][j][k]$ 表示只考虑前 $i$ 个字符时，溢出为 $j$ 且备用为 $k$ 的子序列的数量。初始仅有 $dp[0][0][0]=1$。

考虑第 $i+1$ 个字符的转移，设只考虑前 $i$ 个字符时溢出为 $j$ 且备用为 $k$：

• 若删除第 $i+1$ 个字符，那么溢出和备用都不变，所以 $dp[i+1][j][k]+=dp[i][j][k]$；
• 当第 $i+1$ 个字符为 (，那么若不删除第 $i+1$ 个字符则溢出增加一，所以 $dp[i+1][j+1][k]+=dp[i][j][k]$；
• 当第 $i+1$ 个字符为 ? 且 $j=0$，那么若不删除第 $i+1$ 个字符则溢出增加一，所以 $dp[i+1][j+1][k]+=dp[i][j][k]$；
• 当第 $i+1$ 个字符为 ? 且 $j>0$，那么若不删除第 $i+1$ 个字符则溢出减少一且备用增加一，所以 $dp[i+1][j-1][k+1]+=dp[i][j][k]$；
• 当第 $i+1$ 个字符为 ) 且 $j>0$，那么若不删除第 $i+1$ 个字符则溢出减少一，所以 $dp[i+1][j-1][k]+=dp[i][j][k]$；
• 当第 $i+1$ 个字符为 ) 且 $j=0,k>0$，那么若不删除第 $i+1$ 个字符则溢出增加一且备用减少一，所以 $dp[i+1][j+1][k-1]+=dp[i][j][k]$。

答案为 $\sum dp[n][0][k]$，其中 $k$ 为任意非负整数。

可以用滚动数组的技巧来将空间复杂度降低至 $O(n^2)$。

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