文章目录
有些好的题解就直接复制过来了，所以部分非作者所写题解
持续更新中…
Round1032(Div3)
F. Yamakasi （map前缀和+二分）
给你一个由整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 和两个整数 s 及 x 组成的数组。请计算元素之和等于 s 且最大值等于 x 的数组子段的数目。
更具体地说，计算 1 ≤ l ≤ r ≤ n 1 \leq l \leq r \leq n 1≤l≤r≤n 这样的数组对的个数：
a l + a l + 1 + … + a r = s . a_l + a_{l + 1} + \ldots + a_r = s . al+al+1+…+ar=s.
max ( a l , a l + 1 , … , a r ) = x . \max(a_l, a_{l + 1}, \ldots, a_r) = x . max(al,al+1,…,ar)=x.
如果没有最大值的约束，我们可以用 map 维护每个前缀和的出现次数，在遍历时累加每个位置上当前前缀和 s u m − s sum-s sum−s 在 map 中的出现次数。
多出最大值的约束后，还需要维护最后一个值大于 x x x 的位置 g x gx gx 和最后一个值为 x x x的位置 e x ex ex ， m a p map map需要数组维护每个前缀值每一次出现的位置。在遍历每个位置时计算前缀和为 s u m − s sum-s sum−s 中第一个大于等于 e x ex ex 的位置在数组中的下标和第一个大于等于 g x gx gx的位置在数组中的下标，对答案的贡献就是 e x − 1 − g x + 1 = e x − g x ex-1-gx+1 = ex-gx ex−1−gx+1=ex−gx， e x − 1 ex-1 ex−1的原因是我们一定是要取到 x x x的，所以向前移动一个的下标一定是小于 e x ex ex下标的。
G Gangsta（前缀和变种+树状数组）
H Ice Baby（最长上升子序列+线段树）
Round1033(Div2)
D Matrix game（容斥原理）
一、首先看行，使用最少的行一定能够取出a行一样的数字，由鸽巢原理可得，最少需要 n = ( a − 1 ) ∗ k + 1 n=(a-1)*k+1 n=(a−1)∗k+1行。
二、然后看列，这种情况思考的是：最多有多少种不同的列，这些列取出a个相同数字的方式不同，在这里，取出的数字不同或者取数字的位置不同即认为不同。对于任一数字 i ( 1 < = i < = k ) i(1<=i<=k) i(1<=i<=k)，均有 C ( n , a ) C(n,a) C(n,a)种不同的方式，所以一共有 k ∗ C ( n , a ) k*C(n,a) k∗C(n,a)种方式，将这些方式看成数字，再次使用鸽巢原理得， m = k ∗ C ( n , a ) ∗ ( b − 1 ) + 1 m=k*C(n,a)*(b-1)+1 m=k∗C(n,a)∗(b−1)+1。
实现时预处理阶乘逆元，计算 C ( n , a ) C(n,a) C(n,a)时使用 C ( n , a ) = A ( n , a ) / f [ a ] C(n,a)=A(n,a)/f[a] C(n,a)=A(n,a)/f[a]进行计算即可。
Round 1034 (Div. 3)
E.MEX Count
先统计出来子序列所有可能的MEX值，这个很明显就是整个数组的MEX值（cnt）。
然后贡献法计算，0-cnt 这些MEX值分别在 k属于哪个区间的时候可以取到，很明显每个MEX值可以让k取值为 [ s u m [ i ] , s u m [ i ] + s u m [ n ] − s u m [ i ] + s u m [ i − 1 ] − i ] [sum[i],sum[i]+sum[n]-sum[i]+sum[i-1]-i] [sum[i],sum[i]+sum[n]−sum[i]+sum[i−1]−i]的所有ans[k]+1，前缀和维护sum，然后差分维护一下答案即可
F. Minimize Fixed Points
题意：
构造一个长度为n的排列，对所有 2 < = i < = n 2<=i<=n 2<=i<=n的 p i p_i pi满足 g c d ( i , p i ) > = 2 gcd(i,p_i)>=2 gcd(i,pi)>=2，且要求 p i = = i p_i==i pi==i的值尽可能少。
考虑固定点的下界，所有满足 2 ∗ p > n 2*p>n 2∗p>n 的质数都必须成为固定点，现在构造方案使得达到下界。
质数的限制是比较大的，先考虑所有质数 p 和 2*p 构成一个环，可以使质数不成为固定点，现在考虑其他点，只需要加入最小因子所在的环就行，每个质数代表的环做一个轮换就行，用埃氏筛。
Round 1035 (Div. 2)
B. Line Segments（思维+多边形）
题意：平面上两个点，用 n n n 条线段连接，每个线段有 a i a_i ai的长度。求能不能恰好从起点连到终点。
其实就是给定 n + 1 n+1 n+1条边，是否能组成一个封闭多边形，注意成线的情况也是符合题意的。何时能组成一个多边形呢？显然只要除了最大边的其他边的和大于最大边即可，相等的情况成线，判断一下即可。
D. Token Removing（组合数+计数dp）
题意：长度为 n n n 的数组合法条件为对于所有 i i i属于 [ 1 , i ] [1,i] [1,i] , 0 < = a i < = i 0<=a_i<=i 0<=ai<=i。对于每个数组从前往后操作，如果 a i = 0 a_i=0 ai=0 不操作，否则在 [ a i , i ] [a_i,i] [ai,i]中选一个没有操作过的位置，数组的价值为有多少不同的操作序列。求所有合法数组的价值和。
重要的一点是需要想出来倒着 dp。记 f [ i ] [ j ] f[i][j] f[i][j]为 [ i , n ] [i,n] [i,n]操作了 j j j个位置的价值。那么如果 i i i不被 [ a i , i ] [a_i,i] [ai,i]某个位置操作，则 f [ i ] [ j ] + = f [ i + 1 ] [ j ] f[i][j]+=f[i+1][j] f[i][j]+=f[i+1][j]。
如果我们从 [ i , n ] [i,n] [i,n]中选一个位置 k k k操作 i i i，那么有 a k < = i a_k<=i ak<=i，因为已经有 j j j个位置被操作，所以一共有 n − ( i − 1 ) − j n-(i-1)-j n−(i−1)−j个位置可以选择，那么就是 f [ i ] [ j + 1 ] + = f [ i + 1 ] [ j ] ∗ i ∗ ( n − i + 1 − j ) f[i][j+1]+=f[i+1][j]*i*(n-i+1-j) f[i][j+1]+=f[i+1][j]∗i∗(n−i+1−j)。这样为什么能计算出正确的答案？我们可以想已经有一个后缀组成的序列，现在我们可以在一些位置插入 i i i，显然不同位置插入一个 i i i就是不同的方案。每个 a k a_k ak取值可以是 [ 1 , i ] [1,i] [1,i]，不同的 a k a_k ak其实对应不同的数组，而在每个数组中都有 ( n − i + 1 − j ) (n-i+1-j) (n−i+1−j)个位置插入 i i i 可以产生不同的方案。所以直接相乘就是价值。
Round 1036 (Div. 1+Div. 2)
B. Minimise Sum
C. Subset Multiplication（思维+gcd+lcm）
D.Make a Palindrome（区间第k小+回文串）
题意：给你一个数组，每次选择一个长度大于等于 k k k的子区间，然后删掉第 k k k小的数，如果有多少可以删任意一个。求能不能使得数组变成回文。
显然原数组第 1 1 1到 k − 1 k-1 k−1小不可能被删掉，假设得到了一个结果，那么我们可以把第 k k k小及比它大的都删掉，依然符合条件。那么我们把第 1 1 1到第 k k k小的位置拿出来，问题变为删掉一些第 k k k小的位置使得数组变成回文，注意数组长度最少为 k − 1 k-1 k−1。
这个可以通过双指针判断，先记录两侧第 k k k 小的数最多可以删除几个（因为可能有多个），然后把所有 > a k >a_k >ak的数删掉，最后判断左右两侧的数是否相同，如果相同就 l + + , r − − l++,r-- l++,r−−，否则就看左侧或右侧是否为 a k a_k ak，如果是，那我们可以删掉他看看接下来是否相同。注意删去的第 k k k小数是有限制的。
E.Make it Zero（思维+构造）
题意：将一个数组分为多个数组，满足所有数组的第 i i i位加起来等于原数组的第 i i i位，且这些数组需要满足存在某一位 i i i使 s u m [ i ] = s u m [ n ] − s u m [ i ] sum[i]=sum[n]-sum[i] sum[i]=sum[n]−sum[i]，即前后缀相等。
题解：至多两次就能实现，首先找到原数组第一个前缀 ( p r e i ) (pre_i) (prei)大于等于后缀 ( s u f i + 1 ) (suf_{i+1}) (sufi+1)的地方，如果该位置 p r e i = s u f i + 1 pre_i=suf_{i+1} prei=sufi+1，那么直接输出原数组即可，否则记录差值 d = ( p r e i − s u f i + 1 ) d=(pre_i-suf_{i+1}) d=(prei−sufi+1)，再构造一个新的数组，该数组后 [ i + 1 , n ] [i+1 ,n] [i+1,n] 位上全是0，且存在某个位置使得 p r e j = s u f j + 1 = d / 2 pre_j=suf_{j+1}=d/2 prej=sufj+1=d/2，那么结果就是新构造的数组与原数组减去这个新数组的值。