constructive
566E
- 对于一对相邻的点 $(x,y)$，它们其它的相邻点之间的交集就是 ${x,y}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的（出现的点如果不相邻那么它们路径上的也应该在交集中）。
- 这样可以求出所有非叶子节点之间的连边，剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。
- 这样非叶子节点数量 <=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<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<k<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)<2n$。
- 对于 $k$ 是偶数，无论怎样翻转奇数位还在奇数位置上，偶数同理，所以可以再判断 $s,t$ 奇数位之和是否相同。剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=-d_1$。这样清的位置是一个前缀或后缀，且会不停地翻，只剩下第一个和最后一个位置，次数是 $k+(m-k)<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
- 先离散化然后讨论。
- 如果一个位置覆盖了超过两个，这个位置就一定不会被照到。
- 如果一个位置覆盖了正好两个，想要照到就必须让两个都消失。
- 如果一个位置覆盖了恰好一个，若相交的有覆盖恰好两个的那么之前一定算到了，如果没有则说明相交部分没有贡献，可以都当作没有相交的来算，数据结构维护即可。
933E
- 可以改为相邻的同时减任意值。证明可以使用归纳，从后往前考虑相邻两个之间总共减了多少次，如果恰好是当前最后一个数那么多次，即等价于对最后一个做这样一次操作；如果不到，那么不妨先不减最后一个数，把多余的操作次数给前一个，如果使得倒数第二个直接减为 0 那么先处理前面的，再做 $(n-2,n-1),(n-1,n)$，这样次数不会增加（只要保证为 0 的依旧为 0 剩下的任意）。
- 根据上面的证明也可知一定可以按照从左往右的顺序，所以区间情况
ps：我现在又感觉有问题，先放着。
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 个必定有两个相邻，它们就满足条件。
geometry
792F
- 转化为打出 $1$ 的伤害要消耗 $\frac yx$ 的法力值和 $\frac 1x$ 秒。
- 可以变成一个线性规划问题，设第 $i$ 种法术打了 $v_i$ 的伤害，则限制为 $\sum_i \frac{y_i}{x_i}v_i\leq m,\sum_i \frac 1{x_i}v_i\leq t$，要求 $\operatorname{maximize} \sum_i v_i$。
- 对偶一下（？），即变成 $\operatorname{minimize} km+rt$（第一个的限制的对偶为 $k$，第二个限制的对偶为 $r$），要求 $k,r\geq 0$，且 $\forall i,\frac{y_i}{x_i}k+\frac{1}{x_i}r\geq 1$，可以改写为 $r\geq x_i-y_ik$。
- 又由于线性规划目标函数值关于于每一个变量都是凸的（？），所以可以三分 $k$，根据式子可以求出最小的 $r$。如果快速查询？$x_i-y_ik$ 可以看作若干一次函数，李超树动态维护即可。
1508D
- 如果排列形成一个环，就可以固定一个点，每次其它点都和它交换。这样最后的图就是它连向其它所有点，一定不会相交。
- 但是多个环就有可能出现相交的，我们希望这种情况不会发生，比如说先提前把它们合并成一个环。不妨设 Down-Left 的点为最后固定的点，把它变为原点，剩下所有点极角排序，相邻的如果不在一个环就合并。这样和原点往外连的一定不会相交。
1534G
- 先切比雪夫转曼哈顿，变成每次往右上或右下走。
- 则标记一个点一定在 $x$ 相同的时候标记，因为 $
- 固定 $x$ 看所有 $y$ 的贡献，如果当前 $x$ 有点就给每个加上和 $y$ 差的绝对值，从上一行转移就是从 $y-1$ 和 $y+1$ 的较小值转移过来。
- 然后自闭，怎么优化呢？你发现第一个操作是加一个凸函数，而凸函数之和显然还是凸函数；第二个操作对于凸函数操作还是凸函数（这里的定义只保存和 $x$ 奇偶性相同的，刚开始我不知道，迷惑了半天）。
- 不过肯定不能这样扫过去，所以不考虑中间一段空白的，用 set 维护每一段斜率，加入的时候根据加入的点和最小值的位置讨论一下。
744D
- 边界上可以包含可以不包含，说明固定圆心后一定可以扩大半径到和某个蓝点相切。
- 换个角度，对于那个在边界上的蓝点，它和圆心两点作一条直线，把圆心往另一个方向移动，要求蓝点还在边界上，此时圆包含的部分只多不少，所以又可以扩大到有另一个蓝点在边界上。
- 所以 $O(n^3)$ 可以枚举两个蓝点解出圆然后判断。不过更快的做法是二分，直接枚举一个蓝点，算出红点蓝点能贡献的极角，看是否有区间只有红点没有蓝点。但是这样不一定是有二分性的，原因是很小你可能直接包含不到红点，所以红点在边界上的先得算上。把所有的一起二分，刚开始枚举的时候红点蓝点都枚举，再判断是否可行即可。
607E
- 以 $(p,q)$ 为原点考虑。
- 这么 $m$ 并不是很大，最后要暴力把 $m$ 个答案加起来。
- 二分答案求出第 $m$ 小的值（圆的半径），判断圆的半径内是否有 $m$ 个。
- 两条直线是否在圆内相交，等价于它们和圆的交点交错排列。 离散化一下可以变成线段相交且不包含的数量。
- 排序之后按照顺序加入，每次查询之前右端点在当前区间的个数，树状数组即可（注意是一个环，可以倍长然后在后面一段计算答案）。
- 至于求那 $m$ 个，也不能暴力求，因为有可能一大堆恰好在圆边界上的，总数量很多。
- 只求那些不是恰好在边界上的，剩下的都是二分出来的答案。这些的求法和之前类似，把树状数组换成 set 暴力求出所有可行的。
528E
- 根据经典多边形面积计算方法，面积为 $\dfrac 12(\overrightarrow{OA}\times \overrightarrow{OB}+\overrightarrow{OB}\times \overrightarrow{OC}+\overrightarrow{OC}\times \overrightarrow{OA})$。
- 里面的乘积可以拆开，所以可以枚举两条直线然后计算。不过根据叉积的定义式可以发现叉积是满足分配律的，所以你可以直接把其它的加起来再做叉积。
- 所以只需要枚举两条直线，求出交点即可。不过要保证叉积的顺序正确，所以取原点为一个很远的点，直线按照极角序从小到大插入（也就是你加的面积都是正的）。
1584G
- 对每个 $P$ 画半径为 $R$ 的圆。把这个线段距离不超过 $R$ 变成到两条射线都不超过 $R$。
- 枚举 $P_i$，那么所有的 $P_j$ 必须在 $P_i$ 向圆作的两条切线，形成的夹角范围内。若干个夹角求角还是可以求的。
- 然后看每个点是否在合法的夹角区间内，如果不可以就标记为不行（可以不一定行，反过来还要再判断一次，两条射线）。
780H
- 首先可以 two-pointers 求出两个出发时间差为 $\frac Cm$ 的点的距离的变化过程。
- 二分答案，可以求出哪些时刻是可行的（具体就是看当前这两段走完一段的时间，过程中距离是一个关于 $t$ 的二次函数，可以解出来合法的时间段）。
- 由于段数是 $O(n)$ 条的，所以判断是否有时刻合法，可以把区间的时间 $\bmod \frac Cm$，有多个的 and 起来看是否有非 0 位置。离散化即可。
1446F
- 和 607E 类似，二分答案求出第 $k$ 小的值（圆的半径），判断两点连线和圆有交的是否有 $m$ 个。
- 两个点的连线是否和圆相交，等价于它们和圆的切点交错排列。 离散化一下可以变成线段相交且不包含的数量。
- 排序之后按照顺序加入，每次查询之前右端点在当前区间的个数，树状数组即可（注意是一个环，可以倍长然后在后面一段计算答案）。
696F
- 这个圆和直线有交是指圆心到直线距离不超过 $r$。
- 二分这个 $r$，那么每个直线的限制就是要求在一个半平面内，求一下半平面交就可以得到是否存在点合法。
- 所以现在要把一些分给一个点，另一些分给另外一个点，怎么分呢？可以看点到 $A$ 比 $B$ 近的情况，此时就是 $AB$ 直线和边所在的直线的交点距离 $A$ 比距离 $B$ 近，画一下就容易发现一定是一段区间，剩下的都是离 $B$ 近的，双指针即可求出。