A 牛妹的游戏

不妨假设绿方已经控制了所有蓝方没有控制的链，此时存在一个结论：当 时答案必定为 yes。这就是拉姆塞结论，下面给出简单证明：

假设 个据点分别为 ，那么在 连向其它据点的控制链中，必然至少有 条链被同一方控制，不妨假设它们为 。如此一来只要 中有任意一条链也被这一方控制，则可以形成控制区域；如果这三条链都没有被这一方控制，也就意味着它们都被对方控制了，则它们同样可以形成控制区域。

于是这道题只有在 时会出现答案为 no 的情况，这部分直接暴力判断即可。

B 病毒扩散

问题可以转化为以下模型：

多次询问从点 出发，每个时刻可以选择将 坐标或 坐标增加 或不走动，时刻 走到点 的方案数量。

如果要在时刻 走到点 ，那么必定有 个时刻选择走动，共有 种方案。

同时，走动的 步中有 步需要将 坐标增加 ，其余的需要将 坐标增加 ，共有 种方案。

于是答案即为 ，预处理组合数可以做到 查询，总时间复杂度为 。

C 牛牛染颜色

这是一道树形dp。

我们记 表示选择/不选择 这个节点后以 为根的子树的合法方案数。

我们分开来转移：

• 若选择 这个节点，则子树内可以随便选点，那么转移方程就是：

• 若不选择 这个节点，则只能选择其中一颗子树的节点或者一颗都不选，否则在 的子树内就会存在两个点 使得 ，这样就不满足题意了。

注意： 包含空集的方案，所以在枚举子树统计的时候每颗子树贡献的答案要减 ，但最后也要把空集的情况算上，还要加个 。

转移方程就是：

这样就能在 的时间复杂度内解决本题。

D 牛牛的呱数

首先这道题题目很容易联想到 dp，但是由于拼接顺序是不确定的，dp 是有后效性的。

但是我们可以把 dp 的状态变成节点，转移边做带权边，跑最短路。

我们可以这样设计节点：

一个二元组 表示 ，( 是数字串 的串长) 且数字串 的值 后的值为 。

对于每个串可以这样连边：(设长度为 ，模 后的值为 )

对于每个 连向 ，边权为 。

还要建一个超级起点和超级终点，超级起点连向各个只有一个串的状态，每个 的状态连向超级终点。

直接连边用 Dijkstra 算法跑最短路即可。

由于边数是 级别的，所以时间复杂度：。

E 水灾

根据题目中所说："将图中所有所有边权小于等于 x 的边删除"，不难想到可以把原图的 Kruskal 重构树建出来，

那么原题就转化为：在重构树上删去若干个点，使得被询问的点互不连通。

由于 Kruskal 重构树的性质：每个节点的权值肯定小于等于它的子树中任意一个点的权值，可知删去重构树上的点深度越小越好。

最优情况可以是删去所有任意被询问两点的 。

由于我们只需要知道这些被删去的点中点权的最大值，所以我们只用知道把被询问点按照 dfs 序排序。

那么每组询问的答案就是排序后所有被询问相邻两点的所有 的点权的最大值。

非相邻两个被询问点的 一定是某相邻两点的 的父亲，它的点权一定不是最大的，所以就不需要查询。

时间复杂度：。

F 牛牛的繁星

根号科技练手好题，难度并不是很大。

离线做法

考虑使用莫队，维护每个数的出现次数，然后使用平衡树维护出现次数，每次挪动端点至多改变 个出现次数，因此复杂度是 的，总时间复杂度为 。

一些优化

仍然考虑莫队，这次我们想办法去掉平衡树的 。考虑别的什么方法维护出现次数，可以做到 单点修改，并可以在不超过 的复杂度内查询第 大，显然有一个值域分块做法。

我们考虑对出现次数分块，然后维护每个出现次数的个数，以及块内所有出现次数的个数，修改时只会改动 的信息，查询时从大到小枚举整块，然后在块内枚举出现次数即可，总时间复杂度为 。

强制在线

有很多做法，我介绍其中一种做法。先序列分块，考虑维护前缀块中每个数的出现次数。

再考虑将数分为两类：出现次数大于 的，我们称为 A 类数；出现次数小于等于 的，我们称为 B 类数。可以发现，A 类数至多只有 个。

考虑维护两两块间出现次数为 的 B 类数分别有多少。查询的时候先查整块中出现次数为 的 B 类数的个数，然后枚举 A 类数，将出现次数小于等于 的也算到前面，剩下的留下来。接着扫描散块，如果是 B 类数则算入前面的贡献，否则像之前处理 A 类数一样分开。

最后我们得到了若干 A 类数，它们的出现次数一定大于 ，用我们刚刚优化莫队的那个查询第 大的技巧处理这部分即可，剩下的数出现次数必然在 间，暴力枚举即可，总时间复杂度为 。