个人练习一句话题解

所有题目按做出顺序排序。

练习链接。$(\textcolor{green}{10}/\textcolor{red}{26})$

做出顺序：VCTRLNEIAY。

V。简单模拟。但是看了好几遍都没读懂题，最后还是看了题解。map 即可。

C。发现不好 dp。数据范围很小，考虑图论建模。建出一个边权为 $0$ 或 $1$ 的图跑 dijkstra 即可。

T。简单模拟。拆一下位即可。但是不会证答案的范围，以为要跑很久，实际上就二十多万。

R。kruskal 模板。

L。发现 $1$，$2$，$4$，$8$ 都要被改掉，打表知 $2$ 的幂都包含它们，但 $65536$ 不满足这个条件。特判即可。

N。让最大的字母出现次数的最大值尽可能小，就尽可能平均分，向上取整一下，最后如果没有余数再把后面字典序最大的子序列接上即可。

E。正难则反，倒着放人，然后二分套树状数组进行模拟即可。

I。如果 $x$ 到 $y$ 有多条路径，那肯定会构成环，然后因为环上所有边的异或和为 $0$，所以每条路径必然相等，然后随便找一条路即可，比如 $x \to 1 \to y$，预处理一下即可。

A。悬线法模板。从这篇题解学会了。

Y。完全二叉树，所以深度很小，设 $t_{i,j}$ 是从第 $i$ 个点开始染色，向下染 $j$ 层的时间，$c_{i,j}$ 表示染的颜色，这样修改就可以 $O(1)$ 处理 $t$ 和 $c$，询问就把所有祖先的所有深度全枚举一遍，就有了跑不满的 2log，随随便便进最优解 Page 1。

练习链接。$(\textcolor{green}{6}/\textcolor{red}{26})$

做出顺序：CSNHBK。

C。除了左上 - 右下对角线外的都可以抵消，然后简单维护即可。

S。用个 map 直接模拟，然而有可能被两个都是变量的情况卡掉，多跑几次即可，测试结果是 4 次。

N。发现无论在放哪个频道，它的下一个频道是固定的，链表模拟即可，要什么图论。

H。究极诈骗，因为当 $n > 2$ 时，必然会同时有多个 $7$ 或 $9$，取 $7,7$ 和 $7,9$ 或者 $9,9$ 和 $7,9$ 就能辨识，所以 $n > 2$ 时没答案。

B。硬模拟，一个个插入即可。

K。先换再删一定不优，所以一定先把要删的删完，枚举删多少个，但是支持删除的数据结构很难搞，所以换一下，从大到小加进去，就是数逆序对了。

练习链接。$(\textcolor{green}{6}/\textcolor{red}{26})$

做出顺序：XMWVCF。

X。总数不会变，所以直接枚举总数的因数并模拟即可，$O(n \cdot d(sum))$ 轻松过。

M。防止四舍五入，就直接让 $A,B$ 是 $1000$ 的因数，取 $A = 200,B = 500$，然后就转成 $5a + 2b = c,a \le 200,b \le 500$ 的构造，随便构造就好。

W。可以转化为对 $1 \le k \le n$ 求 $\sum^{n}_{i = 1} \min^{i + k}_{j = i}$，相当于对 $1 \le k \le n$ 求所有长度为 $k + 1$ 的子串中的最小值之和。然后对每个数用单调栈求出左边第一个小于等于的，以及右边第一个小于的，这样 $(l, r)$ 内的任意子区间的最小值都是 $a_i$。接着数区间、拆贡献可以得到一个区间加等差数列的式子，二阶差分即可。然而暴力一阶差分好像也能过。思维难度不及代码难度的 $\frac{1}{10}$。

V。每个点最多只能被平推一次，所以最后肯定是一个一个小区间连着平推，且每次区间端点的 $h$ 都相同，这就转化成了数每个数的出现次数，开个桶数一下即可。

C。简单模拟，题面能不能写好一点。

F。根号算法 111 ！！！先考虑暴力，显然想求答案就需要求 $u$ 和 $v$ 的相邻节点的交集，直接 bitset 可以做到 60pts，但是 4e10 的 bitset 开不下，只能用根号分治进行优化：对于在询问中出现次数多的，放进 bitset；出现次数少的就暴力遍历相邻节点。可以做到 $O(\frac{n \times \sqrt{n}}{w})$！！！

练习链接。$(\textcolor{green}{5}/\textcolor{red}{26})$

做出顺序：AVNDT。

A。考虑枚举有几个人参战，然后可以得到答案是 $\sum^n_{i = 1} C^i_n \times (i - 1)$，随便推推或者放进 oeis 里搜一下就可以知道答案等于 $(n - 2) \times 2 ^ {n - 1} + 1$。

V。简单最短路，答案必然是 $\operatorname{dis}_{a \to b} + \operatorname{dis}_{b \to c}$ 或 $\operatorname{dis}_{a \to c} + \operatorname{dis}_{b \to c}$，取小的即可。

N。就是要去掉岛中湖中岛，先对最外层的大海八连通搜一遍，剩下的就必然是岛了（相当于把岛中湖填平），然后就是经典的四联通泛洪了。

D。直接暴力枚举基因对不太好做，考虑对于每个基因爆搜出与它能匹配的字符串集合，然后统计集合里有哪些字符串在给出的里面有就行了，因为长度只有 $8$，所以对每个字符串而言能匹配的只有 $C_8^4 \times 3 = 210$ 个，$8000 \times 210$ 是稳过的。

T。经典结论是每行 / 列最优情况下最多只会变一次，所以一旦确定了第一行要不要变，就可以确定每一列变不变，每一列确定后就一行一行地检验即可。