Staff
本次招新系列活动的工作人员如下：
活动策划 & 宣传推广：CYMario
题目 Idea：来自清华算协的往届推研机试各位命题成员（大部分题目），瑾雨瑭（清华考研机试 2024 调剂）
题目 Solution & 复刻 Data：CYMario
题目 Check：来自北京航空航天大学的秋花追忆（jhdonghj112，Nerovix，J_B_Y）
本次系列活动的题解通道
致谢
感谢洛谷提供可以自由上传题目并举办比赛的平台，以及相对良好的评测环境。
感谢“水木清研”站长目鱼石提供大家自由交流讨论的平台，以及作为复刻组初期成员所作出的贡献。
感谢来自清华计算机类考研社区其他分区的各位领头人、来自计算机保研交流群（“绿群”）的群主、来自大兔子竞赛咨询交流群以及 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\limits_{i=1}^n\sum\limits_{j=1}^n (ij)^k=\sum\limits_{i=1}^n i^k(\sum\limits_{i=1}^n i^k)=(\sum\limits_{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$，从板子的二部图变成了三部图。暴力连边跑最小割即可，但是 $nk$ 的边数太大了，一般的网络流实现会被卡掉，结合子任务 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\le n\le 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\le x$ 。首先根据题目不难想到，对于所有的限制 $p,x$ ，当且仅当都满足 $p\ge x$ 时能够找到合法序列（这是显然的，因为位置 $\le 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$。
设 $dp_{i,k}$ 为前 $i$ 个学生分成 $k$ 列的最小花费，则有：
- 初始状态 $dp_{i,1}=(a_i-a_1)^2$
- 状态转移 $dp_{i,k}=\min\limits_{j=1}^{i-1} dp_{j,k-1}+(a_i-a_{j+1})^2$
时间复杂度 $O(n^2 k)$，可以通过样例 2，期望得分 0。
算法二
注意到算法 1 中的状态转移方程满足斜率优化的形式，将 $i,j$ 两项进行分拆：
$dp_{i,k}-a_i^2=dp_{j,k-1}+a_{j+1}^2-2a_ia_{j+1}$
将该式子改为 $b=y-kx$ 的形式，$b=dp_{i,k}-a_i^2,~y=dp_{j,k-1}+a_{j+1}^2,~x=a_{j+1},~k=2a_i$，维护下凸壳相切即可。
插入点集保证 $x$ 递增，查询斜率 $k$ 也递增，因此直接使用单调队列线性维护即可（从 $dp_{i-1,k}$ 到 $dp_{i,k}$ 的转移）。跑 $k$ 轮斜率优化dp的时间复杂度 $O(nk)$，空间复杂度 $O(n)$，可以通过样例 3，期望得分 0。
算法三
将算法 1 的状态转移方程修改一下，$dp_{i,k}=\min\limits_{j=2}^{i} dp_{j-1,k-1}+(a_i-a_{j})^2$ ，该方程满足区间分拆问题模型，区间分拆的前置状态为 $f(j-1)=dp_{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_ia_j)-2(a_{i+1}a_j+a_ia_{j+1})=2a_{j+1}(a_{i+1}-a_i)+2a_j(a_i-a_{i+1})=2(a_{i+1}-a_i)(a_{j+1}-a_j)\ge 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
（不知道 QOJ 的 LaTeX 为啥容易抽风，姑且写成这样了，复制到 markdown 公式当中就能看懂了）
注意到这同样是一个可以斜率优化dp的转移方程，$b=y-kx$ 的式子当中，$y=f_j+a_{j+1}^2,~x=a_{j+1},~k=2a_i$。类似算法二基于单调队列做斜率优化dp即可，同时记录最优决策的区间分段数。外层基于区间分段数对 $v$ 做 wqs 二分即可。总时间复杂度 $O(n\log V)$，$V$ 是费用偏移的值域。期望得分 100。
本次活动完结撒花，非常感谢大家的参与！