9
T4
个人难度：绿 下位
一眼并查集。
题目问题是如果某些人离开群后有多少人得不到消息，我们可以假设这些人在一开始时就离开，
然后再将查询反转，把问题转换成第 pip_ipi 个人加入第 cic_ici 个群后会有多少人收不到消息。这样就转换成简单的并查集问题了，只需要查询班长所在的集合有多少人即可。
注意特判（如样例二）的情况，就是班长没有加入任何一个群，这时得不到消息的人数为 n−1n-1n−1 而不是 nnn，因为班长是知道这个消息的。
时间复杂度：O((∑ki+m+q)logm+(q+∑ki)logn)O((\sum k_i+m+q)\log m+(q+\sum k_i)\log n)O((∑ki +m+q)logm+(q+∑ki )logn)（我也不知道啊，我乱写的）
T5
个人难度：黄 中位
首先打个正常的 DP，令 dp[i][j]dp[i][j]dp[i][j] 为到达第 iii 行第 jjj 列时宝藏价值最大值，则有
dp[i][j]=maxk=imdp[i−1][k]+a[i][j](k≠j)dp[i][j]=\max_{k=i}^{m} dp[i-1][k]+a[i][j](k\not= j) dp[i][j]=k=imaxm dp[i−1][k]+a[i][j](k=j)
如果暴力硬算，时间复杂度 O(n×m2)O(n\times m^2)O(n×m2)。
注意到这个 max 可以分成左右两部分，即
dp[i][j]=max(maxk=1i−1dp[i−1][k], maxk=i+1mdp[i−1][k])+a[i][j]dp[i][j]=\max(\max_{k=1}^{i-1} dp[i-1][k],\space\space\max_{k=i+1}^m dp[i-1][k])+a[i][j] dp[i][j]=max(k=1maxi−1 dp[i−1][k], k=i+1maxm dp[i−1][k])+a[i][j]
我们可以使用线段树来求出区间和。
注意使用滚动数组，否则会 MLE；还要特判 m=1m=1m=1 的情况。
时间复杂度：O(n×mlogm)O(n\times m\log m)O(n×mlogm)。
什么？你说直接记录前缀最大值和后缀最大值也能过？没错，赛时我唐了。
T6
个人难度：绿 上位
本题是道大模拟题，我将使用分类讨论的思路讲解。为方便表示时间复杂度，我们令 nnn 为数字个数，即 n=4n=4n=4。
注意到题目只需要我们凑出 242424 的倍数，所以除法是个诈骗，可以不用管。
于是我们可以把构造结果分成 555 种情况，分别判断。
1. a×b×c×da\times b\times c\times da×b×c×d。
模拟难度：红 中位
显然，只有一种情况，直接判断、输出即可。注意乘法取模。
时间复杂度：O(n)O(n)O(n) 。
2. a±b×c×da\pm b\times c\times da±b×c×d。
模拟难度：红 上位
我们可以选择一个数作为 aaa，剩下三个数就作为 b,c,db,c,db,c,d。
时间复杂度：O(n2)O(n^2)O(n2)。
3. a±b±c±da\pm b\pm c\pm da±b±c±d 。
模拟难度：橙 上位
ai,bi,ci,dia_i,b_i,c_i,d_iai ,bi ,ci ,di 都有两种选择情况：正，负。
所以我们可以爆搜一波，如果有可能的结果，就对应输出。
注意，第一个数不能为负，所以如果 ai<0a_i\lt 0ai <0，需要找一个大于 000 的数代替 aia_iai 。
时间复杂度：O(2n)O(2^n)O(2n) 。
4. (a±b)×(c±d)(a\pm b)\times(c\pm d)(a±b)×(c±d)。
模拟难度：橙 上位
我们先选好配对的两个数，再和第三种情况一样，爆搜四个数的状态，最后输出即可。
时间复杂度：O(n×2n)O(n\times 2^n)O(n×2n)。
5. a×(b±c±da\times (b\pm c\pm da×(b±c±d 。
模拟难度：黄 中位
这里的右括号可以加在任何地方，如 a×(b)±c±d,a×(b±c)±d,a×(b±c±d)a\times (b)\pm c\pm d,a\times (b\pm c)\pm d,a\times(b\pm c\pm d)a×(b)±c±d,a×(b±c)±d,a×(b±c±d) 。
我们先挑选 aaa，即乘数，然后搜索每个数的 444 个状态。假设现在要枚举状态的数为 kkk，则 444 种状态的结果如下：
1. kkk，这是 kkk 在括号外面，并且符号为正的结果。
2. −k-k−k，这是 kkk 在括号外面，并且符号为负的结果。
3. a×ka\times ka×k，这是 kkk 在括号里面，并且符号为正的结果。
4. −a×k-a\times k−a×k，这是 kkk 在括号里面，并且符号为负的结果。
接着，我们把所有在括号内和在括号外的数分别进行组合、输出。
时间复杂度：O(n×4n)O(n\times 4^n)O(n×4n)。
卧槽类似我了 谁抄我题解我 [数据删除]
来补个赞
有帮助，赞一个