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\limits_{i=1}^k b_{c_i} - \min\limits_{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(nk)$ 。

作为场上的 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(n2^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\limits_{i,j\in S, i\le j}2^{c_{i,j}}$，其中 $c_{i,j}$ 为 $i$ 号与 $j$ 号连通块之间 $z=1$ 的边数。需要注意的是，连向同一连通块的边也需要处理。

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

算法四

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

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

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