Codeforces Round 1842 F题 *2500

观察到对两边取最大值再相加的操作，可以联想到树的带权中心问题。这样，每条边的贡献就是k减去两倍的子树节点数。

由于题目要求最大值，选择中心作为根节点即可得到最大值。

因此，我们可以枚举一个根节点，然后计算每个位置染色的贡献，最后排序得到结果。

Codeforces Round 1842 G题 *2800

本题解法十分巧妙，首先需要运用乘法分配律展开给定的表达式。

初步思路是对于选中的v的数量，绘制垂直柱状图，但发现这种方法难以处理。

转而考虑绘制水平柱状图，对于每个需要选择v的位置，有两种情况：一种是该行前面已经选择了v，另一种是重新开始一行。

设计动态规划状态f[i][j]，表示前i个元素中，有j行已包含元素的和，直接进行状态转移即可。

Codeforces Round 1842 H题 *3000

初步思路是枚举一个大于1/2的集合，将其分为两个子集。集合内部的条件无需考虑，只需处理中间的限制条件。这些限制条件可以将小于1/2的元素转换为1-a_i，然后整体排序，发现每个限制条件对应排序后序列的一个先后关系。

这相当于对拓扑序进行计数。

然而这种方法复杂度过高，两部分均为O(2^n)。

采用联合动态规划的方法，按照排序后的序列逐个选择元素。如果确定当前元素属于小于1/2的集合，则已选元素中不能存在与大于1/2的限制条件冲突的情况，大于1/2的集合同理。

这样可以将复杂度降至O(n2^n)。

UOJ462题

读完题目后会发现解法相对直接，但似乎其他选手花费了较长时间。

一条重链显然是从一个节点出发到叶子节点的路径。

容易设计出O(n^2)的动态规划解法：f[i][j]表示i子树内，重链从i到j的最小值。

注意到转移过程类似于链旁边毛毛虫结构的和，因此考虑在DFS过程中维护每个叶子节点对应的DP值，仅需进行区间修改，使用线段树即可实现。

UOJ164题

本题思路较为简单，但需要维护操作标记。将下传的标记改为加上一个数并与另一个数取最大值，三种修改操作都可以表示，且可以直接合并。

P6242题

本题难度较高，代码量达3.67k。

学习了beats算法，即处理区间取最大值操作时，可以维护区间最小值和次小值。当修改值介于这两个值之间时，对最小值进行区间修改，否则递归处理。

本题思路相对简单：在区间取最大值时对区间最小值进行区间修改操作，同时还需要维护历史最值，因此需要设置多个标记。

关于线段树空间优化的技巧：

#define mid ((l+r)/2)
#define ls mid*2
#define rs mid*2+1

这样只需两倍空间即可。

LOJ3495题

本题等价于带权重心问题。

通过简单证明可以发现，满足条件的点一定位于一条链上。直接使用点分治求解，没有太多细节问题。也可以使用DSU on tree等方法。

LOJ6892题

本题与回转寿司问题相似，但修改操作是全局的，且数据范围不支持分块处理。

采用类似思路，观察到修改操作经过一个区间时，对区间和的影响是将新数加入并移除最小值。同时发现操作顺序不影响结果，因此可以将操作放入堆中与区间内的数合并。

对于查询操作，相当于将[1,l-1]区间内的数与堆中的数合并，移除前(查询个数)个元素，再与[l,r]区间合并，选出r-l+1个最大的数作为答案。

具体实现时，使用主席树二分得到最终答案的数值区间并求和，查询的堆使用权值线段树维护。

初始实现采用二分后查询，复杂度为O(n log² n)，导致一个点运行20秒。改为在主席树上直接二分后，复杂度降为O(n log n)，运行时间减至7秒，但由于线段树查询次数多，常数较大。

经过多次优化，终于通过所有测试点。卡常技巧如下：

void Ad(seg, int x, int z) {//AC
  s[p] += z, sum[p] += 1ll * x * z;
  if (l == r) return;
  x <= mid ? Ad(lid, x, z) : Ad(rid, x, z);
}

void Ad(seg, int x, int z) {//TLE
  if (l == r) {
    s[p] += z, sum[p] += 1ll * l * z;
    return;
  }
  x <= mid ? Ad(lid, x, z) : Ad(rid, x, z);
  s[p] = s[ls[p]] + s[rs[p]], sum[p] = sum[ls[p]] + sum[rs[p]];
}

这是普通的线段树单点修改操作，上面版本在递归过程中直接修改，下面版本是修改叶子节点后向上更新。

UOJ180题

签到题。不合法的情况是指集合A中较小的元素在较大元素之前，但在集合B中跑到后面去了。使用树状数组即可维护。

UOJ181题

本题质量较高。

最初考虑使用容斥动态规划，但发现根本不需要。因为竞赛图缩点后形成链，且询问的是强连通分量数，因此直接枚举割集并累加即可，暴力枚举复杂度为O(m2^n)。

然后考虑与m相关的复杂度算法。

枚举对答案有贡献的边，会发现可以将图划分为若干连通块，每个连通块对应一个二分图。由于其他边概率均为1/2，可以使用背包合并计算答案，复杂度为O(n²2^m)，但仍无法通过。

