sfiction/selection/Codeforces

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
- 468C, [], 解法非常巧妙
- 519E, [LCA], 树上两点中点，LCA倍增法应用
- 570D, [DFS], 按高度分层后对DFS序二分，离线可在进出时分别统计答案做到O(n+m)
- 601D, [Trie], Trie树内部冗余合并。
- 609E, [MST, LCA, 倍增], MST之外边w与MST所成环上所有边权值大于等于w
- 611F, [], 枚举前2n步，之后选取关键点枚举。枚举前2n步时直接删除非关键点。
- 618E, [数学, 线段树], 坐标变换矩阵。还有其他做法@@
- 618F, [数学], 鸽笼原理
- 622F, [数学], 拉格朗日插值法
- 629E, [树形DP],
- 632E, [FFT], FFT计算幂可通过对点值表示法求幂加速
- 632F, [MST],
- 633F, [树形DP], 树上多链最大权值和
- 645E, [字符串], 相异子串计数，增量法（考虑子串结尾）。
- 645F, [数论, 计数], 枚举GCD。可以考虑对贡献去重和对集合去重。本题集合去重比较麻烦，贡献去重只需要求出phi(x)即可。
- 650D, [LIS], 对每个询问，求包含和不包含修改位置的LIS。
- 652F, [其他], 将蚂蚁相撞视为互换标号。
- 653E, [DS, 连通性], 禁止边并查集，维护连通块集合及对应点数，对当前点扫描禁止边，将全被禁止的连通块移出。
- 653F, [SA, 括号序列], 括号序列合法子序列的半区间查询（单点固定）和SA去重
- 653G, [组合计数],
- 660E, [组合计数, 字符串], f[n][m]可由f[n-1][m]求得，方法与644E相似。另外也可以计算每个串的贡献，只需令当前枚举子串为整个串“最早出现”的该子串即可。
- 662C, [DP, fwt], 根据交换操作的mask进行DP。
- 665E, [Trie], 将二进制表示视为串从高位到低位加入Trie，维护每个结点的串数进行统计。O(nlogn)。
- 666C, [数学], 正整数n的任意划分中，不同数的数量不超过sqrt(n)。对某个长度可以做到O(n)DP。总的复杂度为O(n^1.5)。
- 675E, [贪心, 单调队列], 从后往前贪心，维护一个关于a[i]的单调队列，选择[i+1,a[i]]中a[j]最大的一个，因为必然包含其他位置的所有选择。统计从后往前线性即可。O(nlogn)。
- 677D, [分块, BFS], 显然可以将每种箱子视为一个阶段，若上阶段点数大于n则BFS转移，否则点对点转移，每点均摊复杂度不超过O(n)。O(n^3)
- 677E, [对数], 枚举中心，对数比较保证精度。O(n^2)。
- 678E, [状压DP], f[i][mask] 表示已选 i，待选 mask 的最大胜率。O(n2^n)。
- 679C, [BFS, 尺取法], 线性维护当前范围内连通块和各种块数量。O(n^3)。
- 682E, [几何, 凸包], 找出面积最大的三角形，以其顶点为中点作所求三角形，必定包含所有点，否则可以构造面积更大的三角形。O(n^2)。

