2026 年 7 月日祭

树上处理技巧

Link

数据结构专题

Link

前情提要

• U - 众数

  挺牛的。首先容易想到一个分块做法但是不太能过。发现若块长从右往左相邻两项翻倍，这样查询的复杂度是均摊线性的了。

• V - 生产计划 (Day 2)

  显然从全取 依次加到全取 就能取到所有答案。考虑怎么维护加的过程和处理询问。显然可以一个个点地加到 并维护当前权值，那么处理询问时可以二分到取 的前缀，再对当前正在加的点讨论。发现一个点对答案贡献的时间段显然是一个后缀，那么只要求出后缀就好做了。考虑怎么维护，发现按 DFS 序加点就可以换根 DP 解决。做完了。

• W - Communication Towers

  线段树分治板子，懒得写了。

• X - k-d-sequence

  大概就随便维护一下吧，懒得写了。

可持久化数据结构

Link

感觉没啥难题。

点分治、点分树

Link

点分治是简单的，但是之前不太会写。点分树也是简单的，大概就是可以用来处理一些动态的、只与树上距离有关的题。

• J - 成都七中

  好题。考虑点分治，并令要求的连通块中在点分树上深度最小的点作为代表元，容易证明这个点的子树完全包含要求的连通块。考虑对于某个询问判断两点是否在同一连通块中，那么显然求一下路径上点编号的最值即可。那么接下来是好做的，离线下来类似区间数颜色地维护即可。

• K - rdCcot

  卡常题 /ll。令连通块中 bfs 序最小的点做代表元，容易证明这样是对的。接下来点分治 + 线段树或平衡树维护出每个点的贡献区间，再二维数点即可。

• Ex - Statistics on Tree

  好题但屎。首先 的答案由五部分组成，容易发现当 即 时其一定是最大值。看到 考虑以重心为根，那么对于 不是根的点对的答案就一定是上面这个东西。对于这一部分，直接做是 的，可以把 放到桶里再暴力枚举，可以证明这样是 的。考虑 是根的情况，发现此时还是不能直接枚举 与 。发现当 与 都不是根的重儿子时答案也一定是上面这个东西，这一部分可以如法泡制。对于 或 是重儿子的情况，钦定 是重儿子并枚举 ，这部分也是容易维护的。

思维型题目选讲 1

Link

• D - 字符串

  好题。题面让你反转就放一个反串在后面，接下来尝试转为比较后缀的大小，然而发现这样会多算，发现多算的部分是个回文串，对于两部分分别处理即可，是一个扫描线的形式。也可以 bitset 大力 DP 过掉。

• H - Nim 游戏

  TBD

• I - Minimizing Edges P

  TBD

• J - 蔬菜

  TBD

• K - 序列

  TBD

思维型题目选讲 2

Link

好难啊。

• A - Half Queen Cover

  一个 的区域有 条对角线，那么在矩形左上角 的区域构造一个排列使得恰好能覆盖右下角的 区域即可。

• B - Weighted Mean

  把平均数确定下来之后形式优美了许多，那么考虑令平均数为中位数，于是可以正负两两匹配。 是奇数时就做完了，考虑 是偶数的情况，发现 时可以如法炮制，于是考虑 的情况。发现 时无解。考虑令 是平均数，此时正数比负数多了一个，那么令 并令 ，即把这两个正数合成一个，发现不会影响原有的性质，但要求 是独一无二的（除了 ），可以通过调整配对来满足条件。发现此时可能无解，那么令 为平均数再类似地做一遍即可。可以证明两种情况中一定有解。

• D - Cookies

  考虑判定一个确定的盒子序列是否合法。将盒子从大到小排序，那么对于每个 要求 ，可以通过 Hall 定理证明这是充要的。发现直接 DP 不好做，考虑可达性 DP，设 表示选到 一共 个盒子且和为 是否可行。注意到 只用开到 且可以 bitset 优化，时间复杂度 。

• E - 序列变换

  好难啊。注意到这个操作极其抽象，考虑把它变得正常一点。建出括号树，那么操作二说明儿子无序，操作一形如把 变成了 ，代价与 的权值有关。对 分讨一下，贪心即可。

• F - 楼梯

  TBD

• G - 山河重整

  TBD

• H - Conquer The World

  TBD

• I - Non Arithmetic Progression Set

  TBD

