2026 年 6 月日祭

数论进阶

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

跳了。

NOIP 模拟赛 20260616

Link

• A

  好难啊。首先容易写出 暴力，注意到若 在 中已经合不了了，那么它在 的子集中显然也合不了了。合并时写个搜索即可，时间复杂度 。

• B

  注意到当前集合下，异色位置的或和一定是它的一个子集，那么直接做就是 的。考虑优化，发现可以看成去掉颜色的限制，每次加一位，就可以做到 了。

• C

  显然先把 最大的搞出来，此时需要用 打不掉的打 ；注意到可以连环打，写出来是一个区间覆盖的形式，大力维护即可。

• D

  转化后容易发现限制只与每个等级最左边的点有关。发现限制过于抽象，把它放在坐标系上就是一个 L 形的限制，但是因为是两维的所以依然难以处理。尝试发掘一些性质，钦定一个点合法，发现其第一象限的点都合法，因此可以将偏序的点去掉，整体变成了一个单调递减的点列；钦定一个点不合法，发现其第四象限的点的限制变成了一维的。于是枚举最小的不合法等级再 DP 即可。

NOIP 模拟赛 20260617

Link

• A

  手模一下发现前缀和搞搞即可。

• B

  转化一下变成在一个序列中选至多 段的最大和，反悔贪心或闵可夫斯基和即可。

• C

  很困难吧。一个结论是 和 中一定有一个序列的每个 pm 都是原序列的 pm，否则一定不优，可以通过调整法证明。考虑判断在一位填了 之后是否合法，容易写出一个等式，将等式化简后可以将判定转化为：将原序列的 pm 的权值视作 ，其余视作 ，求当前后缀是否存在一个指定权值和的 LIS。注意到若能凑出 则一定能凑出 ，因此拿两棵线段树分别维护奇数和偶数即可。

• D

  线段树大力维护即可，pushup 是单 的。

动态规划

Link1 Link2

• A - 新魔法药水

  预处理出在使用 次魔法的前提下药水 的最低成本即可。大力 DP 一下。

• B - Array Shrinking

  简单题，处理出 表示 往后走到哪里能凑出 即可。

• C - Swedish Heroes

  神人题目。观察发现，方案合法当且仅当 且存在相邻的两个位置相同，其中 分别是贡献为正和负的位置数量。大力 DP 即可。

• D - 选课

  简单题。

• E - 骑士

  简单题。

• F - 宝藏

  简单题，状压一下，一层层选即可。

• G - PTA-Little Bird

  简单题，单调队列优化即可。

• H - 灯塔

  原。

• I - 邮局 加强版

  原。

Codeforces Round 1105 (Div. 1)

Link

• D - Hunting the Beast

  挺牛的啊。显然容斥，枚举白色叶子数量 和纯白的环的总点数 ，通过又一次容斥可以得出后者的容斥系数是 ，然后大力推式子即可。lcy 枚举不合法的点数然后打表把这题过了。

组合数学

Link1 Link2

• A - 集合计数

  /bangbangt。

• B - 分特产

  /bangbangt。

• C - 按位或

  Min-Max 容斥板子。

• D - 重返现世

  Min-Max 容斥板子，不过好难。容斥过后考虑 DP，拆组合数之后发现只需要对所有 同时 DP 即可。

• E - Galgame

  简单题，需要启发式合并一下。

• F - 组合数问题

  考虑把普通幂转成下降幂，然后大力推式子即可；也可以先把系数放一边，拆组合数得到递推式。

• G - 硬币购物

  原。

• H - 划艇

  原。

• I - 骗我呢

  原。

• J - 奇怪的分组

  /bangbangt。

• K - Split and Maximize

  /bangbangt。

• L - White and Black Balls

  /bangbangt。

晚练

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 分。

• Asteroid Mining (20260612)

  Link，一层层统计答案并合并即可。

• Tree Traversals (20260613)

  每层是独立的，并且只存在至多两种情况，随便做做即可。

• 骰子旅行 (20260615)

  要求的是 ，其中最后一个 是离开 后第一次经过 ，随便 DP 一下即可。

• Random Isolation (20260620)

  好难啊。考虑计算每个连通块贡献的概率，可以将题意转化为任意排列的期望操作次数，那么对于一个大小为 的连通块，设它与连通块外的 个点直接相连，说明这 个点要在这个连通块之前操作，那么概率就是 。直接 DP 数连通块数量即可。

• 长安幻世绘 (20260621)

  考虑双指针，那么只需要动态维护答案，动态 DP 即可。

• 一个网的路 (20260622)

  DP 即可。

• Paired Up P (20260623)

  好难啊。设 表示第 只奶龙不选，前 只奶龙中选了的奶龙匹配到第 只暴暴龙的答案。直接转移即可。

• Expected Destruction (20260624)

  我选的。正难则反，发现相邻两个撞一起会减小答案，于是 DP 算一下概率即可。

• 疫情控制 (20260624)

  单独让我做的。先二分，注意到若某节点的最小权值不超过边权的两倍就可以直接留下，做完了。

• Amusement Park (20260625)

  每次可以增加一个独立集，那么直接 DP 再容斥一下即可。

• Boxed Like a Fish (20260628)

  简单题，赛时脑抽了但是误打误撞过了。若两个 的距离 那么它们的 LCA 是 。做完了。

• Voltage 2 (20260629)

  我选的。嘟，不过这个好像在随机说话。

• Destruction of Walls (20260630)

  我选的。嘟。