CYMario的博客

博客

标签

暂无

清华推研机试复刻组 2025 招新 day 2 题解 & 本次系列活动总结

2025-02-03 22:46:30 By CYMario

Staff

本次招新系列活动的工作人员如下：

活动策划 & 宣传推广：CYMario

题目 Idea：来自清华算协的往届推研机试各位命题成员（大部分题目），瑾雨瑭（清华考研机试 2024 调剂）

题目 Solution & 复刻 Data：CYMario

题目 Check：来自北京航空航天大学的秋花追忆（jhdonghj112，Nerovix，J_B_Y）

本次系列活动的题解通道

Day 0、Day 1、Day 2。

致谢

感谢洛谷提供可以自由上传题目并举办比赛的平台，以及相对良好的评测环境。

感谢“水木清研”站长目鱼石提供大家自由交流讨论的平台，以及作为复刻组初期成员所作出的贡献。

感谢来自清华计算机类考研社区其他分区的各位领头人、来自计算机保研交流群（“绿群”）的群主、来自大兔子竞赛咨询交流群以及 jiangly 2 群管理员对本次活动推广的支持。

感谢所有参与到我们系列比赛中的选手，以及旁观见证本次系列活动的大家。

当然，也感谢坐在屏幕前观看这篇文章，听我讲述我们故事的你！

这次系列活动是我为这个项目的延续所作出的一次尝试，希望能够让来自考研、保研、算法竞赛社区的大家认识我们，了解我们所做出的这些工作，和大家结交朋友，希望能够得到大家的帮助，和大家一起接着把这项工作做好！后续我大概应该会在知乎也写一下相关的系列小作文，简单回顾一下从我的视角中，有关清华推研机试相关工作的过去、现在以及未来。

本次系列比赛全部结束之后，我会向参与活动的同学们发出邀请，加入我们的后续工作，也会构思一下之后的工作流以及相关活动。由于考研初试出分在即，不久之后我们应该还会继续为大家举办考研机试的虚拟参赛（类似于本次活动的 day 0，当然这次主要就是面向进入复试的同学们了）。之后能做的事情还有很多...

不过这两天我需要好好休息一下了，这几天在精神上和体力上确实是非常累，几乎所有主要工作全都是我一个人在准备（尤其是在之前一段时间一直没有好好休息的情况下），这也是我对该项目未来所担忧的主要原因。单兵作战不只是无法持续为大家带来高质量的内容，更大的问题就是这个为大家带来帮助以及促进互相交流的项目可能就这样在我手里过早地结束了。和前两年相比，今年我也相当于是提前工期，加大了一些工作量，主要还是希望能打破单兵作战的闭环，在这次活动中招到对我们工作感兴趣的人，让这个项目以及活动能够在大家的努力下继续活下去。

有点喧宾夺主了，接下来将是 Day 2 总结和题解的部分。

Day 2 介绍 & 题解

本场同样为清华推研机试往届题目混搭，主要以进阶算法和大模拟为主。本场的补题通道已开放。恭喜 fuyuki 以 300/300（Day 0）+ 492/520（Day 1）+ 600/600（Day 2）的成绩一骑绝尘，在本次招新活动当中大赢特赢！唯一的一点点遗憾就是被 D1T5 前两个暴力子任务的边界数据送走了，私密马赛（）

本场的事故 & 自我检讨

前两天还在 Day 1 题解里讲原始场上出现的事故，是的孩子们，我也干了。这次主要的事故是来自于 T2 和一道被删掉的题目。

在验题的时候（同时也是 Day 0 举办的那天）我就意识到 T2 的初版数据质量极其粗糙（这破题的数据是真的超级不好造啊啊啊，输出答案动不动就整出一大堆 0），但是中间因为忙于后续活动的各种事情，我就搁置了没有着急重造。结果今天从上午重新造的时候，还是一直都没造好。由于这题是放在第二题这种靠前的位置，所以这题数据造得不足够的话，我是万万不敢让比赛开始的。因此比赛推迟了整整 30 分钟。

此外，原本的 T6 我一开始的数据有问题，也提示大家先不要看这题。然后比赛期间也在修其他的各种锅，好不容易重新回来修这题的时候，才意识到这完全是一道错题（原题其实只有其中一个特殊性质，是我擅自改成了一般情况）。由于比赛已经进行了三分之一，紧急换题肯定是来不及了，索性直接将这题删掉了，原始的 T7 改为了 T6。万幸并没有对 Fuyuki 造成太大的影响以及时间上的大量浪费。

需要澄清的是，这两个错误均与验题队完全没有任何关系，他们很好地完成了自己的工作。这道题目完全是我后面擅自决定追加的，但是在出题解的时候确实欠考虑了（事实上本次系列活动的 Day 0 全部 3 道题、D1T5、D2T3 我都没有让验题队去验，D1T5 甚至是在离比赛还有 1 个半小时的时候才发现数据还有问题，不过也好在最后呈现出来的时候都没出锅）。

我深知这样的事故如果出现在规格更大的正式比赛中会给选手们带来什么样的影响，这对我来说也是深刻的教训，也非常感谢各位选手对我的包容和信任，陪我继续完成了这场比赛。这其实也反映出高强度的单兵作战势必会出现问题，希望后续的活动当中，我能够和新加入的各位一起互相监督，一起将活动办得更好。

T1 鸽子窝