- 710F, [AC自动机, 二分], 用类似二项堆的方法维护多个AC自动机，暴力合并。O(Llogn)。
- 713C, [DP], 离散化取值后DP，O(nlogn+n^2)。还有一个与维护凸线相关的O(nlogn)做法。
- 715B, [图论, 二分答案], 先判断无解、已有解等边界情况，然后在待定边（顺序无关）上二分，得到将最大的前缀置零而大于L的位置，然后二分下一条边的取值。O(km(logn+logm))或O(mlogn(logn+logm))，取决于最短路。
- 715C, [数论, 树分治], 根据后缀计算相应合法前缀，O(nlog^2n)。
- 717A, [数论, 组合数转多项式, 带根号公式取模], 将组合数展开为多项式，问题即转化为fibonacci数列k次幂求和，可以对其通项公式等比数列求和。O(k^2logL)。
- 717F, [性质转化, 数据结构], 要求区间内奇偶位置和相等没有零，线段树数据域设计。O(nlogn)。
- 722E, [DP], 首先只需考虑经过特殊方块的次数。设f[i][j]为从i处出发，经过恰好j个特殊方块的路径数。则按照偏序关系求解f[i][j]时，所有经过次数>j的路径都可以根据倒数第j+1个经过的点归类统计。
- 723E, [欧拉回路, 消环], 连边构造欧拉回路。消环后DFS分配方向。O(m)或O(m^2)。
- 724E, [网络流, DP], 用动态规划求解特殊网络的最小割。O(n^2)。
- 724F, [DP], 通过重心将无根树转化为有根树，有根树计数可以用f[i][j][k]表示i个点j棵子树，子树大小不超过k且子树中的内部节点均满足度数要求的解的数量，DP即可
- 724G, [异或线性基], 图中任意环都可以通过连边的方式加入路径。O(m+nlogV)。
- 725E, [性质], 可以证明对于一个选择序列，合并其中任意两个之后所选硬币仍然不变。因此枚举加入的硬币面值即可。如果取硬币时相同面值一次取完，则最多sqrt(C)种不同面值，复杂度为O(sqrt(n))，可以预处理完成。O(C^1.5)。
- 727F, [DP], 从后往前DP求出[i..n]去掉j个后所得序列前缀和的最小值。询问可以二分求得。O(n^2+qlogn)。
- 731D, [字符串], 只需考虑相邻串第一个不同位置即可，对所有可行区间求交。O(c+L)
- 731E, [DP], 设dp[i]为1..i合并后i..n的先手最优解。O(n)。
- 731F, [数论], 枚举起点，为i时只有n/i段。O(nlogn)。
- 732E, [贪心], 对pi从大到小排序，当前最大socket匹配则解+1，否则给socket加一个转换器。O(nlog^2n)。
- 732F, [边双连通], 双连通分量按照tarjan算法的访问顺序即可变为强连通分量，剩下的树形结构被汇点所限制，因此全部指向最大值即可。O(m)。
- 733F, [图论, MST], 注意到在一个解中除了c[i]最小边之外其他边的c[]都是没有意义的，可以先根据w求出一个MST，然后枚举c[i]更小的边更新答案。从MST中选取路径最大边可以用LCA，也可以利用MST的特性。实际树结构上的路径最大值必定也出现在按秩合并的并查集的路径中，这是因为最大值在最后才加入，所有两连通分量间的路径都会经过它。O(m(logm+logn))。
- 735E, [树形DP], dp[u][i]表示点u为根子树的状态，i<=k表示最近黑点离根距离为i，否则表示最远未覆盖白点离根距离为i-k-1，转移时利用前缀和优化。O(nk)。
- 736D, [代数], 考虑完美匹配的矩阵表示，易见与询问与相应位置的代数余子式有关，可以通过逆矩阵求出所有代数余子式。O(n^3/32)。
- 737D, [DP], 一个简单的想法是用dp(l,r,k,p)表示当前为玩家p，上一步取了k个，先手取了l，后手取了r的最优结果。注意到整个游戏过程中两个玩家取走的数的个数差不超过k，因此r可以用r-l代替，状态空间变得相对密集，不需要hash。O(n^2)。
- 739C, [数据结构], 差分后用线段树维护。O(nlogn)。
- 741D, [数据结构], 启发式合并或者树分治。参见dsu on tree。O(Sigma*nlogn)。
- 743E, [DP,二分答案], 二分较小长度len，DP求最多len+1数量。dp(i,mask)表示前i个数，已选数为mask的最大值。O(n2^klogn)。
- 744C, [状压DP], 考虑将所有购买行为移到最后，就只是一个攒钱-购买的过程，于是求最多能省下多少货币。dp[mask][i]表示已经购买物品mask，省下i个red时，最多省下多少blue。O(n^3*2^n)。
- 746F, [尺取法, 数据结构], 容易证明满足尺取法所需性质，用数据结构按所节约时间维护曲目，转为数据结构上二分+求和。O(nlogn)。
- 748F, [图论], 总可以挑选一个点u，每棵子树中点数都<=k，因此答案必定为1。O(nlogn)。对于pair的求解，令同棵子树的点在序列中相邻，那么a[i]和a[i+k]必属于不同子树。
- 749E, [数据结构], 每对数相互独立，对于(i,j)，只有被所选区间完全覆盖时才有1/2概率反转。因此统计所有逆序对的被盖区间数，可以枚举j，计算所有i<j&a_i>a_j的i的和。O(nlogn)。
- 755E, [图论, 构造], 可以证明（https://math.stackexchange.com/questions/1929512/if-the-diameter-of-graph-is-greater-than-3-then-the-diameter-of-its-complement-g）不存在m<=1||m>=4的解，而m=2时红色边为1-n的链，m=3时2..n是以3为中心的菊花图，1再接到2上。O(n)。
- 755F, [贪心, DP], 最大值的部分贪心解决，最小值的部分即为背包问题。注意到最多只有n^0.5种不同物品，每一类再用多重背包的常用作法折半划分处理即可。一个粗略的上界是O(n^1.5logn/32)。可以证明一个更精确的界O(n^1.5/32)。另外一种是将物品按照大小分为<=T和>T两种，前者用O(nm)的多重背包存在性判定算法处理，后者用01背包处理并用bitset优化，复杂度为O(Tn+n^2/(32T))。
- 756C, [数据结构, 括号序列], 将push视为'('，pop视为')'，则问题转化为求出当前序列的最长合法后缀。将'('和')'分别视为1和-1，用线段树维护后缀和即可。O(nlogn)。
- 756D, [组合计数, DP], 只需关注没有相邻项相同的子序列，其他子序列可以“压缩”成这样的子序列。一个长为k的子序列对应C(n-1,k-1)个最终状态。因为要避免相邻项相同，容易想到用dp(i,j,c)来表示[1..j]中尾部为c，长为i的子序列数量。实际上状态可以进一步压缩。dp(i,j)表示[1..j]中以j结尾，长为i的子序列数量，转移时需要额外的数组。O(n^2)。
- 757D, [DP], 串长75最多只能构造m=20的解，因此状态压缩即可。因为要求中间段非零，每个状态转移最多只有五次。O(n*2^n)。
- 757E, [数论], 注意到递推式等价于f_{r+1}(n)=\sum_{d|n}{f_{r}(d)}，容易证明f_{r}满足数论积性，并且f(p^k)的值与p无关。由n的范围知k最大为19，因此可以预处理出所有r<=1e6,k<=19的f_{r}(p^k)，处理询问时做素因数分解即可。素因数分解可以用筛法预处理i的最小质因数md[i]将分解加速到O(logn)。O(rlogn+qlogn)。
- 758E, [贪心], 因为接近根的边副作用更小，所以先自底向上将整棵树重量最小化，然后自顶向下将边权扩展到极限。O(n)。
- 758F, [数学], 首项末项满足ax^(n-1)和ay^(n-1)的形式，且gcd(x,y)=1。因此枚举x和y计算a的取值数即可。O(n^(2*(n-1))logn)。
- 761F, [adhoc], 将每个和分为矩形内和矩形外两部分。矩形内只要统计每种字符的出现次数之和即可，因为第i幅图在矩形i中都是字符c[i]，差异为0，被包含也没有关系。对于矩形外的部分，相当于原图与其他变异图在矩形外的差异之和，由于原图和i在外部完全一致，为了统计方便可以包含i。于是相当于总的差异值减去所有图在矩形i内的差异值之和。所以只需要支持矩形内字符数的查询和矩形内差异值之和的查询。O(n^2SIGMA)。
- 762E, [数据结构], 统计对象有三个限制条件，关于fi的条件因为K过小可以暴力枚举，半径限制的一侧用数据结构维护，另一侧则通过从左往右扫描一遍维护进出解决。O(nklogn)。
- 763C, [数学, 随机化], 由于和固定，确定x即可求出d，然后暴力测试，对于不合法的情形，有(m-n)/m的概率测试失败，因此总的测试量是nlogn级别。另外在m<2n时如果有解，x+kd必定是最大的循环群，因此可以对序列取反，提高测试失败的概率。O(knlogn)。k为单次测试的复杂度。
- 763D, [树同构], 可以用哈希解决，复杂度为O(n)。为了避免冲突可以使用long long级别的MOD+X或者双int甚至4int。哈希方法很多，需要子树顺序无关，如对子树哈希值进行求和，往往再组合子结点数量和子树大小。也可以用map<vector<int>, int>维护互异有根树及其编号，一个点的vector是其所有儿子的编号排序后的结果。由于1个点不可能出现在两个vector中，期望的查找复杂度为O(logn)。总的复杂度为O(nlogn)。分层标号的O(n)树同构算法AHU algorithm。
- 765E, [图论], 容易得出缩成一条链的充要条件是所有儿子内叶子深度相同，且儿子间不同深度最多只有两种。树形DP可以解决此题，但是比较麻烦。可以证明不同中心所得链本质相同；中心是否有解等价于整体有解。因此直接求出重心再统计叶子深度即可。O(n)。
- 765F, [数据结构], 方法很多。莫队算法可以通过巧妙地使用双端链表（解决了无法插入的问题）做到O(n^1.5)（sub-24907816）。另外可以用线段树离线维护，l表示区间[l,r]的解。每个r只有O(logn)个有意义更新。首先r左侧最右大于等于a[r]的位置y需要更新。之后要找一个小于y，大于等于a[r]的位置x更新。如果y-x<=x-a[r]，那么更新是没有意义的。因此每次差值都会减半，总共只有O(logn)个。y<=a[r]的情况也是同理。x和y的查找可以用权值线段树完成。O(nlog^2n)。另外还有一种奇怪的线段树做法，尚不清楚复杂度（sub-24886435）。
- 767E, [贪心], 实际上对于每件物品只有恰好支付和全部用纸币支付两种方式，前者损失ci个硬币，后者得到100-ci个硬币。先视为所有物品都全纸币支付，那么恰好支付就相当于消耗了100个硬币。所有物品等代价之后，就可以用后面的物品替换前面的物品得到更优方案（后面的物品用纸币支付不满值更大时）。从前往后维护当前选定的恰好支付的物品集合，以及当前剩余硬币。超过100个硬币时即使得当前物品恰好支付，否则尝试用当前物品替换之前的物品改进解。注意价格为100倍数的物品。O(nlogn)。
- 771D, [DP], 注意到'V'、'K'和其他字符这三个子序列内部的相对顺序不会发生改变，因此总交换次数可以分解为每个字符两侧其他种类字符的数量变化。例如VEK->KEV，三个字母对应的变化量都是2，因此总交换次数为3*2/2=3。dp(i,j,k,last)表示当前序列前缀由三个子序列的前i、j、k个字符组成，且最后一个字符的类别为last。记忆化搜索即可。O(n^3)。
- 776F, [几何, 树分治], 用farmland求出所有区间以及相邻关系，可以证明必定成树形结构。首先整棵树只能有一个1，其子树即为子问题，因为跨过1的点对都有1保证性质。于是直接用树分治过程处理，每次将当前深度赋给中心。O(nlogn)。
- 778C，[trie], 对每一个阶段，尝试合并其所有儿子，用类似线段树合并的方法做到O(S*SIGMA)。其中S是合并前后trie大小差，即结点合并发生次数。考虑将每个儿子合并到最大的儿子，则代价不会超过其他所有儿子大小之和，因此每个点被合并的次数不会超过其到根路径上所在子树不是最大子树的次数，即logn，因此从的合并次数为O(nlogn)。O(nlognSIGMA)。
- 778D, [构造], 考虑变成所有骨牌横放的形态。从左上角开始先行后列逐个调整。如果当前骨牌竖放，那为了进行调整，其右侧骨牌也必须竖放。如果右侧骨牌横放，则为了进行调整，其下侧骨牌必须横放，这样每个调整的阻碍都只有唯一后继（画图更明显）。注意列数为奇数时进行转置。O(n^3)。
- 785D, [计数], 枚举最内层')'的位置，左侧x个'('，右侧y个')'，因为当前枚举的位置需要固定，方案数为\sum{\binom{x}{i}\binom{y-1}{i-1}}=\sum{\binom{x}{x-i}\binom{y-1}{i-1}}，求和为\binom{x+y-1}{x-1}。O(n)。
- 786A, [博弈], 有向有环图上博弈，从确定状态倒推即可。O(n^2)。
- 788B, [图论], 将连通图所有边都恰好走过两遍的方案必定是回路，因此只走过一次的两条边只可能有公共点，或者至少一个是自环。O(n+m)。
- 788C, [DP], 注意到可以令<n的ai为n-ai，>n的ai为ai-n，然后令所选多重集和为0即可。可以用动态规划解决。dp(i,j)表示大小为i的多重集可以凑出j，转移需要枚举所有ai。对于任意一个解，总能令其所有前缀和均落在[0,1000]中，因此j取[0,1000]即可。O(n^3/bitset)。
- 792E, [数学], 将A分为g组，使得组间大小之差不超过1。那么显然每组至少是floor(A/g)。floor(A/g)只有O(A^0.5)种值，因此枚举任意一个ai的所有可行解，再O(n)判断即可。O(nA^0.5)。
- 797E, [分块], k>=n^0.5时显然可以暴力，k<=n^0.5时显然可以预处理。O(n^1.5)。
- 888G, [MST, Trie, 异或], 首先按照最高位将数分为两组，显然两组间有且仅有一条边，可以用二进制Trie求出。对两组递归处理。O(nlog^2A)。
- 889C, [组合], 考虑枚举n的位置，则需要求出对m=1..n，长为m且最大值在m处的排列中有多少错解，设为f[m]。考虑次大值的位置x，如果x<m-K，则最终结果不会超过次大值，否则需要1..x本身是一个错解排列。因此有递推式f[m]=(m-K-1)*(m-2)!+\sum_{x=m-K}^{m-1}{f[x]*(m-2)!/(x-1)!}。计算过程用前缀和优化。O(n)。
- 891C, [图论, MST], 在Kruscal算法过程中，同权值的边的顺序的变化不影响处理完所有该权值边之后点之间的连通性。因此此题中可以将所有边按权值排序后考虑。使用可撤销并查集维护即可。
- 891E, [数学, 组合], 注意到交换相邻操作不影响代价，可以递推得出单次代价和(\prod{a_i}-\prod{a_i-b_i}，其中b_i为操作次数。先不考虑前半部分，剩余部分期望为\prod{(a_i-b_i)/(b_i)!}K!/n^K对所有合法b_i求和。从生成函数角度看，相当于\prod{\sum{(a_i-k)x^k/k!}}中次数为K的项系数。化简得到\prod{e^x(a_i-x)}=e^{nx}\prod{(a_i-x)}。将e^{nx}再次展开，枚举后半部分各项系数。O(n^2)。
}}}

