566E

• 对于一对相邻的点 $(x,y)$，它们其它的相邻点之间的交集就是 $\{x,y\}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的（出现的点如果不相邻那么它们路径上的也应该在交集中）。
• 这样可以求出所有非叶子节点之间的连边，剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。
• 这样非叶子节点数量 $\leq 2$。如果没有非叶子节点则 $n=2$，特判；如果只有一个非叶节点，那么所有集合都是 $\{1,2,\cdots,n\}$；如果只有两个可以先用上面的方法找出两个非叶节点，但是不能用上面的方法判，叶子节点只会有两种不同的集合，一种接到一个点即可。
• 用 bitset 优化，时间复杂度 $O(\frac{n^3}w)$。

1637G

• 倒过来考虑，要把两个数 $x,y$ 变为 $\frac{x+y}2,\frac{x-y}2$。可以发现如果它们都是奇质数 $p$ 的倍数变化后还是 $p$ 的倍数，就不可能还原成 $1,2,\cdots,n$ 了。
• 说明最后的结果一定是 $2$ 的幂，则最小的是满足 $2^k\geq n$ 的最小整数。通过构造证明可以取到。
• 可以先把所有数都变成 $2^x(x\leq k)$ 的形式，再造出一个 0 然后再处理（$(0,x)\rightarrow (x,x)\rightarrow (0,2x)$）。
• 先找到 $2^t\lt n$ 最大的 $t$，对于 $[2^t+1,n]$ 的数和它们关于 $2^k$ 对称的位置先做一次操作，会变成一大堆 $2^k$ 和 $2,4,6,8,\cdots$，也可以看作是一个前缀，递归下去两个剩下的前缀即可，次数是一个 log 级别的。

1530G

• 先找不变量，发现 1 的个数不变，且操作可逆。
• 设 1 的个数为 $t$，$k=0,k=t,k>t$ 先特判。
• 下面讨论 $0\lt k\lt t$，由于可逆所以可以把 $s,t$ 变成相同的字符串。
• 看相邻两个 1 之间 0 的个数 $d_i$，如果 reverse 的两端都是 1 那么就是把中间的 $d$ 翻过来。
• 对于一般的 reverse，不仅把中间的翻过来，且对于左右两边，可以给 $d_i+=x,d_{i+k}-=x$，$x\in [-d_i,d_{i+k}]$，就是带上若干个 0。对每个 $i$ 取 $j=d_{i+k}$ 把 $d_{k+1},d_{k+2},\cdots,d_t$ 归零。
• 对于 $k$ 是奇数，剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=d_{k+1}$。这样会隔一个清一个，而由于 $k$ 是奇数最后会把所有都清了，只剩下第一个位置，次数是 $2k+(m-k)\lt 2n$。
• 对于 $k$ 是偶数，无论怎样翻转奇数位还在奇数位置上，偶数同理，所以可以再判断 $s,t$ 奇数位之和是否相同。剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=-d_1$。这样清的位置是一个前缀或后缀，且会不停地翻，只剩下第一个和最后一个位置，次数是 $k+(m-k)\lt 2n$。且两个位置奇偶性不同，故只要满足之前的条件就一定可以。

804E

• 有一个经典结论，排列交换相邻两个位置逆序对恰好变化 1，而交换距离为 $d$ 的可以等价于交换相邻的 $d+(d-1)$ 次，所以逆序对奇偶性一定会改变，故交换次数是奇数时一定不会和原序列相同。
• $n\bmod 4=2,n\bmod 4=3$ 时交换次数为奇数，故无解。
• $n\bmod 4=0$，可以 4 个分一组，然后就是组内要两两交换一次，两个组间要两两交换一次。最好的情况是组内和组间的做完都不变。组内的交换一种方案为 $(1,2),(3,4),(1,3),(2,4),(1,4),(2,3)$。两组之间，考虑把每组再分成两部分，两组的一部分之间容易构造出两边都翻转的方案 $(1_a,1_b),(2_a,2_b),(1_a,2_b),(2_a,1_b)$，那么两组每一部分都做一次就可以归位。
• $n\bmod 4=1$，此时多了一个数，考虑在 $(2i,2i+1)$ 交换的时候多加入和 $n$ 的交换，以 $(1,2)$ 为例，把原先的 $(1,2)$ 改成 $(1,n),(1,2),(2,n)$，就可以了。

923F

• 发现某棵树是菊花图一定无解，中心没法分配标号。此外 $n\leq 5$ 的都有解，可以暴力求出，其它的递归考虑。
• 如果当前某棵树有点删掉后就会使得树变成菊花图，设这个点为 $u$，它父亲是 $v$，它父亲的父亲（菊花中心）为 $w$。为了使得另一棵树不能有其它点和 $w$ 连边，就从另一棵树选个叶子节点 $w'$ 与 $w$ 对应，$w'$ 父亲 $u'$ 就与 $u$ 对应。那么 $v'$ 就不能和 $u'$ 相邻，由于不是菊花图，所以一定存在 $v'$。而菊花图的限制只是除了 $u$ 的所有点都不能和 $w$ 相邻，$u$ 和 $v$ 不能相邻，所以剩下的可以随意分配。
• 否则，两棵树都删除两个距离 >2 的叶子使得不是菊花图，递归即可。