source：清华预推免机试 2019 校外 T1，数据范围有所加强

知识点难度：省选实现难度：简单

Tag：数学推导、拉格朗日插值、积性函数的线性求法

本场题目的原始题面我没有，是根据互联网留存的考生回忆进行仿照。在给足了尽可能多的暴力分以及所有可能的提示之后，在最后添加了两组子任务。

不难发现，本题公式为 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} (i j)^{k} = \sum_{i = 1}^{n} i^{k} (\sum_{i = 1}^{n} i^{k}) = (\sum_{i = 1}^{n} i^{k})^{2}$

自然数幂之和在 $k$ 次方的时候是关于 $n$ 的 $k + 1$ 阶多项式，根据题目中的提示求出 $0, 1, 2, . . ., k + 1$ 处的值，然后利用特殊形式拉格朗日插值即可求出，然后求平方取模即可。使用暴力求 $i^{k}$ 的方式期望得分 95。结合其积性函数的性质利用线性质数筛期望得分 100。

本题稍微有些卡常，因此在赛时从 1 秒调整成 1.2 秒（100 组数据可以支持的时间上限）并补充了避免使用 long long 运算的提示，勉强满足 2 倍 std 时限。我的 std 和验题队的实现都能在 600ms 以内跑完。

T2 花店

source：清华夏令营机试 2023 T3

知识点难度：省选实现难度：中等

Tag：指数级枚举、动态规划、最大权闭合子图、前缀优化建图

各种暴力分

本题的前 4 个子任务各不相同，可供大家进行暴力拼分。

子任务 1 满足 $k = m$ ，直接看 $m$ 天摆放的花提升到 $V$ 需要的总和是否大于等于顾客收益即可

子任务 2 满足 $k = 1$ ，逐一比较就行。

子任务 3 满足 $a_{i} = i$ ，可以直接进行动态规划，设 $f_{i}$ 为前 $i$ 个顾客可以获得收益最大值，其可以从 j<i 的 f_j 进行转移，根据 j 和 i 间隔是否在 k 以内设置不同的状态转移方程。

子任务 4 满足 $n = 12$ ，指数级枚举每个花是否提升到 $V$ 的状态能带来的收益。

暴力拼分期望得分最高为 50。

算法一

不难看出这是一个典中典的最大权闭合子图模型，只不过中间套了一层 $a_{i}$ ，从板子的二部图变成了三部图。暴力连边跑最小割即可，但是 $n k$ 的边数太大了，一般的网络流实现会被卡掉，结合子任务 3 的暴力拼分期望得分 75。复刻数据当中也有一些常数较小的做法直接干过去了，而且由于数据上传得很仓促，子任务 3 没有卡掉算法 1，之后会添加 Hack 数据。

算法二

在此算法 1 的基础上，从 $c_{i}$ 向 $a_{i}$ 的连边是固定连续 $k$ 个点，因此只需要以每 $k$ 个点为一段，进行前缀优化建图即可。从 $c$ 的每个点连出的边数为常数，边数量纲可以被优化为 $O (n + k)$ 。期望得分 100。使用线段树优化建图应该也能过。

T3 Balatro

source：清华考研机试 2024 调剂 T2

知识点难度：提高实现难度：中等

Tag：大模拟、排列型枚举

根据题目表格和样例解释，如果一组牌型中的有效牌不足 5 张，则只有有效的牌参与计分。所以对于 $n$ 张牌（ $1 \leq n \leq 5$ ），我们只需要枚举这 $n$ 张牌是否恰好构成一个牌型即可。在枚举时，我们分别枚举牌的个数为 1,2,3,4,5 张的情况（总牌数不足 5 张时则枚举到上限）

1 张牌，直接当高牌计算；
2 张牌，如果构成对子就按对子计算，否则按照非法计算；（非法视为分数 0）
3 张牌，如果构成三条就按三条计算，否则按照非法计算；
4 张牌，先看是否构成四条，再看是否构成两对，都不构成就是非法。
5 张牌，优先级是同花顺、葫芦、同花、数字，都不满足就是非法。

然后使用排列型枚举分别枚举 1,2,3,4,5 张牌的情况，先判断合法性，再计算分数，取最大值即可。

T4 排列

source：清华考研机试 2024 调剂 T3

知识点难度：提高+ 实现难度：困难

Tag：构造、线段树、平衡树

算法一

子任务 1 的 $n$ 非常小，直接全排列枚举，查看每一种排列是否满足所有的限制。满足即可输出，无解则输出 -1 。时间复杂度 $O (n!)$ ，期望得分 20。

算法二

注意到子任务 3 的特殊性质 $p \leq x$ 。首先根据题目不难想到，对于所有的限制 $p, x$ ，当且仅当都满足 $p \geq x$ 时能够找到合法序列（这是显然的，因为位置 $\leq p$ 的数一共就 $p$ 个，这其中还满足小于等于 $a_{p}$ 的个数必然不会超过这个上限）。所以只要出现 p<x 的情况则一定是非法的。输出 -1 即可。

剩下的就是考虑所有限制都满足 $p = x$ 的情况，很显然如果这个排列正好是 $1, 2, 3, . . ., n$ ，那么显然是满足上述限制的。此时直接按照顺序输出 $1 \sim n$ 即可。时间复杂度 $O (n)$ 。结合算法 1 期望得分 30。

算法三

