更好的阅读体验题目传送门题目大意：给定一个有向无环图，每次操作可以选择一个入度为\(0\)的点\(x\)和一个出度为\(0\)的点\(y\)，将\(x\)的所有出边全删去，然后新加一条有向边\((y,x)\)。现在需要将所有的点的入度、出度都小于等于\(1\)，给出一个总步数不超过\(n\)的

好像在洛谷题解区里还没人和我做法一样，，？考场做法，只用到了倍增和线段树，感觉挺好写。考场上从开题到过题只用了2h。最底下有省流版（？）。以下是我考场里比较详细的思路，所以比较长。先考虑如何\(O(n^2)\)做，然后再想优化。容易先想到一个状态数是\(O(n^2)\)的DP，即记录起点，并将向

D2T3树形图首先判掉一些case将任意一个\(1\)类点定为根，求出一棵dfs树，则图上的非树边只有返祖边，没有横叉边。\(1\)类点考虑在这棵dfs树的基础上求出所有\(1\)类点：考虑\(fa_u\tou\)这条边被几条返祖边覆盖了，由于这是一个强连通分量，所以子树中至少有一条返祖边覆

Errich-Tac-Toe(HardVersion)题目描述TheonlydifferencebetweentheeasyandhardversionsisthattokensoftypeOdonotappearintheinputoftheeasyversion.ErrichtogaveMonogonthefollowingchallengeinordertointimidatehimfromtakingh

原题链接感觉挺有意思的。先简化一下不合法的状况，实际上是如果特殊边两侧都有点，且那两个点的另外三个联通方向上也有至少一个点，就是坏的。相当于是四个限制只要有一个不满足就可以了。于是就可以转化成最小割。按四种限制将点分成四类。特殊边两侧分别是\(1\)类点和\(2\)类

RestoringMap星空蚁来了秒了。人与人的智力是有差距的。刷再多的CF智力不行就是不行。OI这种需要智力的游戏不适合我。我还是更适合对智力要求低一点的。比如和妹子贴贴。但是也没有妹子。lifeishard.这类树的构造似乎可以从边缘情况想起,比如CF1844G但是这个题从叶

T1考场竟然没有想到单调栈！后面看题解一看到栈就顿悟了。考场打的时\(O(n\log^2n)\)倍增，挂掉了，区间求重复了。还T了一些点，应该是常数比较大。倍增在求答案的时候其实是可以做到\(O(\logn)\)的，但是我“执意”要求GCD，时间就炸掉了。GCD，LCM和倍数因数关系如果想成与乘除法

CF1442FDifferentiatingGames传送门CF1442FDifferentiatingGames题目大意给你一个DAG，\(n(n\le1000)\)个点，\(m(m\le10^5)\)条边。一次游戏为：两人轮流操作，每

引理1：若\(n\)为偶数，则答案为\(n\)。若\(n\)是叶子，则显然正确。若\(n\)不是叶子，则将整棵树看做以\(n\)为根的有根树，一定可以保证最后一个被删除的是根。故得

题目传送门思路首先我们思考一个性质，由于不能有连续单调不升/不降的三个点连在一起，所以对于单个点来讲，显然要么只和比它大的连边（称为A类点），要么只和比它小的连边（称为B类点

D.ShiftandFlip给定两个\(01\)串\(A\)和\(B\)，每次操作可以将\(A\)循环左移或右移一位，或选择一个\(B_i=1\)的位置将\(A_i\)取反，求使\(A\)和\(B\)相等

考虑将点分为$A,B$两类。其中$[x\inA]\iff\exists_{y\neqx},y|x$。那么我们删去的点只可能在$B$类中，且当前$x\inB$可删当且仅当存在$y\inB,z\inA$使得$z|x