• J - Distance Ranking

  TBD

• K - Manhattan Max Matching

  TBD

• L - Bears and Juice

  TBD

• M - Two Characters, Two Colors

  TBD

• N - Variance Challenge

  TBD

• O - Sonya Partymaker

  TBD

动态规划

Link

• E - Tree Coloring

  不错的题。考虑容斥，那么需要对 求出在树上选 条从父亲到儿子的边使得每个点的出度都不超过 。这东西是一个多项式乘法的形式，可以直接分治 NTT；也可以按一次项系数归类，先通过组合数算出每个系数的结果再从大到小卷积，容易证明这是单 的。

• F - 喜爱之钥

  好难啊。令第一个人用钥匙 和锁 且没开，手模一下第二个人的选择，发现用钥匙 和非锁 或用非钥匙 和锁 的成功概率都是 ，而用非钥匙 和非锁 的成功概率是更低的；假如第二个人用了钥匙 且没开，那么感性理解接下来的人会继续用钥匙 ，用了锁 同理。继续讨论，发现每个人成功的概率都是 ，而成功或失败后就到了一个没有任何附加信息的新的状态，于是 DP 即可。

• G - 公交线路

  TBD

• H - Min Product Sum

  TBD

• I - 机器人

  TBD

• L - A New Beginning

  好题。首先显然只会操作二四象限的格子。考虑一个点到所有点的切比雪夫距离与路径，发现在 过该点的斜率为 的直线与路径的交点处 操作是最优的。于是按直线的截距排序就可以 DP 了。发现 DP 具有凸性，那么维护一下斜率变化的点即可。

• Ex1 - Zigzag

  TBD

• Ex2 - The Maximum Prefix

  TBD

图论与网络流

Link

• D - Max Vector

  不会网络流 /ll。考虑最小割，对于单个变量限制 是好做的，直接给每个值一个点再连一条从源点到该值的流量为正无穷的边即可。对于本题中两个条件满足其中之一的情况，令 部分的权值是从大到小连的，那么让 即可，其中 是一个虚点且边权均为正无穷。

• F - 图函数

  对于 ，若判定到 时不合法，那么它也一定不能对后面的点贡献，因此同样可以删掉。那么 的含义就是有多少个点对 使得 之间可以通过编号 的边互相到达。要求的每次删边过后的结果，把它倒过来改成一条条加边。发现这东西可以从大到小加点跑 Floyd，差分维护即可。卡卡常能过。

• G - 复兴计划

  TBD

• H - 拉丁方

  TBD

• I - Upgrading Cities

  好题。注意到拓扑排序中任意时刻队列中的点都是一个独立集，那么根据队列大小讨论一下即可。

• J - 棋盘游戏

  TBD

• L - 16 Integers

  TBD

省选模拟赛 20260720

Link

• A

  咋是雨后屋檐的严格弱化版（除了合并要拿个数据结构维护之外）。

• B

  容易写出贪心，我们希望有一个能用矩阵乘法表达的转移，发现贪心并不行。考虑问题的本质是求二分图最大匹配，其等价于最小点覆盖，发现后者可以直接 DP。那么剩下的就是简单的了，分块即可。因为卡空间所以要把询问离线下来。时间复杂度 。

• C

  我好菜。首先需要观察到答案是「对于每个距离，到原点为该距离的点数」的最大值。容易算出取到最大值的距离，那么接下来是一个硬币购物的形式。看到 于是果断考虑折半。具体地，对容斥后的式子做一个范德蒙德卷积的逆即可把两部分拆开，注意此时要把组合数视作下降幂的形式（即允许负数）。然而合并两边时是不允许负数的，因此需要双指针一下。时间复杂度

复杂字符串

Link

• E - 歌唱王国

  好神人的题。通过一些神秘的分析，可以发现答案是 。

• G - 弦论

  TBD

• H - 论战捆竹竿

  好题。直接做是一个同余最短路状物，但是边数是 的。考虑 Border 的性质，将其划分为 个等差数列，对于每个等差数列可以以首项为模数跑同余最短路，转移是一个单调队列的形式。发现不同等差数列的模数不同，需要转换模数，然而这部分也是容易的，直接再跑一遍同余最短路即可。直接转圈就是 的。

• I - 节日庆典

  TBD

• J - 字符串

  TBD