非法情况的判断不重复讲解。

按照 $p$ 进行从大到小的排序，将整个序列从右往左递归进行确定。在每一个子问题当中，我们从还没填进排列中的数中选取特定的轴点位置 $p$ 需要填谁，并确定其他数在轴点左右的位置即可。初始情况下没有填进排列的数为 $1, 2, 3, . . ., n$ 。

假设当前还没填进排列的数字个数为 $n$ ，最右侧的限制为 $p, x$ 。这意味着在 $p$ 左侧有 $x - 1$ 个小于 $p$ 位置的数，有 $(p - 1) - (x - 1) = p - x$ 个大于 $p$ 位置的数。

假设我们对数字按照从小到大排名（也就是设未填进排列数字的最小值排名为 $1$ ），那么 $p$ 位置的数在他们当中的排名最大可以是 $n - (p - x)$ ，那么我们不妨直接取排名为 $n - (p - x)$ 的数放在 $p$ 位置。那么排名为 $1$ 到 $x - 1$ 以及排名为 $n - (p - x) + 1$ 到 $n$ 的数会放在轴点的左边，剩下的数只要按照任意顺序排列在轴点右边即可（最右边要么直接是第 $n$ 个位置，要么再往右一个是上一次问题的轴点）。

轴点以及轴点右侧的数都填好之后，轴点左侧的数依旧无法确定位置，则向左递归，将剩余未填写的数放在下一个限制内做判断。最后将从 $1$ 到最靠左的轴点之前的位置把剩余未填写的数按照任意顺序填写即可。

使用 $O (n^{2})$ 做法期望得分 60，使用权值线段树或者平衡树维护 $O (n \log n)$ 期望得分 100。std 用 treap 写的，人傻常数大跑了小 600ms。

算法四

本做法为验题队提供。

还是从右往左构造排列，并维护当前尚未填入数组的数集（初始为 $1$ 到 $n$ ），如果当前位置 $i$ 没给限制，直接找数集排名 $i$ 的数即可（同算法 3 描述中对排名的定义）；反之就直接找排名 $x$ 的数即可（ $x$ 即限制），这样的构造也是正确的。使用权值线段树在 90ms 以内跑完了。

Special Judge 是选手不可见的，但是也在这里顺带提一下算法实现。使用离线二维数点处理针对所有限制的查询即可。时间复杂度也是 $O (n \log n)$ 。

T5 飞镖

source：清华预推免机试 2023 校外 T2

知识点难度：提高实现难度：困难

Tag：大模拟、STL

二维数组暴力维护不多说，期望得分 44。

类似 Day 1 T3 水滴一题维护 set<pair<int, int>> 数组，除了同行同列之外，还需要额外维护同主对角线方向和副对角线方向的斜线。时间复杂度 $O (n \log n)$ ，期望得分 100。相比 D1T3，本题官方时限设置很合理，不卡常。

T6 军训队列

source：清华预推免机试 2016 校外 T4，数据范围有所加强

知识点难度：NOI 实现难度：中等

Tag：多维dp、斜率优化dp、单调队列、四边形不等式、wqs 二分

本题验题队在做的时候因为只有样例 1，虽然很快就上手写了正解，但是交了 10 次才过。因此本场我们提供了 $n = 500$ 和 $n = 3 \times 10^{3}$ 的大样例方便选手进行对拍，且用于引导选手从初等做法逐步引导至正解。

算法一

由于队列内可以更换顺序，显然先对学生身高排序之后再做划分能得到最优结果。以下统一将身高排序后的结果称为 $a_{1}, . . ., a_{n}$ 。

设 $d p_{i, k}$ 为前 $i$ 个学生分成 $k$ 列的最小花费，则有：

初始状态 $d p_{i, 1} = (a_{i} - a_{1})^{2}$
状态转移 $d p_{i, k} = {min}_{j = 1}^{i - 1} d p_{j, k - 1} + (a_{i} - a_{j + 1})^{2}$

时间复杂度 $O (n^{2} k)$ ，可以通过样例 2，期望得分 0。

算法二

注意到算法 1 中的状态转移方程满足斜率优化的形式，将 $i, j$ 两项进行分拆：

$d p_{i, k} - a_{i}^{2} = d p_{j, k - 1} + a_{j + 1}^{2} - 2 a_{i} a_{j + 1}$

将该式子改为 $b = y - k x$ 的形式， $b = d p_{i, k} - a_{i}^{2}, y = d p_{j, k - 1} + a_{j + 1}^{2}, x = a_{j + 1}, k = 2 a_{i}$ ，维护下凸壳相切即可。

插入点集保证 $x$ 递增，查询斜率 $k$ 也递增，因此直接使用单调队列线性维护即可（从 $d p_{i - 1, k}$ 到 $d p_{i, k}$ 的转移）。跑 $k$ 轮斜率优化dp的时间复杂度 $O (n k)$ ，空间复杂度 $O (n)$ ，可以通过样例 3，期望得分 0。

算法三

将算法 1 的状态转移方程修改一下， $d p_{i, k} = {min}_{j = 2}^{i} d p_{j - 1, k - 1} + (a_{i} - a_{j})^{2}$ ，该方程满足区间分拆问题模型，区间分拆的前置状态为 $f (j - 1) = d p_{j - 1, k - 1}$ ，代价为 $w (j, i) = a_{i}^{2} - a_{j}^{2}$ 。不难发现代价一项满足四边形不等式。证明过程如下：

