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
关于比赛答疑等信息，请加QQ群 515201605，入群理由填写“赛时答疑”即可。赛时的答疑，以及针对紧急事项采取的临时解决方案将会在第一时间于群内发布。
Day 0 介绍 & 题解
本场作为本次系列活动的预热场，为大家带来的是清华考研机试 2024 的完整套题，按照原始场次的 4 小时 3 题（满分 300）进行全真模拟。赛时民间统计的最高分为 230，本次 VP 场最高分为 300。本场题目已开放补题通道。
根据粗略估算，本场题目作为清华考研/预推免的安全线约为 80，作为优秀大学生夏令营的优秀营员分数线约为 130，仅供参考。
本次活动题目的难度标定分知识点难度（参照洛谷或者梦熊OJ的难度标定）与实现难度（直接按易中难区分）。
T1 擂台赛
source：清华考研机试 2024 T1
知识点难度：普及- 实现难度：中等
我们对选手的分组情况进行全排列枚举，每一种排列进行模拟，判断 1 号玩家是否为赢家即可。由于全排列当中可能会出现初始分组重复的情况（两个同一组的选手正反顺序算不同排列），枚举之后的答案除以 $2^{n/2}$ 即可。时间复杂度 $O(n!)$ 。
作为签到题，本题相比往年题目而言，从考察基础的 for 循环改为考察指数型/排列型枚举。对于基础较为薄弱的同学而言会较为棘手。
需要注意的是，本题的样例几乎没有任何用处，需要考生对这部分知识点熟练掌握。
T2 栈
source：清华考研机试 2024 T2
知识点难度：提高- 实现难度：困难
根据题意直接用栈结构进行模拟不难得到一种 $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 实现难度：中等
本题的样例同样没有任何用处，甚至会将选手诱导至各种假做法的思路上一去不复返。同样需要选手对相关知识点有一定认知。
使用形如 $O(n^m)$ 的指数型枚举可以获得子任务 1 的 10 分，使用动态规划或其他搜索剪枝方式则同样无法绕过 $O(m^n)$ 的指数复杂度，可以获得至多 40 分。
使用最小费用最大流/有源汇上下界最小费用可行流的基础暴力建模可以获得 45 分，结合数轴上费用的可分段性对建模图进行分治优化则可以获得 100 分。上述部分分做法以及费用流的建模基础与优化思路可见 详细的题解科普 （小编懒得再敲一遍了）。
本题是否存在模拟费用流解法？
这一点主要是因为本题 1 秒的时间限制对于经过了分治优化建图的 SSP 增广费用流依旧十分严苛。再加上本题的建模图一定程度上类似经典的老鼠进洞模型 使得小编有了这样的思考。但是小编脑子不好使，模拟费用流这辈子是学不会了。因此留作 open problem 与大家进行讨论。
（当然也存在另一种可能，就是本题在 OJ 部署时忘记改默认时限了。先例就是清华考研机试 2023 T2 在 OJ 上的时限为 1 秒，但是 tuack 题面时限为 3 秒。赛时对此题的重新评测也导致当时本就拥挤的评测等待队列更加雪上加霜。）
鄂公网安备 42010202000505 号