• K - Exam

  考虑枚举较长的串，那么对于每个位置，至多只有一个较短的串以该位置结尾。称一个短串的一次出现是合法的当且仅当它不被其它串包含（指在长串中的下标区间）。注意到一个短串是合法的当且仅当它在长串中的每次出现都是合法的。出现次数与合法的出现次数都是好算的，做完了。

• L - Twilight and Ancient Scroll

  TBD

数据结构综合1

Link

• F - Joker

  删除一个区间可以转化为，将原序列复制粘贴一次，查询一个区间。做完了。

• H - Sum of Prefix Sums

  TBD

• J - Kingdom of Criticism

  TBD

• K - EI 的第六分块

  TBD

• L - Anagram Paths

  TBD

• Ex1 - Clubstep

  TBD

• Ex2 - Number of Components

  TBD

数据结构综合2

Link

• A - rplexq

  好屎。发现树的度数较小的时候是好做的，于是考虑根号分治。设阈值 ，对于点 ，取它前 大的儿子直接做（用分块维护）；对于剩下的儿子，可以转化为区间数相同颜色对，于是可以莫队。取 ，那么第一部分的复杂度显然是 的，第二部分容易分析出序列长度的总和是 的，于是一共是 。然而实测 过不了，取到 跑得比较快，甚至取到 都能过，而 的理论复杂度是 的。

• D - tdnmo

  TBD

• E - rsmemq

  TBD

• F - 烟花表演

  TBD

• G - 字符串问题

  TBD

• J - Souvenirs

  TBD

• K - Rainbow Triples

  TBD

• L - 简单数据结构

  TBD

省选模拟赛 20260726

Link

• A

  简单题，可以看成一个高维超立方体构造。

• B

  简单题。正难则反，看成从 变到指定的排列。发现我们要把 挪到 ，这就说明了这个区间中相邻两个操作的操作顺序。随后直接 DP 即可。

• C

  TBD

组合计数与DP1

Link

• B - 树的遍历

  好题。 时是容易的，考虑 时为什么会算重，发现一棵树可能从多个根生成，而这些根一定构成一条叶子到叶子的路径。于是问题转化为了求叶子到叶子的路径数量使得路径上至少有一个根，简单树形 DP 即可。

• E - 卡农

  设 表示选 个数合法的方案数，考虑人工容斥，发现只与前两项有关，于是递推即可。

• F - 看电影

  发现链上很难求，考虑在末尾加一个座位变成环，再找一个断点，那么方案数就容易算了。

• L - 异或图

  TBD

• M - 成绩比较

  可以把答案分成分配每个人和他的关系的方案数和分配分数的方案数，这两部分都可以容斥解决。

省选模拟赛 20260728

Link

• A

  简单题，离线下来树状数组维护即可。

• B

  /bb。第一问是好做的。对于后两问先求出 SA，那么转化后的题意是：给定 个询问 ，对于左端点为 、右端点在 中的区间求答案。容易发现一个左括号匹配的右括号是确定的，因此可以从左括号向右括号的下一位连边，连出来是个链的形式。对于第二问倍增一下即可，对于第三问建出单调栈树再倍增即可。

组合计数与DP2

Link

• A - 代码拍卖会

  好题。可以把这个数看成若干个每位都为 的数相加，而这样的数在模意义下显然是有循环的，那么把取模后的值对应多少个取模前的值处理出来再 DP 即可。

• D - Beautiful Bracket Sequence

  好题。考虑答案一定是 ((...()...)) 的形式，那么枚举一下重点对两边求组合数再范德蒙德卷积即可。

数学综合1

Link

学了一些之前不会的板子。

省选模拟赛 20260731

• A

  好难啊，递归构造即可，场上做了 2.6h。

• B

  简单题，莫队 + 链表维护一下即可，我说这个远小于 A。

数学综合2

Link

晚练

Link

• 消息查找 (20260701)

  简单题，直接 DP 即可。

• 棋圣 (20260702)

  好题。注意到非链的情况都可以贪心构造，于是对链大力 DP 一下即可。

• 贸易 (20260704)

  并非困难，咋没写出来。把向下的边拆成 条那么向下的路径就只会经过向下的边了。

• 种树 (20260706)

  简单题，二分即可。

• 苹果树 (20260708)

  简单题，DP 即可。