交叉项： $W_{1} = w (j, i) + w (j + 1, i + 1) = (a_{i} - a_{j})^{2} + (a_{i + 1} - a_{j + 1})^{2}$
包含项： $W_{2} = w (j + 1, i) + w (j, i + 1) = (a_{i} - a_{j + 1})^{2} + (a_{i + 1} - a_{j})^{2}$

包含项减去交叉项有：

$W_{2} - W_{1} = 2 (a_{j + 1} a_{i + 1} + a_{i} a_{j}) - 2 (a_{i + 1} a_{j} + a_{i} a_{j + 1}) = 2 a_{j + 1} (a_{i + 1} - a_{i}) + 2 a_{j} (a_{i} - a_{i + 1}) = 2 (a_{i + 1} - a_{i}) (a_{j + 1} - a_{j}) \geq 0$

因此该状态转移满足四边形不等式，且本问题属于限制区间个数的区间分拆模型，因此可以使用 wqs 二分来解决本问题。

在 wqs 二分当中，设区间分拆代价偏移量为 $v$ ，无视区间分拆个数，设 $f_{i}$ 为前 $i$ 个学生在此限制条件下的最小划分代价，有：

f_i=\min\limits_{0\le j<i}f_j+(a_i-a_{j+1})^2+v
转换为： f_j+a_{j+1}^2=(-a_i^2+f_i)+2a_ia_{j+1}-v

（不知道 UOJ 的 LaTeX 为啥容易抽风，姑且写成这样了，复制到 markdown 公式当中就能看懂了）

注意到这同样是一个可以斜率优化dp的转移方程， $b = y - k x$ 的式子当中， $y = f_{j} + a_{j + 1}^{2}, x = a_{j + 1}, k = 2 a_{i}$ 。类似算法二基于单调队列做斜率优化dp即可，同时记录最优决策的区间分段数。外层基于区间分段数对 $v$ 做 wqs 二分即可。总时间复杂度 $O (n \log V)$ ， $V$ 是费用偏移的值域。期望得分 100。

本次活动完结撒花，非常感谢大家的参与！

阅读全文
好评差评[+3]

清华推研机试复刻组 2025 招新 day 1 题解

2025-02-01 23:45:40 By CYMario

Day 2 预告

本次系列活动 Day 1 将在 2 月 3 日下午 14:00 到 20:00 举行。6 小时 7 题，个人赛， IOI 赛制。题目仅涉及大模拟与进阶算法，知识点难度分布从“提高”到“NOI”。题目来源为尚未复刻并向公众公布的清华往届推研机试题目。

Day 2 也将是我们面向各位算法竞赛爱好者们准备的重头戏！我们同时也欢迎想在清华考研/预推免机试中取得中上或前排成绩，或者在优秀大学生夏令营中获得优秀营员的同学们参加，熟练掌握大模拟以及在进阶算法题中打满暴力分正是达成上述目标的必备技能。希望最后这场能够给大家带来酣畅淋漓的比赛体验，也希望大家都能玩得开心！

比赛链接： https://www.luogu.com.cn/contest/227691 邀请码： patd

关于比赛答疑等信息，请加QQ群 515201605，入群理由填写“赛时答疑”即可。赛时的答疑，以及针对紧急事项采取的临时解决方案将会在第一时间于群内发布。

Day 1 介绍 & 题解

本场为清华推研机试往届题目混搭，参照 CSP 专业级认证套题形式进行组题（编程基础 2 道 + 大模拟 1 道 + 基础算法 1 道 + 进阶算法 1 道），整体难度高于 2024 年的 4 场 CSP 认证。其中有一些题目稍微有点无聊，主要是清华推研毕竟和 CSP 还有一些区别，所以确实想组好确实有一些困难。于此同时，不少坑人的点也都集中在了本场。希望 Day 2 能够为大家带来更好的做题体验。

本场满分为 500+20，赛时最高分为 492。对于做出 T5 后几个子任务正解的两位选手被前两个子任务卡了半天感到私密马赛（但是毕竟原题就长这样，我就负责照本宣科造数据，这也怪不得我了www），最高分更是离 ak 就差一步之遥，确实有一点点遗憾（）

本场题目已开放补题通道。

T1 毕业照

source：清华夏令营机试 2023 T1

知识点难度：普及- 实现难度：简单

Tag：排列型枚举

类似 Day 0 推出的签到题，直接全拍列枚举所有排列，并检查当前排列是否满足给出的性质即可。时间复杂度 $O (5!)$ 。

以前签到题都是 for 循环，现在签到题全都是排列型枚举/指数型枚举，感觉看多了真的会产生审美疲劳...

T2 金色传说

source：清华考研机试 2024 调剂 T1

知识点难度：普及实现难度：中等

Tag：排列型枚举、滑动窗口、优先队列、动态规划

算法一

类似 T1，全排列枚举所有能选取的卡牌和开包顺序，时间复杂度 $P (n, k)$ ，可以通过子任务 1 和 3，期望得分 40。

算法二

注意本题的关键性质，在卡包给定之后，根据绝对值不等式不难发现，只要开包顺序升序或者降序即可使目标式子的后一项达到最小值 ${max}_{i = 1}^{k} b_{c_{i}} - {min}_{i = 1}^{k} b_{c_{i}}$ 。

