ARC093F
不会
我们发现，如果(1)和某个(x)在第(i)次比赛中相遇，那么(x)必须得是自己的那棵子树中所有(2^i)个数字里最小的
由于总共的子树只有(O(n))棵，我们考虑容斥，强制枚举某个集合(S)表示这个集合代表的子树的最小值是这(m)个数中的某一个，算出(f(S))，最后统计答案即可
从大到小考虑每个数字，我们可以设(f_{i,s})表示考虑(m)个数中前(i)大的，其中集合(s)所代表的的子树已经被占据了的方案数，枚举新占据哪个子树，用组合数计算方案数即可
CF708E
不会
设(c_i)表示(k)秒后左边恰有(i)个格子消失的概率，那么一行剩下([l,r])的概率就是(c_{l-1} imes c_{m-r})
我们设(f_{i,l,r})表示第(i)行剩下([l,r])，且上面都连通的概率，容易写出一个(O(nm^2))的转移
考虑优化，我们设(f_{i,l}=sum_r f_{i,l,r},g_{i,r}=sum_l f_{i,l,r})，容易发现(f,g)可以通过前缀和优化做到(O(nm))的转移
CF571D
不会
如果只考虑学校的话，用一个带权并查集就能处理
如果只考虑军营的话，也可以用一个带权并查集来处理每个点最后一次被爆破的时间
那么我们先只考虑军营，预处理出每个点最后被爆破的时间，然后离线处理学校就行了
AGC029C
二分一下，然后模拟即可
AGC037F
做过，(这里)[https://www.cnblogs.com/yuanquming/p/11378620.html]
CF553E
不会
我们设(f_{u,i})表示(i时刻在)u$时的最小期望代价，转移如下
边界条件为(forall i>t,f_{u,i}=dis_u+x)
注意到(f)的第二维是递减的，而且我们可以把后面那一个东西写成卷积的形式
所以用分治(FFT)即可
AGC24E
不会
如果我们直接算往(A_i)中添加一个数使得(A_{i+1}>A_i)，那么方案会算重，比方说(233)，添加一个(3)，它放在第一个(3)前面和第(2)个(3)前面是一样的。为了避免这种情况，我们强制这种时候都把(x)放在连续一段(x)的最后面
方便起见设(A_0={0})，那么我们发现一个满足条件的方案中(x)需要放在一个严格小于(x)的数前面
我们考虑一棵树，有(n+1)个点，根为(0)表示虚根，每个点的编号表示它是在第几次操作中放入的，权值为这个数的权值，容易发现它满足堆的性质，而且每一个堆和一个操作序列都是一一对应的，所以我们只需要考虑这样的堆的个数即可
设(f_{i,j})表示树的大小为(i)，编号为([0,i))，根的权值为(j)的方案数，转移我们枚举(1)号点（也就是编号最小的儿子）
后面组合数表示子树内的编号，发现(l)可以用后缀和优化
最终的答案就是(f_{n+1,0})
AGC027F
不会
我们先枚举一个不动的点，将它当做根节点，那么此时一个点被操作当且仅当它在两棵树中的父亲不同，且它必须在第一棵树父亲之前被操作，在第二棵树父亲之后被操作
我们模拟一下这个过程，康康是否可行
顺便注意如果根节点度数为(1)，那么根节点也可能被操作，此时答案为(n)
CF536D
不会
首先求出(S)和(T)到每个点的最短路，离散之后分别作为这个点的横纵坐标，那么就是要求轮流选若干行列
设(f_{i,j,0/1})表示选了([i+1,n])行和([j+1,m])列，谁先手时，以(f_{i,j,0})为例，如果第(i+1)行没有数了，那么(f_{i,j,0}=f_{i+1,j,0})，否则设这些数的和为(s)，(f_{i,j,0}=max(f_{i+1,j,0},-f_{i+1,j,1})+s)
AGC028D
不会
我们考虑枚举连通块的左端点和右端点来计算贡献，设(f_{i,j})表示(i,j)连通，且((i,j))中的边没有连出((i,j))之外的方案数
先求出(g_n)表示(n)个点任意匹配的方案数，以及(c_{i,j})表示([i,j])范围内未匹配的点数，那么(f)的计算就是用任意的减去不连通的，即
复杂度(O(n^3))
AGC031E
做过
首先，我们先枚举选的珠宝的个数(k)
然后先来考虑一维的情况，对于(L a_i b_i)来说，就是小于等于(a_i)的数最多选(b_i)个，等价于选的第(b_i+1)个的坐标要大于等于(a_i+1)
同理，(R a_i b_i)就代表选的第(k-b_i)个的坐标要小于等于(a_i-1)
那么我们对于每一个位置，都得到了一个区间([L_i,R_i])，表示选的第(i)个数的横坐标要在这个区间内（显然这里有(L_ileq L_{i+1})，因为如果(L_i>L_{i+1})等价于把(L_{i+1})设为(Li)，那么同理(R_ileq R_{i+1})）
然后建二分图，左边(k)个点，每个点向右边(n)个点中的可行点连边，跑一个最大权匹配就行了
然后回来考虑二维的情况，左边(k)个点表示(x)坐标的限制，中间(2n)个点左边表示(x)右边表示(y)，(xy)之间连对应的珠宝的边权，右边(k)个点表示(y)坐标的限制，跑一个费用流就行了
CF605E
不会，完全没看到最优策略几个字
设(E(u))表示从(u)到(n)的期望步数，考虑下一步，如果是走到(v)且(E(v)geq E(u))，那么当前这一步的最优策略肯定是停在原地
由于我们永远不会走到一个比当前期望步数大的点，所以我们可以考虑将所有答案按从小到大得到顺序算出，并以此扩展
设(u)的后继分别为(v_i)且(E)非降，那么
第一部分表示(v_i)可以走且所有期望步数小于(v_i)的都不能走，第二部分表示这些点都不能走，那么就停在原地，第三部分就是这一步
那么我们每一次选出(E(u))最小的(u)来更新所有点的答案，为防止(1-prod_i(1-p_{v_i})=0)的情况，我们记下(prod_i(1-p_{v_i}))，算的时候再除掉就行了
ARC102F
不会，题解没看懂
CF666D
不会
先枚举每个点是上下还是左右，那么去重之后得到四条直线，考虑怎么求正方形顶点
如果是两横两竖，那么必须在四个交点
如果是一横两竖，那么正方形顶点必须在两个交点，枚举剩下的两个交点在上面还是下面
如果是两竖，那么已经知道了边长，对(x_1)来说，最大值就是(x_1,x_2+D,x_3,x_4+D)的最大最小值的平均值
细节会比较麻烦
CF626G
不会
我们发现，如果某个位置当前已经加了(c_i)张票，再加一张对答案的贡献是({l_iover (c_i+l_i)(c_i+l_i+1)})
而总共的票数(tleq 2 imes 10^5)，所以我们可以用一个堆维护所有的位置(+1)的贡献
考虑一次更改，可以证明最多只会改变一张票，所以我们可以再开一个堆维护所有已经加入的票，每次取出最小的删掉
AGC027E
不会
如果将(a)视为(1)，(b)视为(2)，那么整个串在模(3)意义下的和是不变的
如果不存在两个相邻且相同的字符那么答案一定是(1)，否则(s)能变成(t)，当且仅当我们能把(s)划分成若干段，使得其中一段为(0)，剩下每一段都和(t)的字符对应，直接(dp)就行了
AGC036E
做过，这里
CF611H
不会
我们把(1)号点当成根，那么可以看做是边和儿子的匹配，由于同种颜色本质相同所以我们一起考虑，每一次取出两个颜色康康在这两个颜色之间连一条边是否合法，合法的话就选择这两个颜色的代表点连边。由于这是一个二分图，根据(Hall)定理，如果二分图((X,Y))存在完美匹配且(|X|leq |Y|)，那么对于(X)的每个点集(S)，它向另一边连接的点数(geq |S|)，用这个判断一下就行了
AGC029E
不会
我们记(c_u)为(u)的答案，以(1)号点为根，(mp_u)表示根节点到(p_u)的路径上的最大值，(Q(u,x))表示从(u)出发，只经过(idleq x)的点能到达的(u)的子孙的个数，然后考虑设(u)是(v)的父亲，有
发现对于每个数来说只有(Q)只有两个值是有用的，而且由于一些奇妙的性质所以爆搜即可
AGC038F
做过，这里
CF528C
不会
首先一个充要条件是每个点的度数为偶数且总边数为偶数，这个就随便匹配两个奇数度的点，最后康康要不要再连一条自环
然后我们跑一个欧拉回路，对于回路上第奇数条边原方向，偶数条边反方向就是了
AGC21F
做过，这里
AGC033E
不会
我们分情况考虑，如果全都是同一种颜色，假设全都为(R)，那么连续两段蓝色的圆弧肯定不合法，问题转化为一个长度为(n)的序列，不允许有两个相邻的蓝色，首尾也不许同时蓝色的方案数。记一下(dp_{0,1,2,3})分别表示开始是否为蓝色，当前最后一个是否为蓝色的方案数，转移显然
如果不是同一种颜色，假设开头的颜色为(R)，那么依然不允许存在两端相邻蓝色圆弧。然后还有两个结论
-
整个序列一定是由若干段组成的，其中每一段都形如连续奇数个红色+一个蓝色
-
每一段序列的长度都有一个限制，不能超过(L)
先考虑第一个结论，如果连续红色的个数为偶数，我们不妨设序列最前面有连续(k)个(R)，如果(k)是奇数，把起始点设为这段红色的结尾就(gg)，如果(k)是偶数，把起始点设为这段红色结尾前一个依然(gg)，所以只有红色个数是奇数合法
第二个结论，对于开头的连续(k)个(R)，如果(k)是偶数，则最多只能放连续(k+1)个红色，如果(k)是奇数则最多只能放连续(k)个。如果这(k)个连续(R)不在开头，那么它们前面是一个(B)，也就是说我们现在在一段红色的一个端点处。如果(k)是偶数，显然可以走回来，如果(k)是奇数，那么这段连续红色的个数不能超过(k)。
那么我们预处理出(dp_i)表示长度为(i)的序列的合法方案数，发现奇数的位置肯定全都是红色，所以我们只要考虑偶数位置怎么放就行了，转移也比较显然
最后是旋转导致的多种方案数，我们枚举第一个蓝色和最后一个蓝色之间的距离，乘上对应的系数就好了
CF613E
不会
我们发现整个路径最多被分成三段，其中第一段先往左再转弯再往右，第二段只能上，下，右，第三段也是先左再转弯再往右，分别用哈希来(dp)一下就行了
AGC022D
不会
实际上就是判断到底会走几个来回
先将(t_iover 2L)加入答案，然后将(t_imod 2L)，设(l_i)表示火车从右边来，下次经过(i)时能不能直接上车，(r_i)同理
对于最右边的，一定是从左边来的，所以如果(r_n=0)就(++ans)
对于省下的，如果(i<j)且(l_i=1,r_j=1)，那么就可以匹配成一组，减少一次来回，由于(l_i=1,r_i=0)的点一定在(l_i=0,r_i=1)的点右边，所以可以对两端分别匹配
AGC034E
不会
首先枚举根，那么有两种操作，一种是选两个有祖先关系的点，一种是选两个没有祖先关系的点。由于前一种操作不会改变深度之和，所以可以证明不需要考虑，那么我们只考虑第二种操作
如果记所有子树的深度和分别为(sz_1,...,sz_n)，每次可以选择两个不同的点同时(-1)，那么这是一个经典模型，结论就是如果(sum-mxgeq mx)则最后剩下的是(0/1)（取决于(sum)的奇偶性），否则是(mx-(sum-mx))
这是只操作根的情况，我们还需要递归一下(mx)的那棵子树，康康能得到的最小深度和是多少
CF566E
不会
先考虑一般情况，即非叶结点个数大于等于(3)
两个非叶节点((u,v))有边，当且仅当存在两个集合的交为({x,y})，用(bitset)优化就可以得到所有非叶节点之间的边了
然后考虑叶节点，叶节点对应的集合一定是所有包含它的集合里最小的那个，找出一一对应之后，发现去掉这个集合里所有叶节点，就等于它所连的非叶节点的连边集合，那么我们就可以找到它所连的非叶节点了
剩下的特殊情况讨论一下即可
ARC029F
不会
考虑一条边((u,v))，如果他俩在同一个强连通分量里，那么(diff)的条件就是不存在另一条(u)到(v)的路径，如果在同一个强联通分量里，那么(diff)的条件就是存在另一条(u)到(v)的路径
那么我们以每个点(u)为根遍历一遍，记录下到达每个点时是从(u)的哪条出边出来的，每个点最多只会被遍历到(2)次（第一次和大于等于(2)次），时间复杂度(O(nm))
CF700E
不会
建出(SAM)后线段树合并，然后在(parent)树上树形dp一下就行了
CF566C
做过
假设现在根节点为(u)，康康往(v)走会不会更优
设现在根节点在((u,v))这条边上，离(u)的距离为(x)，那么权值为
求导之后为
如果(x>0)时导数小于(0)就往这棵子树走，那么只需要判断一下此时是否有(v)满足(2 imes sum_{iin tree_v} a_isqrt{d_i}geq sum_{i} a_isqrt{d_i})即可，然后点分往里面跑，这样只会走(O(log n))个点，总复杂度(O(nlog n))