833E

• 先离散化然后讨论。
• 如果一个位置覆盖了超过两个，这个位置就一定不会被照到。
• 如果一个位置覆盖了正好两个，想要照到就必须让两个都消失。
• 如果一个位置覆盖了恰好一个，若相交的有覆盖恰好两个的那么之前一定算到了，如果没有则说明相交部分没有贡献，可以都当作没有相交的来算，数据结构维护即可。

1060H

• 它没有两个未知数的乘法操作，只有加法操作。
• 可以想到能表示成 $((x+y)^2-x^2-y^2)/2$。
• $/2$ 可以表示成 $\times 2^{-1}$，求逆元可以在外面求，而乘法可以用龟速乘。$-x$ 可以表示成 $(p-1)\times x$，也用龟速乘。
• 现在问题在于平方，它只有 $d$ 次方，能否通过 $d$ 次方的值求出平方？给 $x,x+1,x+2,\cdots,x+d$ 前带个系数，让它们凑出 $x^2$。用高斯消元消一下，发现是可行的。每个都用龟速乘把系数带上求和即可求出平方后的值。

317E

• 牛逼题。如果你走不到影子那里，又因为两人都不能穿墙，就永远不可能抓到影子。
• 否则，你先走到当前影子的位置，然后看它现在在哪里，再继续走过去。如果你走出了这个 100*100，就可以再通过原来障碍的四个角，把影子靠上去再往它的方向走，就可以移动到一起。
• 每一步走了后长度要么减少要么不变，且如果你出不去的话那么每一次走到影子要么距离减小（影子被挡了一下），要么两个的增量相同，而不可能一直增量相同，那么你就走出去了，所以一定会求出解。

1292E

• 直接问 C,H 各一次剩下的都是 O，这样代价为 $2$。
• 考虑优化，问一下 CC,CH,CO 就可以求出 C 的位置，再求出 H 的位置可以用 OH,HH，剩下的都是 O（第一个位置可能是 H,O，最后一个位置可能是 C,O），这总共问了 $5$ 次长度为 $2$。

• 确定第一个和最后一个位置可以问 $3$ 次长度为 $n$，如果都不是就是剩下的一种。这样的代价总共是 $\frac 54+\frac 3{n^2}$，当 $n>4$ 时不超过 $1.4$。

• 题目的限制是 $n\geq 4$，所以要特判 $n=4$。

• 还是先问 CC,CH,CO,OH，如果问出了结果就至少确定了两个数，剩下的数还是用问 $3$ 次的方法解决，代价不超过 $\frac 44+\frac 3{16}$。但是接下来不能和之前一样了，否则代价就超了。
• 如果问 HH 出了结果，就有几种情况：HHHH,HHH*,HH**。有些不可能（*HHH,*HH*,**HH）的原因是 CH,OH,HH 都问过了，不可能存在某个 H 前一个位置没问出来。而 HHHH 不用考虑；HHH* 最后一个只有可能是 C,O；HH** 倒数第二个只可能是 O（CC,CH,CO 都问过了），最后一个只有可能是 C,O。由于只有最后一个有两种不确定，所以可以直接问 $1$ 次长度为 $4$ 的，代价为 $\frac 54+\frac 1{16}$。
• 如果问 HH 还不出结果，那么说明除了开头结尾一定是 O，且开头不是 C 结尾不是 H，如果其中有 O 就一定可以一次 OOO 问出来，否则就是另一个，代价为 $\frac 54+\frac 19$。

1267H

• 显然的一点是在任何一步不能有两个相同的数字相邻。
• 假设本身某个区间是合法的，往其中加入一些没有出现过的数，还是合法的。
• 考虑每次拿出一些不相邻的位置，然后变成一个子问题。
• 从后往前拆，倒着过来把每个能加入使得不会有数字相邻的选出，把它们分配一个新的权值，剩下的递归。
• 这样能选出 $\frac{n}{3}$ 个数（近似），即每次 $n$ 变为原来的 $\frac 23 n$（近似），那么需要的颜色数为 $\log_{\frac 32} n$（近似）。

1526F

• 考虑倒着推过来，假设知道了 $1,2$ 的位置或 $n-1,n-2$ 的位置，通过 $n-2$ 次询问就可以得到其它所有的（这个比较常见，求出某个特殊的可以推出全部）。
• 如果你求出了两个差比较小的 $a,b$，如果两个数的距离不超过 $\frac {n-4}3$，用它们两个询问出的距离最大次大分别是 $1,2$ 或 $n,n-1$。
• 那么假设你询问出的结果 $\leq \frac{n-4}6$，则任意两个距离都不超过 $\frac {n-4}3$。其实可以大力随机找，找不到的概率很小。不过也可以证明 13 个数中的所有三元组必定有符合条件的。其实也容易证明，考虑按照顺序两两之间的距离（共 12 个），现在相当于问是否有相邻两个都 $\leq \frac{n-4}6$。这个可以用鸽巢原理，总和不超过 $n-1$，则一定只有最多 5 个 $\geq \frac {n-4}6+1$，那么剩下的 7 个必定有两个相邻，它们就满足条件。