2025 年 11 月日祭

CSP-S 2025

• A - 社团招新

  原来这就是反悔贪心啊。

• B - 道路修复

  我是唐。发现一个图在加入若干条边后，原来不在 MST 的边现在还是不在 MST。随便搞搞即可。

• C - 谐音替换

  赛时想到一个树套树做法但是没写出来。

  感觉转成二维数点的做法不是很优，于是严肃决定恶补一下串串。

  首先把 写成 的形式，然后把两个串合在一起变成 ，然后原题就变成求有多少个模式串是文本串的子串了。时间复杂度 。

• D - 员工招聘

  不想写了。

多校联考 20251104

Link

• A - 图

  甚至是搜索题。搜一下每个点到 的最短路距离，边搜边算贡献即可。

多校联考 20251105

Link

这场是啥啊。

多校联考 20251108

Link

下分场。

• A - 国王的试炼

  拆拆贡献，发现只用关注当前数与比当前数小的数，所以随便 DP 一下即可。

多校联考 20251111

Link

上分场。

• A - 青蛙

  唐。

• B - 表达式

  我唐。注意到 0+x+x-0 正着是 倒着是 ，于是直接构造即可。

• C - 淘汰赛

  首先容易写出 。

  然后你会发现我们只用关注以 为右下角、长宽为 的矩形中的位置，于是就做完了，时间复杂度 ，用数位 DP 实现可以做到 。

多校联考 20251112

Link

原神 Round. 1

• A - 异或

  唐。

• B - 伊甸

  奶龙大战暴暴龙，但是输在了原题没有的 corner case。

• C - 炼丹炉（[CF1979F] Li Hua and Path）

  板，但是不会。首先人工容斥一下，变成求同时满足两个条件的点对个数。考虑从小到大与从大到小各加一遍点，令新加的点成为当前连通块的根，那么限制就转化为了祖孙关系。用类似阿狸的打字机的做法即可。

多校联考 20251113

Link

原神 Round. 2

• A - 传统题

  大样例题。

• B - 非传统题

  你没蛋还在发力。

• C - 历遍的树

  考虑找出哪些点可以用来掉头，发现这样的点需要有三条以它为起点的路径，使得每条路径的长度都大于等于蛇的长度。称满足条件的点为关键点。可以证明，只要蛇可以到达一个关键点，它就可以到达任意一个关键点。所以任取一个关键点为根，模拟蛇移动的过程，判断蛇能不能移动到根即可。

多校联考 20251118

Link

原神 Round. 3

• A - box

  唐氏 DP 题。

• B - graph

  侦探 JYY 还在发力。

• C - chess

  赛时通过手模大样例猜出了斜列黑白交替的结论，然而因为时间原因，没发现第一行相邻的一对格子颜色相同（实则是因为赛时做完前两题开始发呆耽误了很久）。Solution。

多校联考 20251119

Link

• A - 下一个天亮

  乱构造一下即可。

• B - 希巴拉克的道路

  发现需要维护一堆线段的斜率，上李超树即可（但是赛时写了个神秘做法）。

• C - 超纲

  似乎挺板，但是不会。

多校联考 20251121

Link

• A - 『木叶创立』

  唐。

• B - 『须佐能乎』

  容易写出一个暴力的矩阵快速幂优化 DP。可以发现，若令直径的中点作为根，那么对于一棵子树，其内部点的 DP 转移是完全相同的。进一步发现，若称两棵子树本质相同，当且仅当其内部的直径端点数量相同，那么对于两棵本质相同的子树，其内部点的 DP 转移都是相同的。所以对于本质不同的子树进行 DP 即可，时间复杂度 。

多校联考 20251122

Link

• A - 破乱的诗歌

  随便乱做做即可。

• B - 增殖的病菌

  塔尖缩一下点就昨晚了，细节有点多。

• C - 可爱的猫猫

  难绷搜索。

多校联考 20251124

Link

• A - 创生矩阵

  难绷构造题。考虑构造两个长度为 的序列 ，其中 满足 ， 同理。那么对于原矩阵 ，只需要构造 即可。对于 ，随便构造一下即可。

• B - 都因为你

  签到题。

多校联考 20251125

Link

A 原，其他不会。

多校联考 20251127

Link

• A - 幸运数字

  分讨题，被 corner case 创飞了。

• B - 树的遍历

  屎。随便推一推发现需要维护一堆东西的和，然后维护即可， 还需要写个扫描线。

• D - 季风

  签，随便推推式子即可。

NOIP 2025

• A - 糖果店

  按照 排序，取最小的若干个 ，再取若干个最小的 即可。

• B - 清仓甩卖

  父母是一块还是两块。

  记 表示第 个物品打折后为 费。发现统计不合法的方案数应该更容易。发现一个方案不合法，当且仅当考虑物品的顺序为 ，且考虑 时恰好只剩 费。特别地，若考虑 后考虑了 ，应当满足 。

  于是考虑对 排序，并枚举 ，使得 。通过双指针求出 的最大值。对于每个物品，若下标属于 ，那么取一费或二费均可；若属于 ，那么只能取二费；若属于 ，那么取一费或二费均可。

  另一个限制是在考虑 之前恰好花掉了 费，除去 花掉的 费，还剩下 费。对于下标属于 的物品，若取一费，那么它会在考虑 之前被取，贡献为 ；若取二费，那么它会在考虑 之后被取，贡献为 。对于下标属于 的物品，无论取一费还是二费，它都会在考虑 之前被取，所以贡献为 或 。现在要求从这些物品中选 费的方案数，发现两段本质相同，我们可以认为第一段是 ，第二段是 ，于是直接组合意义即可。当然也可以枚举一段求另一段，再用一个神秘恒等式化简。