随便收集

E. Xor Tree
Solution:
这种找异或和最小对的问题，可以直接想到用01Trie，我们首先保留所有的数，看看Trie数的结构，我们可以发现如果有两个数他们之前如果有高位是相同的，说明他们互相之间能够异或和最小的就是彼此之间，也就是这两个数之间会形成环，我们如果要让这个数组为Good，就不能出现环，所以我们要删去其中一个数，而题目需要我们删去越少越好，因此这个便转为Trie树上dp问题，我们只有在有分叉点的时候才能做选择，定义 $f[u]$ 为对于 $u$ 点的子树而言至少需要删去多少点 这样的状态即可。

#665. 数组划分
Solution:
按与运算找最大值，一般可以从高位开始枚举，高位大，数就能大。
我们从高位开始枚举，可以尝试一下该位置 1 ，然后对其进行 dp ，也既：能否将数组正好划分成 $k$ 段，使这个结果经过划分之后的与运算仍能保留下来。我们设 $dp[i][j]$ 为枚举到第 $i$ 个数，划分了 $j$ 个区间，这很显然就是一个可行性 dp ，也即如果枚举到一段区间和与运算之后仍能保留结果，才能够状态转移。如果经过 dp ，之后仍无法保留原答案，说明该位不能置 1 。

选数2
Solution:
这是一个挖掘（猜）贪心性质的题目。
我们将题意的条件转化为数学公式，可以得到：
$$ q \cdot m \cdot max \leq p \cdot sum $$
首先因为选数与顺序无关，我们可以对这个数组进行排序，尽可能地让题目更好做，当然还要保留他们原来的下标。

我们要让 $m$ 尽量地大，首先如果我们已经知道了这个 $m$ ，并且对 $max$ 固定，我们可以发现上述的不等式的左边是不变的，这时候我们就要让 $sum$ 尽可能大，那么只要这 $m$ 个数是连续的即可，因此可以通过二分来找这个 $m$ 。

我们要找不可能被选上的数，那么在得到这个 $m$ 之后，我们可以枚举所有长度为 $m$ 的连续区间，这时候我们可以发现最大值总是在这个区间的最右端，因此上述的不等式的左边仍然是固定的。这时候我们就要找 $sum$ 最小的满足的解，我们只要通过二分找左端点以及左边的所有点，最小能够代替左端点还能满足条件的点即可，此时新的左端点和右端点之间的所有数都是有可能被选上的，这时候我们可以用差分标记那些可能被选上的数的区间，在最后找不可能被选上的数的时候直接对差分前缀和，然后取下那些前缀和为0的数即可。

#614. “Z”型矩阵:
Solution:
严格鸽的题解

#611. 拆拆
Solution:
我们首先对 x 进行质因子分解，然后这 k 个数里面只要总共 k 个数的乘积的质因子等于 x 的质因子即可。我们可以把这些质因子分别分配给这 k 个数，也即将这些质因子“球” 放入这 k 个“盒子”里面。这就是一个经典的组合数学模型。然后控制负号个数，分配偶数个负号即可，也即$\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + …$，这个可以计算得 $2^{n-1}$，然后根据乘法原理即可。

#131. 最大公约数
Solution:
如果要分成 k 段，假设公约数是 g ，那么可以知道这个数组的总和只能是 g 的倍数，我们计算可以得知总和最多为$1\times 10^{11}$，我们可以通过试除法枚举这个数的所有因子，来计算这个因子最多可以让数组划分为多少组，并将答案存入map中取最大即可。

D. For Gamers. By Gamers.
Solution:
很显然这只需要贪心雇佣一种unit就行（怪会同时攻击所有人），而且题目中是连续攻击不是离散攻击，所以如果要胜利，就假设雇佣 $i$ 品种的数量为 $x$ ，这样对于第 $j$ 只怪，就可以列出等式 $\frac{H_j}{xd_i} = \frac{h_i}{D_j}$，转换可得 $D_jH_j < xd_ih_i$，而 $x$ 个 unit 的价格为 $xc$ ，所以我们只要找最小的 $xc$ 即可 ，这时候我们可以对价格作为下标，输入完 $n$ 个 unit 的信息之后，预处理出所有价格及其倍数的最高$d_ih_i$，然后再对 $m$ 只怪二分找到最小的合法解即可。

D. Closest Equals
Solution:
离线处理，对询问先按右端点排序，再按左端点排序，枚举到某个线段的右端点就修改左端点，之后更新右端点，再查询这个询问的区间内最短的线段，也就是最小值。带修查询线段树即可。

D. Integral Array
Solution:
对出现过的数字记录权值，并对权值进行前缀和，然后从左到右枚举 1 到 m ，如果出现了某个数，那么就要检查他的倍数以及倍数加上剩余量，如果其数存在而其商不存在，说明不合法。

C. XOR Inverse
Solution1:
对于两个数，我们都可以直接从最高位开始比较，如果有一位不相等，那么他们之间的大小关系基本确定，后面的位对他们的大小关系基本就没有什么作用了。这时候我们可以建二进制01Trie，每个节点上储存有什么下标的值经过这个节点，我们在计算的时候如果遇到有左右儿子，就可以计算以当前节点为高位时01变换与否的逆序对数，最后计算的时候取最小值，决定该位置1与否即可。$O(30n)$，缺点是费空间。

