2023牛客暑期多校训练营5
A - Jujubesister
B - Circle of Mistery
C - Cheeeeen the Cute Cat
题意：给定一个稠密二分图，满足 $1 \sim n,n+1 \sim 2n$ 之间两两不相连，$i,j+n$ 相连 $\Leftrightarrow i+n,j$ 不相连，$i,i+n$ 不相连，求原图的最大匹配
大胆猜结论，当有点没有出度时答案为 $n-1$，否则答案为 $n$，可以通过
D - Cirno's Perfect Equation Class
题意：给定 $k,c,n$，求满足 $ka+b=c,a \geq 0, b \geq 0,b \vert c,gcd(a,b) \geq n$ 的 $(a,b)$ 对数
本来以为是 exgcd，结果注意到 $b \vert c$，所以可以直接枚举 $c$ 的因数暴力判断，复杂度 $O(q\sqrt{c}\log c)$
E - Red and Blue and Green
题意：给定一些相互包含/相离的区间，要求每个区间的逆序对个数为奇数/偶数，求一个满足条件的排列
由于区间都是相包含/相离的，所以我们可以将所有长度为 $1$ 的区间加上之后将所有的需求建成一棵树，每次要完成一个区间，要么就是所有子区间直接拼起来，要么就是需要其中一些区间中的值交换一下，使得区间的逆序对数奇偶性反转后满足条件。一个很容易想到的构造方案就是选择任意两个相邻的直接子区间，交换前一个的最大值和后一个的最小值，这样得到的排列逆序对数正好增加 $1$，最后得到的就是合法的答案。注意可能存在矛盾的条件，只有这种时候需要输出 $-1$。复杂度 $O(n^2)$，可以通过
F - NoCruelty
G - Go to Play Maimai DX
题意：给定一个数列，值域为 $1 \sim 4$，求最小的包含所有四种数并且包含至少 $4$ 个 $4$ 的区间长度
签到题，双指针或二分均可，复杂度 $O(n) \sim O(n\log n)$，可以通过
H - Nazrin the Greeeeeedy Mouse
题意：有 $n$ 个物品和 $m$ 个容量不同的背包，背包的容量递减，每个背包可以选择一段连续区间的部分物品装入，不同背包对应的区间不能相交，求能得到物品最大权值和
有一个很明显的 dp：$dp_{i,j}$ 表示前 $i$ 轮选择了 $[1,j]$ 区间内的部分物品得到的最大权值和，之后就是一个简单的一维区间 dp 转移了，每个区间的价值可以事先用背包 dp 求出，复杂度 $O(mn^2+n^3)$
场上我们就卡在了这里，其实有一个很显然的结论：需要的背包个数 $\leq n$，因为每个物品最多用一个背包装，所以只用取最后 $n$ 轮的背包跑即可，时间复杂度 $O(n^3)$，可以通过
~~事后看别人代码才想到，悔死。。。~~
I - The Yakumo Family
题意：给定序列 $a$，求 $\sum\limits_{1 \leq l_1 \leq r_1< l_2 \leq r_2 < l_3 \leq r_3 \leq n} XOR(l_1,r_1) \cdot XOR(l_2,r_2) \cdot XOR(l_3,r_3)$，其中 $XOR(l,r)=\bigoplus\limits_{i=l}^r a_i$
首先很明显可以将区间异或和改为点对异或和，由于异或的线性性，我们可以将原问题拆解为 $$\begin{align} &\sum\limits_{1 \leq l_3 \leq r_3 \leq n} XOR(l_3,r_3)\sum\limits_{1 \leq l_2 \leq r_2<l_3}XOR(l_2,r_2)\sum\limits_{1 \leq l_1 \leq r_1 <l_2} XOR(l_1,r_1)\ =&\sum\limits_{0 \leq l_3 < r_3 \leq n} (pre_{r_3} \oplus pre_{l_3})\sum\limits_{0 \leq l_2 < r_2 \leq l_3} (pre_{r_2} \oplus pre_{l_2})\sum\limits_{0 \leq l_1 < r_1 \leq l_2} (pre_{r_1} \oplus pre_{l_1})\ =&\sum\limits_{0 \leq l_3 < r_3 \leq n}\sum\limits_k(pre_{r_3}[k] \oplus pre_{l_3}[k])2^k\sum\limits_{0 \leq l_2 < r_2 \leq l_3}\sum\limits_k(pre_{r_2}[k] \oplus pre_{l_2}[k])2^k\sum\limits_{0 \leq l_1 < r_1 \leq l_2}\sum\limits_k(pre_{r_1}[k] \oplus pre_{l_1}[k])2^k \end{align}$$ 其中 $a[k]$ 表示数 $a$ 在二进制表示中第 $k$ 位上的数
而这样的问题可以转化为重复三遍一个更小的子问题：对所有 $i$ 求解 $val_i=\sum\limits_{r=1}^i\sum\limits_{l=0}^{r-1}\sum\limits_k (pre_l[k] \oplus pre_r[k]) * 2^k * preval_l, preval_i=\max(preval_{i-1},val_i)$，这样只需要一个简单的前缀和即可，复杂度 $O(n\sqrt V)$，可以通过