因此我们可以按照 $b_{i}$ 对卡包进行升序排序，给定任意两个一定选择的卡包，再从中间选出 $a$ 最大的 $k - 2$ 个即可。因此使用滑动窗口+优先队列进行答案的枚举即可。时间复杂度 $O (n^{2} \log k)$ ，本题 $n$ 上限 5000 看上去 1 秒不太能过，但是 $n^{2}$ 对应的常数其实比较小，基本上敢写敢过。赛时最大时间有 800ms 过的。

算法三

还是结合上述性质，按照 $b$ 权值对卡包升序排列。考虑二维动态规划，设 $f_{i, j}$ 为前 $i$ 个卡牌当中选择 $j$ 个，且暂未减去最大 $b$ 值的最大答案。

初始状态： $f_{i, 1} = a_{i} + b_{i}$ 。因为按照上述升序排列之后， $i$ 号卡包作为第一个被选取的卡牌权值最小。

状态转移方程： $f_{i, j} = max (f_{i - 1, j}, f_{i - 1, j - 1} + a_{i})$ 。不解释。

备选答案为 $f_{i, k} - b_{i}$ ，时间复杂度 $O (n k)$ 。

作为场上的 T1，本题本来就不怎么签到，所以放算法二过个人认为比较合理。官方数据疑似没有答案是负数的数据，在复刻数据中我们加入了这种边界情况。

T3 水滴

source：清华预推免机试 2021 校外 T2

知识点难度：提高实现难度：中等

Tag：STL，大模拟，递归，卡常

需要注意的是，本题在原场次发生了较为严重的命题事故，原始数据错误且无法现场解决。当年的解决方案是赛后重造数据再 rejudge。本题原始 2s 的时间限制其实是非常不合理的（或许这与命题人的错误std与数据有关），而数据范围的 351493 也直接锁定了本题命题人的身份...本次复刻我们依旧采用 2s 的时限，主要是因为数据比较多，时限真的没法再抬了，这一点也对被卡常的选手们说一句私密马赛。

由于二维平面范围太大，无法用二维数组支撑，因此可以使用 set 套 pair<int, int> 数组记录同行与同列的水滴情况，四个方向上的临近水滴则可以用 lower_bound 找前驱和后继，按照题目规则进行递归即可。

本题比较卡常，尤其是在子任务 2 当中棋盘 $2000 \times 2000$ ，水滴方格规模 $7 \times 10^{5}$ 的稠密情况，当连锁反应可以将所有水滴消掉的情况下即可达到上界。

一些解决方法包括但不限于：

使用更加快速的输入输出方式
在递归模拟的过程中尽可能修改全局数组和全局变量，递归函数返回类型设为 void，减少堆栈消耗空间
对数据范围分治，子任务 1 和 2 当中直接使用常数小的二维数组即可

需要注意的是，有一种复杂度错误的十字链表模拟做法，我在造数据的时候只是想到了这个肯定不对，但是没有刻意造相关的数据，直接放过去了。再次表示私密马赛，已在赛后针对此做法在子任务 3 和 4 添加 Hack 数据。

T4 过去的项链

source：清华考研机试 2020 试机 T2

知识点难度：提高实现难度：中等

Tag：动态规划

算法一

两两枚举翻转区间，翻转之后两两枚举每一段的区间和，复杂度 $O (n^{4})$ ，期望得分 30。

算法二

两两枚举翻转区间，翻转之后求环状最大非空子段和，复杂度 $O (n^{3})$ ，期望得分 55。

算法三

题目本质上其实就是求环状最大双子段和。可以使用矩阵+线段树的方式维护dp，每次枚举环状的端点在哪里即可。时间复杂度 $O (k^{3} n \log n)$ ， $k$ 是矩阵阶数，期望得分 100。本次活动的验题队以及场上部分选手均是此做法。

算法四

不难看出环状最大双子段和无非就是两种情况（0 代表选，x 代表不选）：

xxx000000xxxxx00000xxx
000xxxxx000000xxxx00

因此问题就变成了求一次序列最大双子段和以及序列最小双子段和。时间复杂度 $O (n)$ ，期望得分 100。

一些边界数据包括：全正数、全负数、仅 1 个正数/负数、不同的正负数值或不同绝对值大小的分布。

T5 连通图的方案数

本题 20 分的附加子任务评测链接见这里，后续称为子任务 6（原始题目只有前 5 个子任务）。

source：清华夏令营机试 2020 T3

知识点难度：NOI-/NOI 实现难度：中等

Tag：指数型枚举、并查集、子集DP、FMT/FWT、子集卷积

请注意，子任务 1 和 2 以及子任务 3 到 6 的数据范围完全不相关，这需要选手针对不同 subtask 写数据分治。场上打暴力的基本稳拿前面 28 分，但是两位写了后续子任务正解的选手反而在这里被卡住了（尤其是最高分把子任务 6 都拿下了，子任务 1 和 2 还没过），私密马赛。

算法一

特殊性质是边数最多 18，直接对边集做指数级枚举，判断加上这些边之后的连通块大小是否为 1 即可。复杂度 $O (n 2^{m})$ ，期望得分 13。

以下是一些边界数据：

边数 18，点数 19，所有边满足 $z = 1$ 。这组数据可以卡掉想用算法 3 $O (3^{n})$ 通过该子任务的选手。
边数 18，点数 1e5。直接指数级枚举毫无疑问会超时，直接用 m<n-1 特判无解输出 0 即可。

