ABC 450 差 1s AK，气急败坏的我顺手 AK ABC 451。
题号 个人难度 tag（个人做法） AC time A 红 字符串 2'19'' B 红 STL 4'24'' C 橙 STL 10'23'' D 黄 枚举、BFS 22'33'' E 绿 MST、BFS 34'07'' F 蓝 带权 DSU 50'54'' G 紫 01 Trie、线性基 85'19''
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A. ILLEGAL
使用 string 类的 size() 函数或者 length() 函数判断是否为 555 的倍数即可。
B. PERSONNEL CHANGE
用一个桶记录两个学期每个社团的人数，然后相减即可。
C. UNDERSTORY
看到操作容易想到 multiset，它不会自动去重，而且自动排序，因此每次删除操作时只需要使用 upper_bound() 找大于 hhh 的第一个数，erase() 区间删除即可。
D. CONCAT POWER OF 2
由于 log109≈30\log 10^9 \approx 30log109≈30，所以可以从每个 222 的幂出发，使用 BFS 暴力生成所有拼接数，用 set 去重，最后将集合中的数排序即可。
E. TREE DISTANCE
由于是稠密图，所以我们使用 Prim。以 ai,ja_{i,j}ai,j 为边权构建最小生成树。在 MST 上跑所有点对的最短路，与输入矩阵比较即可。
F. MAKE BIPARTITE 3
用带权 DSU 维护每个连通分量内的颜色关系。每个分量根节点维护 cntrt,0cnt_{rt,0}cntrt,0 和 cntrt,1cnt_{rt,1}cntrt,1 分别表示与根同色和异色的顶点数。当加边时：
* 若 u,vu,vu,v 已在同一分量，检查边是否异色，若为 000 则出现奇环，不可行。
* 否则合并两个分量，根据 u,vu,vu,v 的颜色关系计算需要翻转其中一个分量的颜色，更新合并后的计数和最小黑点数。
G. MINIMUM XOR WALK
油 奠 以 死
完成了 异或粽子 和 线性基 以后，你就会发现他其实就是这俩玩意的结合。没做过先别着急做，看我操作。
这种典题有一些经典步骤：
* 固定一棵生成树，任意两点间的异或 walk 最小值为 basex⊕basey\operatorname{base}_x \oplus \operatorname{base}_ybasex ⊕basey 与所有环的线性基组合得到的最小值。
* 所有环的异或值构成一个线性基 B\operatorname{B}B，则任意两点间的最小异或值等于 mins∈span(B)(basex⊕basey⊕s)\min_{s \in \operatorname{span(B)}} \bigl( \operatorname{base}_x \oplus \operatorname{base}_y \oplus s \bigr)mins∈span(B) (basex ⊕basey ⊕s)，即 basex⊕basey\operatorname{base}_x \oplus \operatorname{base}_ybasex
⊕basey 在子空间 span(B)\operatorname{span(B)}span(B) 中的最小表示。
* 通过线性基可以将所有 base 向量化简为代表元，使得之间两两的异或值就是原图两点间的最小异或值。
容易将问题转化为：有多少对 i,j (i<j)i,j\ (i<j)i,j (i<j) 满足 ai⊕aj≤ka_i \oplus a_j \leq kai ⊕aj ≤k。那就经典了：
* 建一棵 303030 位 01 Trie，插入时统计。
* 对每个代表元，在 Trie 中查询与它异或值 ≤k\leq k≤k 的数的个数（这一步貌似是经典数位 DP 查询）。
* 注意去重，可以在插入前先查询，再插入当前数。
