2026 年 6 月日祭

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

数论进阶

Link1 Link2

• A - Fraction Floor Sum

  数论分块板子。

• B - DZY Loves Math IV

  观察到 很小，因此考虑对每个 求答案。设 ，可以大力推式子推出一个递推式，记搜即可，边界条件是 ，还要写个杜教筛。时间复杂度能过。

• C - DZY Loves Math VI

  推式子即可，稍微精细实现一下就能做到 。

• D - 数字表格

  首先拆贡献，再推一下式子，预处理出 再数论分块即可。

• F - 杜教筛

  有点神奇。对于数论函数 ，构造数论函数 使得 ，且能在较低的时间复杂度内算出 的前缀和。可以对 写出一个有关 的递推式，那么对小数据预处理出答案，对大数据记搜即可，时间复杂度平衡下来是 。

• G - 简单的函数

  对于积性函数 ，若有积性函数 使得 ，且对于任意质数 均有 ，那么有 ，因此 仅在 PN 处有值。要求求 的前缀和，可以利用杜教筛，那么只需要快速求 的前缀和与 的单点值。因为 PN 的数量是 的，因此枚举 PN 即可。

• H - 循环之美

  推推式子，随后整除分块 + 杜教筛即可，需要一些想象力。

NOIP 模拟赛 20260606

Link

• A

  赛时不会。记录一下从每一列丢下去的路径，丢一个石头后显然只会占掉路径的末尾，那么暴力更新一下即可，复杂度是对的。

• B

  从大到小枚举边然后转移，过程类似于拓扑排序。

• C

  对于单独一边显然是好做的。先不考虑矛盾的边，对两边直接做再直接合并起来，再判一下即可。

• D

  注意到任意时刻草的高度都单调不降且每次割的是一个后缀，因此草 被割的时刻包含于草 被割的时刻，同时一棵草第一次被割之后就会进入循环。考虑求出每棵草第一次被割的时间，接下来只要再求出每一刻所对应的后缀，就容易求出答案。后者显然是好求的，考虑怎么求前者。对于草 与一个时刻 ，若它会在时刻 被割，那么求出它在时刻 第一次被割的绝对时刻 ，那么它第一次被割的时刻显然 。容易想到二分，但是发现不太好做。发现要求的东西形似斜率优化，因此拿线段树维护区间的凸壳再线段树二分即可。

Codeforces Round 1102 (Div. 2)

Link

• E - Vlad, Misha and Two Arrays

  每次需要找到区间最大值，注意到拿两个指针往中间扫的时间复杂度是对的。

• G - Stripe, Token and Two Players

  看了一眼但没时间补。容易设出 DP，发现其中为零的位置很少，分析一下发现只有 个。考虑求出所有为零的位置，拿数据结构维护一下即可。

树上处理技巧

Link

圆方树、图匹配

Link1 Link2

• A - Tourists

  要求的显然是圆方树上两点路径上的权值最小值，其中方点的权值是其相邻圆点权值的最小值。直接树剖维护，并将方点的权值改为其儿子权值的最小值再特判一下即可。

• B - Redundant Paths G

  直接缩点即可。

• C - 道路相遇

  答案是圆方树上两点路径上的圆点数量。

• D - 稳定婚姻

  依次断掉每条边再跑二分图匹配即可。

• E - 部落战争

  最小路径覆盖 = 点数 - 最大图匹配。

• F - 矩阵游戏

  行数和列数连边即可。

• G - Bricks

  换一个角度思考，看成选尽可能多的边并合并两个点，那么限制是横着的边不能和相邻的竖着的边，那么把边看作点，建图跑最大独立集即可。

• H - Prime Set

  抽象题，注意到这东西不完全是二分图，但是乱搞搞直接跑二分图匹配即可。

ACM 20260613

Link

ez round，ex 题也不难，启发式合并即可。

计算几何

Link1 Link2

晚练

Link

• 百万富翁 (20260601)

  暴搜一下每层的大小，再卡卡常就 了，剩下 次询问调一下参即可。似乎也可以 DP + 优化找出最优方案。

• LUK-Triumphal arch (20260602)

  二分再树形 DP 即可。贪心怎么是假的啊，赛时没瞪出来。

• 星空 (20260603)

  差分一下原序列变成 个 ；操作是选择两个位置，使距离在 中并 flip 这两个位置；目标是全部变为 。将一些操作头尾相接就可以得到新的操作，因此先建出图跑 BFS 再状压 DP 即可。

• Svjetlo (20260604)

  什么传奇大分讨 DP /咦。设 分别表示子树中有零个、一个、两个端点的答案即可。

• 赛博乐园 (20260605)

  直接最短路即可，因为精度是 所以阈值需要开到 左右。赛时阈值开小了点挂了 3 分。

• Perfect Binary Trees (20260607)

  简单树形 DP，赛时对零求逆元挂了 5 分。

• Arranging Cows (20260608)

  困难区间 DP。将操作看成选两个相邻且相同的数，让旁边两个数同时加上它们的数值并删掉它们。为了处理边界需要在边界补 ，容易发现只需要补 个。最终状态是只留两个数，因此容易想到设 表示删掉 的方案数，因为每次删两个所以操作次数一定是 。直接做是 的，容易发现转移可以双指针优化，于是可以做到 。

• Dynamic Instability P (20260609)

  并非困难，求出 表示从 走到 子树外的期望步数， 表示从 走到 的期望步数，求答案就容易了。赛时式子推错了也没时间写完了。

• Partitioning into Three (20260611)

  断环为链，钦定 ，那么可以类似双指针地维护，之后再倒过来做一遍即可。赛时少判了个 Corner 挂了 3 分。