结合上述两种方法，由于可以将连通块分开处理，找出原图的每个连通块单独求解，而一个连通块最多只有m+1个点，因此直接枚举割集即可，然后合并。

最终复杂度为O(n2^m + n²)。

UOJ182题

不会多项式相关内容。

UOJ186题

需要被删除的节点，需要找到左右比它小且不能被删除的节点，然后检查这个区间内比它大的节点数量。

使用离线算法和并查集即可解决。

UOJ187题

较为常规的斜率优化问题。

UOJ188题

阿拉丁的题目，有时间再做。

UOJ193题

首先考虑生成树计数方法。

可以使用矩阵树定理，也可以直接使用状态压缩。

具体来说，对于集合S，取出最小和第二小的两个点x和y，以x为根，枚举y所在子树的集合，然后合并，复杂度为O(3^n)。

然后考虑基环树计数。

基环树等价于每个节点指定一条出边，即度数之积。可能不连通，因此需要容斥，且可能将重边误认为是基环，直接减去生成树个数乘以边数。最后由于环有两个方向，结果除以2。

这部分复杂度为O(n2^n + 3^n)。

最后考虑贡献计算，即染色问题。所有节点可以染黑白，但叶子节点不能染黑。

使用容斥，枚举染黑的叶子节点集合即可。

这部分使用DFS，复杂度可达O(3^n)。

LOJ3806题

本题难度较高。

首先将不在1到n路径上的点去除，可以通过构建圆方树实现。

对于剩余边，如果一条边不在任何最短路径上，则必然存在"远路"。

否则，一条可以走远路的边(x,y)满足存在1→x→y→n和1→y→x→n两条路径。

可以证明不存在这种边的图是一个"西瓜图"，即起点和终点之间有若干条链，每条链上可能有类似结构。

但判断方法并不明显。

实际上有一个重要性质：度为2的节点可以直接删除。

不断缩点，如果最后只剩两个节点，则说明没有远路。

Codeforces 1168D题

首先考虑一个简单的动态规划：从下向上遍历，统计子树中相同字母链的最大长度，然后合并即可。

答案是将所有字母数减去最长链长度，即可得到问号数量。

唯一的问题是可能存在一个节点的字母总数超过最长链长度，此时无解。

正确解法是注意到叶子节点深度相同，因此可以将无分支的链合并，剩余树高为√n，直接暴力处理即可。

比赛中未观察到这一性质，采用强力维护方法，修改的贡献相当于修改一条向上的链，可以使用倍增检查，修改时使用树剖。

Codeforces 1845F题

观察发现，i和j碰撞的条件是t(a_i+a_j) mod 2l=0或t(a_i-a_j) mod 2l=0。

通过卷积求出a_i+a_j和a_i-a_j的取值。

然后相当于有一堆k，需要满足t=x(2l)/k（x为正整数）才是合法的。

注意到k的合法集合包含k的因数，因此将所有因数也加入集合，然后开始容斥，减去可以被自身因数表示的部分。

复杂度为O(n log n)。

AtCoder Beginner Contest 309 Ex题 *3029

解法十分巧妙。

一个询问都无法直接处理。

通常做法是直接容斥，走到上下边界，但这样复杂度爆炸。

仍需考虑多项式方法，每次将0和m+1项移除。

一个巧妙的方法是将问题放到长度为2m+2的环上，然后在另一侧放置对称的-1，这样相互抵消，直接卷积即可。

Codeforces 1835D题

k值很大，提示我们可以随机行走。

大致证明：如果有多条路径，长度分别为a₁,a₂,a₃,...,aₙ，放在同余最短路径上，最大只会有a₁aₙ，即n²级别，远小于k值。

先进行强连通缩点，需要找出所有路径长度的最大公约数，这不易求解，但最大公约数可以做差。因此枚举一条边，可以得到1→y和1→x→y的差，枚举所有边即可得到最大公约数，然后答案即可求解。

AtCoder Beginner Contest 308 Ex题 *2861

本题解法逆天。看错题意后通过，以为是数据水，后来发现可以证明与原问题等价。

将问题视为边不能在环上，利用求最小环的套路，相当于找到连出去的点，即除该点外的所有点都加入Floyd算法计算。

这可以通过线段树分治或分块实现O(n³√n)或O(n³ log n)的复杂度。

为什么这与原问题等价？因为如果一条边连向环上的点，就可以缩成一个更小的"Q"。

O(n³)的解法也不难，因为连出去的边只可能是最小的三条边之一，因此枚举这条边，删除后跑单源最小环，这可以用Dijkstra算法实现O(n²)的复杂度。

AtCoder Beginner Contest 307 Ex题 *2754

模板题，卷积匹配通配符。

AtCoder Beginner Contest 306 Ex题 *3335

比赛中只有一名日本人通过，其余是中国人，看来DAG容斥套路已被广泛掌握。

最终图是一个DAG，使用容斥找出入度为0的点，这些点之间必须都是"="，然后找出连通块数量，容斥系数为(-1)^(c+1)，直接动态规划即可。

P4770题