非传统题练习（自用）
∗ * ∗：重点 ^：难点
题单：https://vjudge.net/contest/645884#overview
A - Hamilton
我们将 ( p i , p i + 1 ) ( p_i,p_{i+1}) (pi,pi+1) 看作一条从 p i p_i pi 到 p i + 1 p_{i+1} pi+1 颜色为 C i , i + 1 C{i,i+1} Ci,i+1 的边。
那么最后的图就是一条白色的链和一条黑色的链组成的环。
使用增量法，逐个加边。
若当前的环为纯色，则当前边加到哪都行。
否则将边加到黑链与白链交界的地方。
B - GCD Queries
维护两个位置 a=1,b=2，从 3 开始遍历；
设 x = gcd ( p a , p i ) x=\text{gcd}(p_a,p_i) x=gcd(pa,pi), y = gcd ( p b , p i ) y=\text{gcd}(p_b,p_i) y=gcd(pb,pi)
若 x = y x=y x=y 说明 i 不为 0
若 x < y x<y x<y 说明 a 不为 0
若 x > y x>y x>y 说明 b 不为 0
如果 a/b 不为 0，就将 a/b 赋值为 i 。
这样操作 2n 次，排除 n − 2 n-2 n−2 个数，最后剩下两个数。
C - 传 Mapa
n 个点值可以确定一个唯一的 n − 1 n-1 n−1 次的多项式，而这一点再 % p \%p %p 意义下任然成立，所以我们确定多项式后把多项式的系数传过去即可，而每个系数需要用到 30bits
D - 想法 *^
n 个 [ 0 , 1 ] [0,1] [0,1] 的随机值的最小值期望为 1 n + 1 \frac{1}{n+1} n+11，设 m m m 为最小值，则 n n n 大概为 1 m − 1 \frac{1}{m}-1 m1−1。
我们给每道题赋一个 [ 0 , 1 ] [0,1] [0,1] 的值，递推求出每道题的最小值，然后用上面的式子反推出 n n n，多跑几次，取个平均值就行了。
E - Secure Password
对于每个位置我们赋予一个 13 位，恰好 6 个 1 的二进制数，这样就可以保证二进制表示下没有包含关系，然后对每一位询问所有这一位为 1 的二进制数对应的位置。
可以发现某个二进制数 x 对应位置的答案就是所有 x 为 0 的位的询问结果的按位或。
F - Sanae and Giant Robot
设 c i = a i − b i c_i=a_i-b_i ci=ai−bi，s 为 c 的前缀和。
若 s l − 1 = = s r s_{l-1}==s_r sl−1==sr 我们就可以操作这一段，操作完后 s L R s_{L~R} sL R 就会变为 s r s_r sr。我们发现只需要对 s r = 0 s_r=0 sr=0 的区间做操作。
把区间保存在端点。从所有 0 的位置开始 bfs 扩展，修改用并
查集快速处理区间推平即可，复杂度 O ( n l o g n ) O(n~log~n) O(n log n)。
G - 8 染色G - 8 染色
首先可以发现我们可以把 （1,2） 当成一种颜色，因为我们拿到每个
颜色后可以手动二染色一下，这样一个点只用发 2bit。
其次可以发现度数 <8 的点完全不用考虑，因为最后再决定一个邻居没有用过的颜色即可，而这样的点数只有 2 m 8 \frac{2m}{8} 82m 个。
策略拼在一起就能做到 个 m 2 \frac{m}{2} 2m bit。