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:数学推导、拉格朗日插值、积性函数的线性求法
本场题目的原始题面我没有,是根据互联网留存的考生回忆进行仿照。在给足了尽可能多的暴力分以及所有可能的提示之后,在最后添加了两组子任务。
不难发现,本题公式为
自然数幂之和在
本题稍微有些卡常,因此在赛时从 1 秒调整成 1.2 秒(100 组数据可以支持的时间上限)并补充了避免使用 long long
运算的提示,勉强满足 2 倍 std 时限。我的 std 和验题队的实现都能在 600ms 以内跑完。
T2 花店
source:清华夏令营机试 2023 T3
知识点难度:省选 实现难度:中等
Tag:指数级枚举、动态规划、最大权闭合子图、前缀优化建图
各种暴力分
本题的前 4 个子任务各不相同,可供大家进行暴力拼分。
子任务 1 满足
子任务 2 满足
子任务 3 满足
子任务 4 满足
暴力拼分期望得分最高为 50。
算法一
不难看出这是一个典中典的最大权闭合子图模型,只不过中间套了一层
算法二
在此算法 1 的基础上,从
T3 Balatro
source:清华考研机试 2024 调剂 T2
知识点难度:提高 实现难度:中等
Tag:大模拟、排列型枚举
根据题目表格和样例解释,如果一组牌型中的有效牌不足 5 张,则只有有效的牌参与计分。所以对于
- 1 张牌,直接当高牌计算;
- 2 张牌,如果构成对子就按对子计算,否则按照非法计算;(非法视为分数 0)
- 3 张牌,如果构成三条就按三条计算,否则按照非法计算;
- 4 张牌,先看是否构成四条,再看是否构成两对,都不构成就是非法。
- 5 张牌,优先级是同花顺、葫芦、同花、数字,都不满足就是非法。
然后使用排列型枚举分别枚举 1,2,3,4,5 张牌的情况,先判断合法性,再计算分数,取最大值即可。
T4 排列
source:清华考研机试 2024 调剂 T3
知识点难度:提高+ 实现难度:困难
Tag:构造、线段树、平衡树
算法一
子任务 1 的
算法二
注意到子任务 3 的特殊性质
剩下的就是考虑所有限制都满足
算法三
非法情况的判断不重复讲解。
按照
假设当前还没填进排列的数字个数为
假设我们对数字按照从小到大排名(也就是设未填进排列数字的最小值排名为
轴点以及轴点右侧的数都填好之后,轴点左侧的数依旧无法确定位置,则向左递归,将剩余未填写的数放在下一个限制内做判断。最后将从
使用
算法四
本做法为验题队提供。
还是从右往左构造排列,并维护当前尚未填入数组的数集(初始为
Special Judge 是选手不可见的,但是也在这里顺带提一下算法实现。使用离线二维数点处理针对所有限制的查询即可。时间复杂度也是
T5 飞镖
source:清华预推免机试 2023 校外 T2
知识点难度:提高 实现难度:困难
Tag:大模拟、STL
二维数组暴力维护不多说,期望得分 44。
类似 Day 1 T3 水滴一题维护 set<pair<int, int>>
数组,除了同行同列之外,还需要额外维护同主对角线方向和副对角线方向的斜线。时间复杂度
T6 军训队列
source:清华预推免机试 2016 校外 T4,数据范围有所加强
知识点难度:NOI 实现难度:中等
Tag:多维dp、斜率优化dp、单调队列、四边形不等式、wqs 二分
本题验题队在做的时候因为只有样例 1,虽然很快就上手写了正解,但是交了 10 次才过。因此本场我们提供了
算法一
由于队列内可以更换顺序,显然先对学生身高排序之后再做划分能得到最优结果。以下统一将身高排序后的结果称为
设
- 初始状态
- 状态转移
时间复杂度
算法二
注意到算法 1 中的状态转移方程满足斜率优化的形式,将
将该式子改为
插入点集保证
算法三
将算法 1 的状态转移方程修改一下,
- 交叉项:
- 包含项:
包含项减去交叉项有:
因此该状态转移满足四边形不等式,且本问题属于限制区间个数的区间分拆模型,因此可以使用 wqs 二分来解决本问题。
在 wqs 二分当中,设区间分拆代价偏移量为
- 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的转移方程,
本次活动完结撒花,非常感谢大家的参与!