Solution2:
总体思想和上面的做法基本相同，不同的是由于题目数据约束可以用 $O(30nlogn)$的做法，也就是每次考虑一位的时候排序一次。相比上一个做法，好处是省空间。

函数求和
Solution:
首先考虑 $a_1$ ，假设 $a_1=0100101$，如果我们要让其受到改变，那么在与运算中，让其改变只能是将某一位的 1 改成 0 ，也即先找到可以让其置 0 的地方，找到有 x 个这样的位置之后，就是要让这 x 个位置至少置一个 0 ，所以贡献是 $2^x-1$ ；而 0 位不管放什么，经过与运算都不会改变，找到 y 个 0 位之后，就是随便放，所以贡献是 $2^y$ 。如果有能置 1 的位，才能加上贡献 $i * (2^x-1) * 2^y$。计算完之后为了后续不会再有能使 $f(x)=i$ 的，我们要将那些 1 位封印，就是这几个原来的 1 位到后面始终是 1 ，才始终不会让 a1 改变，如此继续往下枚举即可。

摘桃子
Solution:
首先要知道的是不可能出现长度大于等于 k 的方案，因为这样的区间的总和取模之后的和一定小于 k 。
考虑对其进行前缀和处理，那么即可转化为有多少个 $(i, j), i < j$ 使得 $(sum[j] - sum[i]) \% k = j - i \Rightarrow (sum[j] - j) \% k = (sum[i] - i) \% k$ ，这时候只要滑窗保证长度小于 k 即可。

B. Game of Ball Passing
Solution:
结论题。我们要找出数组中最大的数，并计算这个数组的总和，这时候可以分成两部分：最大的数和除了最大的数之外的总和，如果 $max <= sum - max$ ，那么 $sum - max$ 内部可以自己相互传球，消耗到跟 $max$ 相等，再把球传给 $max$ ，这样就只需要一个球了；如果 $max > sum - max$ 那么只能让 $max$ 先传球给另一部分的人，然后往后的球只能“自娱自乐” 。

G. MinOr Tree
Solution:
按位贪心，从高位开始。我们对所有边权，只要边权在第 i 位上为 0 ，我们就尝试用这个边建一个生成树，如果发现这些边真的可以挑选 n - 1 个边来让其成为一个生成树，那么接下来就将那些第 i 位为 1 的边权的边删掉，然后再往下一位考虑即可。

D. Nearest Excluded Points
Solution:
首先要找到那些可以直接确定答案的点，也即能一步到位的那些点，那些不能直接确定的点，可以当他走到已经确定答案的点的时候，答案就确定为走到的点的答案了，我们可以对多个直接确定答案的点进行多源BFS，走到那些不能直接确定的点，给予最短路答案，可以证明点数不会超过 $5N$ 。

D2. Half of Same
Solution:
数据量很小，所以考虑暴力即可。
将这 n 个数字分别作为中心，求出其他数减去中心的差，如果 0 有过半数，那么答案即为任意数，也即-1。否则在每个差中求出他的因数，并从大到小枚举这些因子，如果找到一个因子使其能让过半数相等，即为所求。

F2. 生活在树上（hard version）
Solution:
此问题可以转化为：对于询问 $x, y, k$ ，在 $x, y$ 上是否存在一个点 $t$，使其$s[x] \oplus s[y] \oplus a[t] \oplus a[lca(x, y)] = k$。那么这就是一个树上差分的问题，要求出每个询问上是否有满足询问的点，考虑离线LCA，对每个询问都在树上的节点打上标记，就是求 $x$ 到 $lca(x, y)$ 与 $y$ 到 $fa(lca(x, y))$，有多少个点满足要求，我们只要用一个全局桶记录每个数值的个数，计算出路径上有多少个点满足 $s[x] \oplus s[y] \oplus a[t] \oplus a[lca(x, y)] = k$，既求有多少个 $w = s[x] \oplus s[y] \oplus a[lca(x, y)] \oplus k$ 即可。

559. 树上逆序对
Solution:
暴力的方法一般是先枚举节点再枚举 k 叉树，一点一点将贡献加入进 k 叉树的结果中，此法时间复杂度 $O(n^2)$，有很大的进步空间。
可能会想到用主席树来解决，也即枚举父节点，然后再枚举 k 叉树，在 k 叉树中以某父节点的子节点的编号是连续的且可以确定的，这样问题就转换成了对每个节点，在k叉树的时候他的子节点能做多少贡献，也就是在子节点l~r中，有多少个值是小于其父节点的。但此题还是卡了这个做法的时间，还更需要优化。
我们可以对 n 个数从小到大进行稳点排序，我们开一个树状数组，记录枚举到某个点的时候已经出现过的权值，我们从权值小的原序最前的点开始枚举，这样就能够保证子节点对父节点的贡献是完全做足的。

F. Fibonacci Additions
Solution:
这种区间加减的问题，一般考虑差分，如果两个数列相等，那么这两个数列的各位元素之差应为0，所以我们考虑开数组CD，C[i] = A[i] - B[i]，D[i] = C[i] - C[i - 1] - C[i - 2]。因为题目只问会不会全部相等，所以只考虑有和没有，也就是可以直接对差分数组考虑，既等价于差分数组是否全为0即可。此题需要用到的是斐波那契数列的差分数组性质，要注意怎么修改。