目录
1322B - Present
$4e5$ 个数，问两两求和后的异或和。
可以按位考虑，考虑第 $k$ 位时给数字模 $2^{k+1}$ ，这样第 $k$ 位为 $1$ 和只可能在 $[2^k,2^{k+1}-1],[2^{k+1}+2^k,2^{k+2}-2]$ 区间，对于每个数lower_bound找位置就好。
1322C - Instant Noodles
二分图，右边的点每个有一个点权，对于左边点的集合 $S$ ， $N(S)$ 是所有与集合中点邻接的点， $f(S)$ 是 $N(S)$ 的点权之和。问对与所有非空集合 $S$ ， $f(S)$ 的 $\gcd$ 。
如果某些右边的点邻接的点完全相同，则缩点，将权值定为它们的和，去除度数零的点，此时所有点权的 $\gcd$ 即答案。
证明：设此时的 $\gcd$ 为 $g$ ，全集 $U$ 。给所有 $c_i$ 除以 $g$ 。若答案为 $k\times g(k > 1)$ ，则 $k\mid f(U_L)$ 。而必定存在 $k\nmid c_j$ （因为 $\gcd$ 已除），取度数最小的这样的 $j$ ，取集合 $S'$ 为左边所有不与 $j$ 相邻的点，则 $N(S')$ 仅不包含 $j$ 与邻接点是 $j$ 的子集的点，所有右边点的点权和被 $k$ 整除，而这些点的点权和不被 $k$ 整除，可以推出 $k\nmid f(S')$ 。矛盾，故不存在这样的 $k$ 。
写法参考了别人的题解，第一次用iota还有vector比较大小什么的，很神秘。
1322D - Reality Show
$n$ 个观众每个观众有攻击力 $l_i$ ，邀请他花费 $s_i$ ，并直接获得 $c_{l_i}$ 的收益。当现有的两个观众攻击力相同，他们中一个会消失另一个攻击力变 $l_i+1$ 并获得新的收益 $c_{l_i+1}$ （这个过程会不断进行直到选择的观众互不相同）。所选观众的攻击力要求是不上升的，最大化利润。
注意到观众打架消除的过程像二进制加法的进位，处理观众的顺序其实是不影响最终的获利的。由于进位是向高位进的，翻转序列搞一个不下降序列比较容易。我们可以用 $f[l_i][k]$ 表示当前选择的最大攻击力为 $l_i$ ，且 $l_i$ 有 $k$ 个时的最大获利，则 $f[l_i][k]$ 可以向 $f[l_i+1][k/2]$ 转移（因为每次都除二复杂度是可接受的）。
1325E - Ehab's REAL Number Theory Problem
$n$ 个因子不超过 $7$ 个的数 $a_i$ 。问最少选多少个乘积会是完全平方数。
首先如果某个数字能被完全平方数整除就除掉它，不影响结果。之后由于因子不超过 $7$ 个，所有 $a_i$ 的质因子数不会多于 $2$ 个。如果有 $1$ 就直接选它结束，否则其余数字将会是 $p$ 或 $p·q$ 的形式，前者给 $1,p$ 连边，后者给 $p,q$ 连边，问题就转化成无向图找最小环。找环我们直接bfs，由于每条边意味着两个顶点的数字相乘，最小环中必包含一个不大于 $\sqrt{\max_{a_i}}$ 的点，仅枚举这些点作为起点即可。
1325F - Ehab's Last Theorem
给无重边自环的 $n$ 个节点的无向图，要求构造至少 $\lceil\sqrt{n}\rceil$ 个节点的简单环，或 $\lceil\sqrt{n}\rceil$ 个节点的独立集。
dfs树上每个非树边 $(u,v)$ 都代表了一个大小为 $|\mathrm{dep}_u-\mathrm{dep}_v|+1$ 的环（dfs树的一个性质是所有非树边连接一个点与它的某个祖先）。搞一个栈记录一下节点，如果环的大小满足 $\lceil\sqrt{n}\rceil$ ，选择方案2直接输出。
而如果不存在 $|\mathrm{dep}_u-\mathrm{dep}_v|+1\ge\lceil\sqrt{n}\rceil$ ，则鸽巢原理说明每个点最多连出 $\lceil\sqrt{n}\rceil-2$ 条非树边，最多限制 $\lceil\sqrt{n}\rceil-1$ 个点不可取，所以必能得到 $\lceil\sqrt{n}\rceil$ 大小独立集。从dfs树的叶子节点往上取即可。
1326E - Bombs
给出长度为 $n$ 的两个排列 $p,q$ ，按照顺序从 $1$ 到 $n$ ，把 $p_i$ 加入集合，如果位置 $i$ 有炸弹则从集合中取出一个最大值，结果是最后集合中的最大值。第 $i$ 个答案回答的是 $q_1,q_2,\ldots q_{i-1}$ 处有炸弹时的结果。
一个比较厉害的转换思维。我们观察到答案是单调不上升的，如果答案至多为 $x$ ，我们就需要让 $x+1,x+2,\ldots,n$ 都被炸掉，条件就是对于每个位置右边大于 $x$ 的 $p_i$ 的数量都不多于右边的炸弹数量。可以线段树维护 $右面不小于当前答案的p_i的数量-右面炸弹数量$ ，如果小于等于 $ 0 $ 则减小当前答案。
