个人练习一句话题解

· · 个人记录

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

2025.5

练习链接。(\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。

2025.6

练习链接。(\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。先换再删一定不优，所以一定先把要删的删完，枚举删多少个，但是支持删除的数据结构很难搞，所以换一下，从大到小加进去，就是数逆序对了。

2025.7

练习链接。(\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})！！！

2025.8

练习链接。(\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。经典结论是每行 / 列最优情况下最多只会变一次，所以一旦确定了第一行要不要变，就可以确定每一列变不变，每一列确定后就一行一行地检验即可。