B The Game
从小到大排序之后,应当是 \(A\) 的后 \(m\) 个对应到 \(B\) 的后 \(m\) 个,记录 \(A\) 的后 \(m\) 个的总大小 \(sa\),\(B\) 的后 \(m\) 个的总大小 \(sb\),以及 \(A\) 比 \(B\) 多出来的数的个数 \(res\)。\(sb-sa=res\) 那么可以直接对应从小到大将 \(A\) 中的数依次修正为 \(B\),删的一定是前面 \(res\) 个。否则我们需要浪费次数,贪心,需要浪费时去操作 \(A\) 的最小值。
用俩 multiset 实现了一个对顶堆一样的玩意维护前 \(m\) 大。时间复杂度 \(\mathcal{O}(n\log n)\)。
C Master of Both IV
枚举 xor \(=x\),考虑它的真因子一定 \(\geq x/2\),无论怎么异或都搞不出 \(x\) 的最高位,所以一定有奇数个 \(x\),从而 \(x\) 的真因子 xor 和为 0。xor 为 0 的个数即为不在线性基里的元素个数,注意去重以及统计 \(x=0\) 的情况。
E Prefix Mahjong
考虑怎么 check,那就是按值域 \(f_{0/1/2,0/1/2,0/1}\) 表示前前位置开头有几个顺子,前一个位置开头有几个顺子,是否已经有雀头。转移是一个矩阵乘法,那么直接在值域上线段树维护矩阵乘法。因为是 01 矩阵所以可以压位,然后值域可以离散化到 1e5,这样复杂度就是 \(\mathcal{O}(n k^2\log n)\),其中 \(k=18\)。
G Hard Brackets Problem
首先发现无论怎么操作,光标的右侧永远是一堆 )
,只有光标右侧为空的时候才会插入一个 )
。所以合法当且仅当串是若干个合法括号序列中间拼上若干 )
构成的,分析到这里构造就很简单了。
H Sweet Sugar
一个连通块合法当且仅当 \(\sum\geq k\) 且与 \(k\) 同奇偶。和这个题一样证,\(w\) 合法那么 \(w-2\) 一定合法。所以贪心一下就行了。
I Barkley II
计算 cnt-mex 最大的区间。枚举 mex 是 \(x\),计算删去 mex 之后剩余的若干区间 cnt 最大是多少。这里虽然不能保证 mex 是 \(x\),首先答案一定能被统计到,其次算错的话真实 mex \(<x\),只会更劣,所以这么做是对的。