总结

冬月廿四，明天小寒。看起来气温要骤降了。这周就要回去了。感觉地皮子都还没踩熟呢。人生好短暂。今天是模拟赛，做的是 DIV2。还行，就按照顺序来讲讲吧。有一个视频，题面就看视频里的吧我就不说了。

A. 最小四贪那树

给定一张完全图，有边权，次询问，每次询问一个点集，求出包含这个点集的最小权子图使得这个点集内所有点互相联通。。很容易想到求出每一个集合的最小生成树然后高维前缀和。（我也不知道高维前缀和是个啥，反正类似于递推）。这个不能暴力搞，会发现一定是把某一个点拿出来剩下点的那个加上两个连通块最小边。因为肯定有叶子节点（我不太清楚，感性理解）。预处理一下就能预处理然后直接询问了。

B2. 度数

这个是 div 2 的 B 题。就是给一个无向连通无自环图，然后要求你给每条边定向并输出方案，使得对于每个点都满足。其中。正解是先满足环，然后变成一个树。有一个 dp 的办法，但是很复杂。还可以对原图进行拓扑，每次加入度数为且没有满足限制的点，直到找不到。然后剩下的点要么是满足度数要求的要么在环上，跑个 dfs 树，然后从上往下连边，反祖边倒着连就可以。

然后讲一讲我的考场乱搞思路。其实也不算乱搞，可正解有点相似。就是从开始 dfs 出一棵树，然后从上往下连边，多余的从上往下连。现在除了根节点不满足条件的只可能是叶子的，不可能也为，否则就必须有两条边，有两条边肯定就往上面连就满足了。这个时候就将这一条边反转方向就可以。然后往上类似操作递归。但是我后来忘记考虑根的情况了……但是幸好数据很水，特别是图是树的情况，他的竟然都为就很不可思议。然后我的修补办法就是在 dfs 后如果根节点不合法就枚举儿子找到可行的那个反转就行。但是这样其实还是可以继续 hack 的……因为我没有继续往下递归，我也不想造数据了。所以就还有一个办法，就是如果有环，就直接拿一个环上的点当根，如果是树的话，那么肯定有一个点入度为 0，那么找到那个 x 为 0 的点就行了，不然肯定是不行的。这样应该是正确的吧。我猜测。

P.S. 最后那个我认为正确的做法我没有写……我就写了第二种可能可以被 hack 的方法，最后一种的话不想写了，嘻嘻。

B1. 数位

这个是 div 2 的 C 题。简单数位 dp 题目。不是很想描述题意，算了还是说一下。就是给一个不完全确定的数，还有个数，一个数的权值是每一位数字的权值和。让你找到一个使得所有的权值的和最大，求这个最大值。，位数同阶。但是我可能考场上脑子抽了……暴力的做法是枚举进位的数有哪些，然后转移。然后我硬生生地把 15 分的暴力用 bitset 和 unordered_map 给淦到了 80 分。正解就是发现进位是后几位排序连续的进位就行了。其实考场上我差一点就想到正解了，因为我发现 unordered_map 转移状态的最大数量是和差不多大的我就感觉应该是有顺序的，但是我只关注了上一位的大小关系，所以没有想出来，结果是要之前所有位排序的大小关系……很棒。这个排序也很方便，因为前面排好了，所以相当于几个关键字排序。可以使用 stable_sort，当然可以使用更简单的基数排序法，应该是这个名字，就是后缀数组的那种方法。

C. 树与

这个是原题，名字是：《关于因为与去年互测zjk撞题而不得不改题这回事》 。LOJ 和 QOJ 上面都有。你之用输入一个 《 就能找到这道题目。大意就是一个树每个点有一个权值，然后多次在线询问某条链上选择个点相与的最大值。详细可以看命题报告，很详细。这里讲一种最好写的方法。由于很小，且随机，则可以大致看成 6 左右。然后注意到一条链上最多只用取最大的个权值就行，抽屉原理。用主席树维护，每次询问暴力把这些点取出来，然后一位一位找，一位如果能是 1 就把是 0 的从数组中删去。这一步的复杂度大概是的，但是大概率卡不满。写的好的话还是能过的。复杂度。但是能过。

后记

今天又要结束了。晚安。还是要注意保暖，毕竟春天还有一会才回来。坚持住。这周就要回去啦话说，原因是因为打游戏，不能很好监管就把我们叫回去了。还是得有坚定的信念和高效的执行力与规划能力啊。哈。祝好。大家新年快乐！