算法二

特殊性质是 $m = n - 1$ ，那么该无向图要么是树要么不可能连通，直接用并查集判断即可。结合算法 1 的期望得分 28。

算法三

特殊性质是保证加入 $z = 0$ 的边之后，连通块个数不大于 15。

我们将每一个连通块看出点之后，不同点之间视为有标号的，那么需要使用子集 DP 来解决。

设 $s$ 是二进制表示的点集， $f_{s}$ 是该点集为无向连通图的方案， $g_{s}$ 是该点集为任意无向图的方案。

初始状态有 $g_{s} = \prod_{i, j \in S, i \leq j} 2^{c_{i, j}}$ ，其中 $c_{i, j}$ 为 $i$ 号与 $j$ 号连通块之间 $z = 1$ 的边数。需要注意的是，连向同一连通块的边也需要处理。

接下来求 $f$ 则用 $g$ 减去不连通的方案数即可。任意取 $s$ 中的一个点集 $p$ ，枚举 $s$ 当中包含 $p$ 的真子集 $s^{'}$ ，则有 $f_{s} = g_{s} - \sum_{s^{'} \subset s, p \in s^{'}} f_{s^{'}} g_{s - s^{'}}$ 。枚举子集复杂度为 $O (3^{n})$ ，结合算法 1 和算法 2 期望得分 100。

算法四

特殊性质是保证加入 $z = 0$ 的边之后，连通块个数不大于 20。

注意到上述转移方式类似于子集卷积，将上述式子转换为 $f_{s} popcount (s) = g_{s} - \sum_{s^{'} \subset s} f_{s^{'}} popcount (s^{'}) g_{s - s^{'}}$ （ $popcount$ 表示点集当中点的数量），将 $f_{s} popcount (s)$ 代入子集卷积即可（由于是或卷积，使用 FWT 或 FMT 均可），时间复杂度 $O (n^{2} 2^{n})$ ，结合算法 2 期望得分 120（子任务 1 除了 $n = 19, m = 18, z = 1$ 的数据点都能用子任务 4 过掉）。在一些实现当中，可能需要将连接同一连通块的边单独拎出来处理。

子任务 6 被选手在赛后利用算法 3 外加取模次数优化卡进了 5 秒以内，故子任务 6 的时限在赛后改为 4 秒。（upd： 4 秒也被卡常干过去了，但是再卡就没意思了，就这样吧）

阅读全文
好评差评[+1]

清华推研机试复刻组 2025 招新 day 0 - 清华考研机试 2024 VP 题解

2025-01-30 21:51:24 By CYMario

Day 1 预告

本次系列活动 Day 1 将在 2 月 1 日下午 14:00 到 18:00 举行。4 小时 5 题，个人赛， IOI 赛制。参照 CSP 专业级认证套题形式进行组题（编程基础 2 道 + 大模拟 1 道 + 基础算法 1 道 + 进阶算法 1 道），知识点难度分布从“普及-”到“省选/NOI-”。题目来源为尚未复刻并向公众公布的清华往届推研机试题目。后面的两场均为我们的正式活动，欢迎各位算法竞赛爱好者前来参加！

比赛链接： https://www.luogu.com.cn/contest/227682 邀请码： 4fte

Day 0 介绍 & 题解

本场作为本次系列活动的预热场，为大家带来的是清华考研机试 2024 的完整套题，按照原始场次的 4 小时 3 题（满分 300）进行全真模拟。赛时民间统计的最高分为 230，本次 VP 场最高分为 300。本场题目已开放补题通道。

根据粗略估算，本场题目作为清华考研/预推免的安全线约为 80，作为优秀大学生夏令营的优秀营员分数线约为 130，仅供参考。

本次活动题目的难度标定分知识点难度（参照洛谷或者梦熊OJ的难度标定）与实现难度（直接按易中难区分）。

T1 擂台赛

source：清华考研机试 2024 T1

知识点难度：普及- 实现难度：中等

Tag：排列型枚举

我们对选手的分组情况进行全排列枚举，每一种排列进行模拟，判断 1 号玩家是否为赢家即可。由于全排列当中可能会出现初始分组重复的情况（两个同一组的选手正反顺序算不同排列），枚举之后的答案除以 $2^{n / 2}$ 即可。时间复杂度 $O (n!)$ 。

作为签到题，本题相比往年题目而言，从考察基础的 for 循环改为考察指数型/排列型枚举。对于基础较为薄弱的同学而言会较为棘手。

需要注意的是，本题的样例几乎没有任何用处，需要考生对这部分知识点熟练掌握。

T2 栈

source：清华考研机试 2024 T2

知识点难度：提高- 实现难度：困难

Tag：双向链表/双端队列，启发式合并

根据题意直接用栈结构进行模拟不难得到一种 $O (n^{2})$ 复杂度的解法，可以获得 20 或 40 分（40 分需要将记录每次插入操作的数字个数，以操作个数为规模进行存储）。我们显然需要一种更优的算法来获得满分（以下几种均可）。

算法一

直接暴力模拟之所以上界为 $O (n^{2})$ ，是因为每次通过操作 3 将规模较大的栈逐步插入规模较小的栈。一种显而易见的方法就是将每一次操作 3 的实际操作改为从较小栈插入较大栈。通过势能分析不难得到此时的复杂度上界为 $O (n \log n)$ 。而在这种实际操作之后为了与题意效果等价，我们在这种修改实际操作的情况下将栈结构上下颠倒。而直接进行翻转又会导致复杂度上界变为 $O (n^{2})$ ，因此我们可以使用双向链表（list）或者双端队列（deque）等价完成栈的存储，并将栈的颠倒状态进行惰性表示（判断栈顶此时应为队首或队尾，由于本题 $n$ 的上界只有 $2 \times 10^{5}$ ，因此使用 deque 不会出现 NOI2022 D1T1 的 MLE 惨案）。

在复刻数据中，我们卡掉了错误的启发式合并方式（包括但不限于：按照数字规模而不是操作规模进行启发式合并、使用 vector 在合并之后直接进行 reverse），给了至多 90 分。不是小编想给这么多分，而是这个数据范围真的太难卡了 ←_←

算法二

将每一个栈直接用平衡树（Splay 或者 Treap）进行表示，需要打区间翻转惰性标记。在进行操作 3 的合并时，将 $x$ 号栈对应的平衡树完全翻转并插入 $y$ 号栈对应平衡树末尾即可。时间复杂度依旧是 $O (n \log n)$ 。

算法三

注意到操作 3 的合并操作本质上是将两个结构的头部或者尾部进行相接，我们直接手写双向链表，根据不同情况头尾相接即可。时间复杂度为 $O (n)$ 。

T3 指针

source：清华考研机试 2024 T3

知识点难度：NOI 实现难度：中等

Tag：指数型枚举，状态压缩dp，搜索剪枝，费用流，分治优化建图

本题的样例同样没有任何用处，甚至会将选手诱导至各种假做法的思路上一去不复返。同样需要选手对相关知识点有一定认知。

使用形如 $O (n^{m})$ 的指数型枚举可以获得子任务 1 的 10 分，使用动态规划或其他搜索剪枝方式则同样无法绕过 $O (m^{n})$ 的指数复杂度，可以获得至多 40 分。

使用最小费用最大流/有源汇上下界最小费用可行流的基础暴力建模可以获得 45 分，结合数轴上费用的可分段性对建模图进行分治优化则可以获得 100 分。上述部分分做法以及费用流的建模基础与优化思路可见详细的题解科普（小编懒得再敲一遍了）。

但是目前除了场上过题的选手之外，另外两个 AC 的解法都是通过对任务坐标的玄学处理莫名其妙地优化掉边数然后草过去了。再加上前面 40 分也有人场上爆搜过了，只能说确实见识到人类智慧了...分治优化建图有一个负收益在于任务与任务之间连边这部分会新开很多的虚拟点。所以从性能上确实会不如做了维修工到任务优化+玄学优化边数的做法，就很尴尬...

本题是否存在模拟费用流解法？

这一点主要是因为本题 1 秒的时间限制对于经过了分治优化建图的 SSP 增广费用流依旧十分严苛。再加上本题的建模图一定程度上类似经典的老鼠进洞模型使得小编有了这样的思考。但是小编脑子不好使，模拟费用流这辈子是学不会了。因此留作 open problem 与大家进行讨论。

（当然也存在另一种可能，就是本题在 OJ 部署时忘记改默认时限了。先例就是清华考研机试 2023 T2 在 OJ 上的时限为 1 秒，但是 tuack 题面时限为 3 秒。赛时对此题的重新评测也导致当时本就拥挤的评测等待队列更加雪上加霜。）

阅读全文
好评差评[+1]

清华推研机试复刻组 2025 招新公告 & 比赛预告

2025-01-24 09:36:57 By CYMario

前排提示： 本次活动的举办主体“清华推研机试复刻组”是来自清华的民间团体组织，与清华大学学生算法协会没有任何直接关系。

清华推研机试复刻组招新赛

“清华推研机试复刻组”一直在致力于针对清华大学计算机科学与技术/网络空间安全/软件工程专业的考研/优秀大学生夏令营/预推免的上机考试题目进行数据复刻，为广大准备清华考研/保研的同学提供高质量的真题练习渠道与自测效果。本次招新活动系列比赛的核心目的之一是在于选出有能力且有意愿参与清华推研机试复刻组后续工作的成员。

本公告只做一些简要介绍，更详细的招新公告见下方链接。我们在此提前祝大家新春快乐！欢迎各位未来有意向参加清华推研的同学们以及各位算法竞赛爱好者参与其中，希望大家玩得开心！也希望大家可以将本场活动推广给身边同样准备清华推研的同学或算法爱好者们！

如果有意向加入我们的项目运维/题目复刻/验题等工作，欢迎按照招新贴中提供的联系方式和要求与我联系。我们非常希望能得到大家的帮助，也诚挚地欢迎各位有能力有想法的同学能够加入我们（不限身份，非清华学生也没有关系），一起将这个项目做得更好！

本次招新活动包含一场推研真题虚拟参赛（VP）和两场正式赛。其中正式赛的两场成绩将作为我们的筛选标准。具体资格线详见两场正式赛的比赛描述。

预热活动：推研真题虚拟参赛

本场比赛为清华考研机试 2024 虚拟参赛（Virtual Participation），采用题目为清华考研机试 2024 一志愿场次的原题，按照题面数据范围严格复刻数据。时长为 4 小时，共 3 题。任何人均可报名参加。欢迎各位准备清华计算机类推研（考研或保研）的同学们参加，检验自己当前的程序设计能力。本场同时也作为后续两场正式赛的测试赛，不计入实际成绩。

清华考研机试 2024 虚拟参赛
- 时间： 2025 年 1 月 30 日 14:00 至 18:00
- 题目配置： 4 小时 3 题
- 比赛链接： https://www.luogu.com.cn/contest/227552
- 邀请码： 7vae

正式比赛

本次正式比赛将于 2 月 1 日（day 1）、2 月 3 日（day 2）进行，任何人均可直接报名参加。希望参与我们工作的同学不做强制要求，根据自己时间情况参与任何一场即可。同时我们也欢迎准备清华推研的同学与算法竞赛爱好者们在这里和大家一起同台竞技，玩得开心！

正式赛 Day 1
- 时间： 2025 年 2 月 1 日 14:00 至 18:00
- 题目配置： 4 小时 5 题，难度从"普及-"到"省选/NOI-"
- 比赛链接： https://www.luogu.com.cn/contest/227682
- 邀请码： 4fte
正式赛 Day 2
- 时间： 2025 年 2 月 3 日 14:00 至 20:00
- 题目配置： 6 小时 8 题，难度从"提高+/省选-"到"NOI"
- 比赛链接： https://www.luogu.com.cn/contest/227691
- 邀请码： patd

预热赛与 2 场正式赛的预热活动的实时榜单，以及正式赛 Day 1 的讲评（比赛结束当晚 7 点）将会通过 B 站进行直播，网址：https://live.bilibili.com/11783320

其他说明

本次活动正式赛使用的题目均为尚未进行复刻并向公众公布的清华往届推研机试题目，我们承认本次使用题目的原始版权均归清华大学计算机系所有，因此本次系列比赛没有收取任何赞助或其他资金支持。

清华推研机试题目的命题风格类似于专业级 CSP 认证（不是 CSP-J/S，也不是信息学竞赛）。在题目考察的知识点难度最高可以对标信息学竞赛的省选或 NOI 的前提下，简化问题建模与思维考察难度，考察重点以代码实现为主（俗称“码农题”）。想了解有关清华推研机试的具体内容，可以参见本人在知乎撰写的以下内容：

清华大学计算机类专业考研/保研--机试经验贴：清华推研机试的概览与简介
专栏：清华大学计算机类保研/考研机试部分题解：清华推研机试部分压轴题目的详细题解科普

本次活动的比赛均为个人赛，赛制为 IOI（实时评测，每题取最高得分计入总成绩）。总成绩从高到低进行排名，总成绩相同时以到达最终成绩的最早时间作为罚时，降序进行排名（与洛谷默认排行榜可能会有出入）。我们会对重新统计榜单后公布正式赛通过资格线的选手排名，当你参加正式赛即表示你知晓并同意自己的 id 可能出现在公开榜单上。

清华推研机试复刻组介绍

项目前身

“水木清研”小程序是由清华计算机类考研（专业课 826 计算机基础综合）的上岸考生开发的半盈利性质的小程序，提供初试与复试的知识付费服务。我们最大的初衷是为所有的 826（原 912）考生提供一个优质的学习、交流、知识传承的平台。

其中“机试训练营”付费项目于 2023 年 2 月正式启动，由“水木清研”站长目鱼石与管理员 CYMario 共同负责。我们免费向考生提供精选练习题以及从 2014 年开始的清华考研机试真题的评测链接，仅题目文字解析和代码标答作为付费服务。

从 2024 年开始，交由 CYMario 全权负责，负责业务也从原本的考研机试（春季推研机试）扩展到所有可以考据的推研机试（包括但不限于预推免、夏令营、留学生推研机试等）。

从 2025 年 5 月开始，“水木清研”将停止“机试训练营”付费项目的运营，将相关资料逐步开源。原“机试训练营”项目组正式转为开源组织“清华推研机试复刻组”。

项目内容

我们在持续进行往届推研机试题目的复刻，意在为准备推研机试的同学们提供真实的模拟练习环境。除了 2016/2017 年的 4 场推研机试采用 github 清华大学计算机系课程攻略开源的官方数据之外，其余题目均严格根据题面数据范围自造数据，可以提供相对准确的评测结果。目前我们的题目部署依托于洛谷，评测链接以个人用户题目的形式免费对外开放。

我们的复刻工作在准备清华推研的学生当中取得了广泛的好评和认可。我们在 2024 年秋季也与清华软院科协达成合作，在软件学院并入计算机类推研机试的首年，为软院科协组织的保研机试模拟练习提供了题目与数据支持。

目前我们已经完成了超过 40 道清华推研机试题目的复刻工作，可以通过下方“水木清研”小程序的“机试训练营”部分了解我们的现有成果（仅浏览工作成果与评测链接的话无需购买该项目）。

SMQY

团队招新

自 2025 年起推研机试复刻组独立之后，我们计划构建新一代的机试复刻团队。考虑持续定期在各位算法竞赛爱好者中招收有意愿完成项目运维、收集推研题目、复刻题目数据（造题）、验证复刻数据（验题）等工作的同学。具体事项可以见其他平台发布的招新贴。

期待你的加入！

阅读全文
好评差评[+2]

共 4 篇博客