- 468C, [], 解法非常巧妙
- 519E, [LCA], 树上两点中点，LCA倍增法应用
- 570D, [DFS], 按高度分层后对DFS序二分，离线可在进出时分别统计答案做到O(n+m)
- 601D, [Trie], Trie树内部冗余合并。
- 609E, [MST, LCA, 倍增], MST之外边w与MST所成环上所有边权值大于等于w
- 611F, [], 枚举前2n步，之后选取关键点枚举。枚举前2n步时直接删除非关键点。
- 618E, [数学, 线段树], 坐标变换矩阵。还有其他做法@@
- 618F, [数学], 鸽笼原理
- 622F, [数学], 拉格朗日插值法
- 629E, [树形DP],
- 632E, [FFT], FFT计算幂可通过对点值表示法求幂加速
- 632F, [MST],
- 633F, [树形DP], 树上多链最大权值和
- 645E, [字符串], 相异子串计数，增量法（考虑子串结尾）。
- 645F, [数论, 计数], 枚举GCD。可以考虑对贡献去重和对集合去重。本题集合去重比较麻烦，贡献去重只需要求出phi(x)即可。
- 650D, [LIS], 对每个询问，求包含和不包含修改位置的LIS。
- 652F, [其他], 将蚂蚁相撞视为互换标号。
- 653E, [DS, 连通性], 禁止边并查集，维护连通块集合及对应点数，对当前点扫描禁止边，将全被禁止的连通块移出。
- 653F, [SA, 括号序列], 括号序列合法子序列的半区间查询（单点固定）和SA去重
- 653G, [组合计数],
- 660E, [组合计数, 字符串], f[n][m]可由f[n-1][m]求得，方法与644E相似。另外也可以计算每个串的贡献，只需令当前枚举子串为整个串“最早出现”的该子串即可。
- 662C, [DP, fwt], 根据交换操作的mask进行DP。
- 665E, [Trie], 将二进制表示视为串从高位到低位加入Trie，维护每个结点的串数进行统计。O(nlogn)。
- 666C, [数学], 正整数n的任意划分中，不同数的数量不超过sqrt(n)。对某个长度可以做到O(n)DP。总的复杂度为O(n^1.5)。
- 675E, [贪心, 单调队列], 从后往前贪心，维护一个关于a[i]的单调队列，选择[i+1,a[i]]中a[j]最大的一个，因为必然包含其他位置的所有选择。统计从后往前线性即可。O(nlogn)。
- 677D, [分块, BFS], 显然可以将每种箱子视为一个阶段，若上阶段点数大于n则BFS转移，否则点对点转移，每点均摊复杂度不超过O(n)。O(n^3)
- 677E, [对数], 枚举中心，对数比较保证精度。O(n^2)。
- 678E, [状压DP], f[i][mask] 表示已选 i，待选 mask 的最大胜率。O(n2^n)。
- 679C, [BFS, 尺取法], 线性维护当前范围内连通块和各种块数量。O(n^3)。
- 682E, [几何, 凸包], 找出面积最大的三角形，以其顶点为中点作所求三角形，必定包含所有点，否则可以构造面积更大的三角形。O(n^2)。
- 710F, [AC自动机, 二分], 用类似二项堆的方法维护多个AC自动机，暴力合并。O(Llogn)。
- 713C, [DP], 离散化取值后DP，O(nlogn+n^2)。还有一个与维护凸线相关的O(nlogn)做法。
- 715B, [图论, 二分答案], 先判断无解、已有解等边界情况，然后在待定边（顺序无关）上二分，得到将最大的前缀置零而大于L的位置，然后二分下一条边的取值。O(km(logn+logm))或O(mlogn(logn+logm))，取决于最短路。
- 715C, [数论, 树分治], 根据后缀计算相应合法前缀，O(nlog^2n)。
- 717A, [数论, 组合数转多项式, 带根号公式取模], 将组合数展开为多项式，问题即转化为fibonacci数列k次幂求和，可以对其通项公式等比数列求和。O(k^2logL)。
- 717F, [性质转化, 数据结构], 要求区间内奇偶位置和相等没有零，线段树数据域设计。O(nlogn)。
- 722E, [DP], 首先只需考虑经过特殊方块的次数。设f[i][j]为从i处出发，经过恰好j个特殊方块的路径数。则按照偏序关系求解f[i][j]时，所有经过次数>j的路径都可以根据倒数第j+1个经过的点归类统计。
- 723E, [欧拉回路, 消环], 连边构造欧拉回路。消环后DFS分配方向。O(m)或O(m^2)。
- 724E, [网络流, DP], 用动态规划求解特殊网络的最小割。O(n^2)。
- 724F, [DP], 通过重心将无根树转化为有根树，有根树计数可以用f[i][j][k]表示i个点j棵子树，子树大小不超过k且子树中的内部节点均满足度数要求的解的数量，DP即可
- 724G, [异或线性基], 图中任意环都可以通过连边的方式加入路径。O(m+nlogV)。
- 725E, [性质], 可以证明对于一个选择序列，合并其中任意两个之后所选硬币仍然不变。因此枚举加入的硬币面值即可。如果取硬币时相同面值一次取完，则最多sqrt(C)种不同面值，复杂度为O(sqrt(n))，可以预处理完成。O(C^1.5)。
- 727F, [DP], 从后往前DP求出[i..n]去掉j个后所得序列前缀和的最小值。询问可以二分求得。O(n^2+qlogn)。
- 731D, [字符串], 只需考虑相邻串第一个不同位置即可，对所有可行区间求交。O(c+L)
- 731E, [DP], 设dp[i]为1..i合并后i..n的先手最优解。O(n)。
- 731F, [数论], 枚举起点，为i时只有n/i段。O(nlogn)。
- 732E, [贪心], 对pi从大到小排序，当前最大socket匹配则解+1，否则给socket加一个转换器。O(nlog^2n)。
- 732F, [边双连通], 双连通分量按照tarjan算法的访问顺序即可变为强连通分量，剩下的树形结构被汇点所限制，因此全部指向最大值即可。O(m)。
- 733F, [图论, MST], 注意到在一个解中除了c[i]最小边之外其他边的c[]都是没有意义的，可以先根据w求出一个MST，然后枚举c[i]更小的边更新答案。从MST中选取路径最大边可以用LCA，也可以利用MST的特性。实际树结构上的路径最大值必定也出现在按秩合并的并查集的路径中，这是因为最大值在最后才加入，所有两连通分量间的路径都会经过它。O(m(logm+logn))。
- 735E, [树形DP], dp[u][i]表示点u为根子树的状态，i<=k表示最近黑点离根距离为i，否则表示最远未覆盖白点离根距离为i-k-1，转移时利用前缀和优化。O(nk)。
- 736D, [代数], 考虑完美匹配的矩阵表示，易见与询问与相应位置的代数余子式有关，可以通过逆矩阵求出所有代数余子式。O(n^3/32)。
- 737D, [DP], 一个简单的想法是用dp(l,r,k,p)表示当前为玩家p，上一步取了k个，先手取了l，后手取了r的最优结果。注意到整个游戏过程中两个玩家取走的数的个数差不超过k，因此r可以用r-l代替，状态空间变得相对密集，不需要hash。O(n^2)。
- 739C, [数据结构], 差分后用线段树维护。O(nlogn)。
- 741D, [数据结构], 启发式合并或者树分治。参见dsu on tree。O(Sigma*nlogn)。
- 743E, [DP,二分答案], 二分较小长度len，DP求最多len+1数量。dp(i,mask)表示前i个数，已选数为mask的最大值。O(n2^klogn)。
- 744C, [状压DP], 考虑将所有购买行为移到最后，就只是一个攒钱-购买的过程，于是求最多能省下多少货币。dp[mask][i]表示已经购买物品mask，省下i个red时，最多省下多少blue。O(n^3*2^n)。
- 746F, [尺取法, 数据结构], 容易证明满足尺取法所需性质，用数据结构按所节约时间维护曲目，转为数据结构上二分+求和。O(nlogn)。
- 748F, [图论], 总可以挑选一个点u，每棵子树中点数都<=k，因此答案必定为1。O(nlogn)。对于pair的求解，令同棵子树的点在序列中相邻，那么a[i]和a[i+k]必属于不同子树。
- 749E, [数据结构], 每对数相互独立，对于(i,j)，只有被所选区间完全覆盖时才有1/2概率反转。因此统计所有逆序对的被盖区间数，可以枚举j，计算所有i<j&a_i>a_j的i的和。O(nlogn)。
- 755E, [图论, 构造], 可以证明（https://math.stackexchange.com/questions/1929512/if-the-diameter-of-graph-is-greater-than-3-then-the-diameter-of-its-complement-g）不存在m<=1||m>=4的解，而m=2时红色边为1-n的链，m=3时2..n是以3为中心的菊花图，1再接到2上。O(n)。
- 755F, [贪心, DP], 最大值的部分贪心解决，最小值的部分即为背包问题。注意到最多只有n^0.5种不同物品，每一类再用多重背包的常用作法折半划分处理即可。一个粗略的上界是O(n^1.5logn/32)。可以证明一个更精确的界O(n^1.5/32)。另外一种是将物品按照大小分为<=T和>T两种，前者用O(nm)的多重背包存在性判定算法处理，后者用01背包处理并用bitset优化，复杂度为O(Tn+n^2/(32T))。
- 756C, [数据结构, 括号序列], 将push视为'('，pop视为')'，则问题转化为求出当前序列的最长合法后缀。将'('和')'分别视为1和-1，用线段树维护后缀和即可。O(nlogn)。
- 756D, [组合计数, DP], 只需关注没有相邻项相同的子序列，其他子序列可以“压缩”成这样的子序列。一个长为k的子序列对应C(n-1,k-1)个最终状态。因为要避免相邻项相同，容易想到用dp(i,j,c)来表示[1..j]中尾部为c，长为i的子序列数量。实际上状态可以进一步压缩。dp(i,j)表示[1..j]中以j结尾，长为i的子序列数量，转移时需要额外的数组。O(n^2)。
- 757D, [DP], 串长75最多只能构造m=20的解，因此状态压缩即可。因为要求中间段非零，每个状态转移最多只有五次。O(n*2^n)。
- 757E, [数论], 注意到递推式等价于f_{r+1}(n)=\sum_{d|n}{f_{r}(d)}，容易证明f_{r}满足数论积性，并且f(p^k)的值与p无关。由n的范围知k最大为19，因此可以预处理出所有r<=1e6,k<=19的f_{r}(p^k)，处理询问时做素因数分解即可。素因数分解可以用筛法预处理i的最小质因数md[i]将分解加速到O(logn)。O(rlogn+qlogn)。
- 758E, [贪心], 因为接近根的边副作用更小，所以先自底向上将整棵树重量最小化，然后自顶向下将边权扩展到极限。O(n)。
- 758F, [数学], 首项末项满足ax^(n-1)和ay^(n-1)的形式，且gcd(x,y)=1。因此枚举x和y计算a的取值数即可。O(n^(2*(n-1))logn)。
- 761F, [adhoc], 将每个和分为矩形内和矩形外两部分。矩形内只要统计每种字符的出现次数之和即可，因为第i幅图在矩形i中都是字符c[i]，差异为0，被包含也没有关系。对于矩形外的部分，相当于原图与其他变异图在矩形外的差异之和，由于原图和i在外部完全一致，为了统计方便可以包含i。于是相当于总的差异值减去所有图在矩形i内的差异值之和。所以只需要支持矩形内字符数的查询和矩形内差异值之和的查询。O(n^2SIGMA)。
- 762E, [数据结构], 统计对象有三个限制条件，关于fi的条件因为K过小可以暴力枚举，半径限制的一侧用数据结构维护，另一侧则通过从左往右扫描一遍维护进出解决。O(nklogn)。
- 763C, [数学, 随机化], 由于和固定，确定x即可求出d，然后暴力测试，对于不合法的情形，有(m-n)/m的概率测试失败，因此总的测试量是nlogn级别。另外在m<2n时如果有解，x+kd必定是最大的循环群，因此可以对序列取反，提高测试失败的概率。O(knlogn)。k为单次测试的复杂度。
- 763D, [树同构], 可以用哈希解决，复杂度为O(n)。为了避免冲突可以使用long long级别的MOD+X或者双int甚至4int。哈希方法很多，需要子树顺序无关，如对子树哈希值进行求和，往往再组合子结点数量和子树大小。也可以用map<vector<int>, int>维护互异有根树及其编号，一个点的vector是其所有儿子的编号排序后的结果。由于1个点不可能出现在两个vector中，期望的查找复杂度为O(logn)。总的复杂度为O(nlogn)。分层标号的O(n)树同构算法AHU algorithm。
- 765E, [图论], 容易得出缩成一条链的充要条件是所有儿子内叶子深度相同，且儿子间不同深度最多只有两种。树形DP可以解决此题，但是比较麻烦。可以证明不同中心所得链本质相同；中心是否有解等价于整体有解。因此直接求出重心再统计叶子深度即可。O(n)。
- 765F, [数据结构], 方法很多。莫队算法可以通过巧妙地使用双端链表（解决了无法插入的问题）做到O(n^1.5)（sub-24907816）。另外可以用线段树离线维护，l表示区间[l,r]的解。每个r只有O(logn)个有意义更新。首先r左侧最右大于等于a[r]的位置y需要更新。之后要找一个小于y，大于等于a[r]的位置x更新。如果y-x<=x-a[r]，那么更新是没有意义的。因此每次差值都会减半，总共只有O(logn)个。y<=a[r]的情况也是同理。x和y的查找可以用权值线段树完成。O(nlog^2n)。另外还有一种奇怪的线段树做法，尚不清楚复杂度（sub-24886435）。
- 767E, [贪心], 实际上对于每件物品只有恰好支付和全部用纸币支付两种方式，前者损失ci个硬币，后者得到100-ci个硬币。先视为所有物品都全纸币支付，那么恰好支付就相当于消耗了100个硬币。所有物品等代价之后，就可以用后面的物品替换前面的物品得到更优方案（后面的物品用纸币支付不满值更大时）。从前往后维护当前选定的恰好支付的物品集合，以及当前剩余硬币。超过100个硬币时即使得当前物品恰好支付，否则尝试用当前物品替换之前的物品改进解。注意价格为100倍数的物品。O(nlogn)。
- 771D, [DP], 注意到'V'、'K'和其他字符这三个子序列内部的相对顺序不会发生改变，因此总交换次数可以分解为每个字符两侧其他种类字符的数量变化。例如VEK->KEV，三个字母对应的变化量都是2，因此总交换次数为3*2/2=3。dp(i,j,k,last)表示当前序列前缀由三个子序列的前i、j、k个字符组成，且最后一个字符的类别为last。记忆化搜索即可。O(n^3)。
- 776F, [几何, 树分治], 用farmland求出所有区间以及相邻关系，可以证明必定成树形结构。首先整棵树只能有一个1，其子树即为子问题，因为跨过1的点对都有1保证性质。于是直接用树分治过程处理，每次将当前深度赋给中心。O(nlogn)。
- 778C，[trie], 对每一个阶段，尝试合并其所有儿子，用类似线段树合并的方法做到O(S*SIGMA)。其中S是合并前后trie大小差，即结点合并发生次数。考虑将每个儿子合并到最大的儿子，则代价不会超过其他所有儿子大小之和，因此每个点被合并的次数不会超过其到根路径上所在子树不是最大子树的次数，即logn，因此从的合并次数为O(nlogn)。O(nlognSIGMA)。
- 778D, [构造], 考虑变成所有骨牌横放的形态。从左上角开始先行后列逐个调整。如果当前骨牌竖放，那为了进行调整，其右侧骨牌也必须竖放。如果右侧骨牌横放，则为了进行调整，其下侧骨牌必须横放，这样每个调整的阻碍都只有唯一后继（画图更明显）。注意列数为奇数时进行转置。O(n^3)。
- 785D, [计数], 枚举最内层')'的位置，左侧x个'('，右侧y个')'，因为当前枚举的位置需要固定，方案数为\sum{\binom{x}{i}\binom{y-1}{i-1}}=\sum{\binom{x}{x-i}\binom{y-1}{i-1}}，求和为\binom{x+y-1}{x-1}。O(n)。
- 786A, [博弈], 有向有环图上博弈，从确定状态倒推即可。O(n^2)。
- 788B, [图论], 将连通图所有边都恰好走过两遍的方案必定是回路，因此只走过一次的两条边只可能有公共点，或者至少一个是自环。O(n+m)。
- 788C, [DP], 注意到可以令<n的ai为n-ai，>n的ai为ai-n，然后令所选多重集和为0即可。可以用动态规划解决。dp(i,j)表示大小为i的多重集可以凑出j，转移需要枚举所有ai。对于任意一个解，总能令其所有前缀和均落在[0,1000]中，因此j取[0,1000]即可。O(n^3/bitset)。
- 792E, [数学], 将A分为g组，使得组间大小之差不超过1。那么显然每组至少是floor(A/g)。floor(A/g)只有O(A^0.5)种值，因此枚举任意一个ai的所有可行解，再O(n)判断即可。O(nA^0.5)。
- 797E, [分块], k>=n^0.5时显然可以暴力，k<=n^0.5时显然可以预处理。O(n^1.5)。
- 888G, [MST, Trie, 异或], 首先按照最高位将数分为两组，显然两组间有且仅有一条边，可以用二进制Trie求出。对两组递归处理。O(nlog^2A)。
- 889C, [组合], 考虑枚举n的位置，则需要求出对m=1..n，长为m且最大值在m处的排列中有多少错解，设为f[m]。考虑次大值的位置x，如果x<m-K，则最终结果不会超过次大值，否则需要1..x本身是一个错解排列。因此有递推式f[m]=(m-K-1)*(m-2)!+\sum_{x=m-K}^{m-1}{f[x]*(m-2)!/(x-1)!}。计算过程用前缀和优化。O(n)。
- 891C, [图论, MST], 在Kruscal算法过程中，同权值的边的顺序的变化不影响处理完所有该权值边之后点之间的连通性。因此此题中可以将所有边按权值排序后考虑。使用可撤销并查集维护即可。
- 891E, [数学, 组合], 注意到交换相邻操作不影响代价，可以递推得出单次代价和(\prod{a_i}-\prod{a_i-b_i}，其中b_i为操作次数。先不考虑前半部分，剩余部分期望为\prod{(a_i-b_i)/(b_i)!}K!/n^K对所有合法b_i求和。从生成函数角度看，相当于\prod{\sum{(a_i-k)x^k/k!}}中次数为K的项系数。化简得到\prod{e^x(a_i-x)}=e^{nx}\prod{(a_i-x)}。将e^{nx}再次展开，枚举后半部分各项系数。O(n^2)。