A. Don’t Detect Cycle
边双缩点之后可以把所有割边在最开始加入。然后每个边双联通分量就是独立的。
正着做不好做，考虑倒着做删边。
问题是要判，删掉一条边之后，边的两个端点不在环上。有结论是删边合法的充要条件是两端点的度数都是 $2$。充分性显然，必要性考虑删去这条边之后，图会变成一条链，每个点都是一个边双。然后这样两端的点必定是单点。
这样可能出现新的桥，再在最开始加入即可。复杂度 $\mathcal O(n^2)$。
B. Self Checkout
先不考虑序列中没有 $1$ 的情况。仅有开头是两个连续 $1$ 才会生成一个 $2$。否则是生成了 $3$。考虑目标序列中一段连续的 $3$ 的段，需要保证 $2$ 的前缀出现次数减一大于等于 $1$ 的前缀出现次数。这是一个卡特兰数。然后后面是一个 $2$ 的话就要连续接两个 $1$，这样每段的答案乘积就是最终答案。
对于序列最后只剩一个 $1$ 的情况，目标序列的末尾就是 $1$，并且目标序列的非末尾位置一定不是 $1$。
对于序列最后没有 $1$ 的情况，可以枚举最后一段连续 $2$ 的生成方式。
C. Segment Tree
首先线段树的结构可以做一个从下到上的 chkmin，即求一个从区间最左走到最右的最小代价。
查询就拉出来两条根链，DP 求出到每个根链上区间左右端点的最小代价，枚举中转点即可。复杂度一个 $\log$。
D. A xor B plus C
先考虑只有一位怎么做。递推式是 $x_{i+2}=x_{i+1}\oplus x_i\oplus C$。可以得到 $x_{i+3}=x_i$。
接下来考虑进位。递推式变为：
\[X_{i+2}=X_i\oplus X_{i+1}\oplus C\oplus Y_{i+2}\\ Y'_{i+2}=[(X_i\oplus X_{i+1})+C+Y_{i+2}\geq 2]\]还是考虑循环节。第一项有长度为 $3$ 的循环节，第二项是常数，考虑第 $0$ 位是第三项是 $0$，所以 $Y$ 的第一位有长度为 $3$ 的循环节。
整理一下式子可以得到 $X_i\oplus X_{i+3}=Y_{i+2}\oplus Y_{i+3}$，因为 $Y$ 的第一位有长度为 $3$ 的循环节，所以 $x$ 有长度为 $6$ 的循环节。以此类推，第 $k$ 位有 $3\times 2^k$ 的循环节。
因为 $A,B,C<2^{20}$，所以对于答案的最第 $20$ 位可以暴力求前 $3\times 2^{19}$ 个来找循环节。
对于高位，$C$ 全都是 $0$。所以只需要考虑第 $19$ 位对第 $20$ 位的进位。假设在第 $i$ 个位置有一个进位，手玩一下可以发现 $i$ 后面 $\bmod 3=i,i+1$ 的位置都异或了 $1$。所以考虑维护进位。
\[Y'_{i+2}=[(X_i\oplus X_{i+1})+Y_{i+2}\geq 2]\]这表明，下一位是 $1$ 的位置必须要满足原来的位置是 $1$ 或者原来的位置减循环节是 $1$。而对于前一项：
\[X_i=\bigoplus^{j\leq i}_{j\equiv i,i-1\pmod 3} Y_i\]带入上式，可以得到：
\[Y'_{i}=[(\bigoplus^{j<i}_{j\equiv i,i-1\pmod 3})+Y_{i+2}\geq 2]\]可以分析一下 $1$ 的个数不会特别多，然后就做完了？/whl/whl
E. ReTravel
是求一个生成树，满足存在 DFS 序能按照顺序遍历到关键点。因为只能向右下走，区间 DP，代价是两个区间的左上角的交点并起来。
F. Origami Warp
因为给的直线斜率都是有理数，所以只有斜率为 $1$ 和 $-1$ 的时候，角度才是 $2\pi$ 的约数，才能比较对称。
否则考虑两条夹角不为 $\frac{\pi}{4}$ 的直线，一个点在上面经过操作是可以到达距离交点为定值的一个圆的！
首先判一下所有直线交点都在同一个点的情况。否则如果存在倾斜角不为 $\frac{\pi}{4}$ 的，那平面上任意两点都可达。
然后分类讨论。如果只有横竖的，那横竖独立，求出来横线的和竖线的所有距离差的 $\gcd$，假设为 $g_x$ 和 $g_y$，则横纵坐标都可以 $\bmod 2g$。更进一步的讨论可以得到，充要条件是 $\bmod g$ 意义下相同或为相反数则合法。
剩余的情况，对于 $y=-x+k$，可以关于 $y$ 轴对称之后得到 $y=x-k$。考虑一条 $y=x+k$ 的直线，$(x,y)$ 经过对称之后会变成 $(y-k,x+k)$。这样 $g_x,g_y$ 就统一了。
进一步的，考虑将 $x$ 轴沿着 $y=x-k$ 对称会得到 $x=k$，所以 $g$ 可以再和 $c$ 做一个 $\gcd$。
此时只有两种斜线：$y=x$ 和 $y=x+g$。暴力枚举是否操作，最后判断横纵坐标都要在 $\bmod 2g$ 意义下相同或者互为相反数即可。