2026 年 7 月日祭

请在 Github 博客浏览完整的日祭。

树上处理技巧

Link

数据结构专题

Link

前情提要

U - 众数

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

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

线段树分治板子，懒得写了。
X - k-d-sequence

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

可持久化数据结构

Link

感觉没啥难题。

点分治、点分树

Link

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

J - 成都七中

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

TBD
Ex - Statistics on Tree

TBD

思维型题目选讲 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 - 歌唱王国

TBD
G - 弦论

TBD
H - 论战捆竹竿

TBD
I - 节日庆典

TBD
J - 字符串

TBD
K - Exam

TBD
L - Twilight and Ancient Scroll

TBD

数据结构综合1

Link

F - Joker

TBD
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

TBD
D - tdnmo

TBD
E - rsmemq

TBD
F - 烟花表演

TBD
G - 字符串问题

TBD
J - Souvenirs

TBD
K - Rainbow Triples

TBD
L - 简单数据结构

TBD

晚练

Link

消息查找 (20260701)

简单题，直接 DP 即可。
棋圣 (20260702)

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

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

简单题，二分即可。
苹果树 (20260708)

简单题，DP 即可。