[YDRS#006] 日拱一卒，功不唐捐 · 云斗四月 Silver Round 总结帖

比赛背景

学习 OI 的你我，其实像极了在崇山峻岭之间攀登的旅人。

广袤的天穹下，层峦叠嶂。带着斗笠、汗流浃背的登山翁，纵然喘息声已经响彻崖峭，在飞鸟的视角里，却也只如山野间的沧海一粟。

但我们仍然向上坚定地攀登着，一步一步、一点一点，希望有朝一日，能够看到更为高远的景色。

参赛选手来源

参加本次云斗四月月赛的选手们来自全国各个省份的中学，也有小学选手参与并取得不错成绩。选手们的主要来源学校如下：

中国人民大学附属中学 四川省成都市第七中学 衢州二中 青岛二中 安徽师范大学附属中学 威海市实验高级中学 四川省绵阳中学 湖北省武昌实验中学 浙江省义乌中学 江西科技学院附属中学 江苏省常州高级中学 山东省潍坊第四中学 常州外国语学校 常州市第二十四中学 北京师范大学海口附属学校 临沂商城实验学校 成都七中八一学校 济南市历城第二中学 湖北省武昌实验中学 深圳中学 赣州中学 山东省文登第一中学 上海市松江区泗泾实验学校

赛况简报

比赛时间：4 月 27 日上午 9 点开始，晚上 8 点结束，期间任选四小时参与比赛。

报名人数：本次比赛共 158 人报名。

题目设置：共 A、B、C、D、E 五道题目，满分各为 100 分，总分 500 分。

题目难度：5 道题难度递增。A 题为 CSP-J T1 难度，B 题为 CSP-J T3 难度，C 题为 CSP-S T1-T2 难度，D 题为 CSP-S T2-T3 难度，E 题为 CSP-S T4 难度。

出题人：A、B、C 题由 @yummy 老师出题，D、E 由 @云浅 老师出题。

得分人数：报名选手中获得分数的共有 120 人。

最高分和最低分：本场比赛有 4 位选手以满分 500 分获得并列第一名。非零最低分为 10 分，得分来自 D 题的部分分。

得分分布：500 分共 4 人，400-500 分共 14 人，300-400 分共 18 人，200-300 分共 27 人，100-200 分共 44 人，100 以下（不包括 0 分）共 13 人。

通过情况：A 题共有 107 位选手通过，B 题共 63 位选手通过，C 题共 36 位选手通过，D 题共 20 位选手通过，E 题共 4 位选手通过。4 位通过 E 题的选手全部取得满分的成绩。

首次通过：A 题和 B 题都是由 @gcx12012 选手最先通过，C、D、E 题则由 @LoverInTime 选手夺得头筹。

赛题回顾

题目列表：

A-Seats B-Yummy > IOI C-有根树上求二维偏序 D-水如果能编织出自由的轮廓 E-将那朵云彩也跨越

A-Seats

关键词：字符串处理

B-Yummy > IOI

关键词：贪心

注：本题 idea 来自 IOI1994。

提示：a 数组和 b 数组的贡献是否可以分开计算呢？

C-有根树上求二维偏序

关键词：DFS 序，树状数组

提示：对 T1 进行 DFS 并记录进入/离开每个点的时间，对时间建立树状数组，思考如何统计贡献？

D-水如果能编织出自由的轮廓

关键词：置换环，计数

提示：对于一个排列，画出它的若干置换环，那么相当于置换环上的每条边 $(u, v)$ 有 $\max(u, v)$ 的贡献，我们希望所有边的贡献之和恰好为 $s$，计数方案数。考虑从小到大插入每个数，设 $f(i,j,s)$ 表示插入了 $1,2,...,i$，当前形态还是一条链的置换环个数为 $j$，目前已经确定的所有边的贡献之和为 $s$ 时的方案数。思考新插入 $i + 1$ 时，有哪几种可能？

E-将那朵云彩也跨越

关键词：状态压缩 DP，矩阵快速幂

提示：状压记录最后一列当前还未填入的格子集合 $S \subseteq \{1,2,...,n\}$，转移时对于新一列的白色格子集合 $T$，首先需要 $S \subseteq T$，在 $S \cup T$ 中的行放上 $1 \times 2$ 的横着的纸条，然后枚举剩下的位置决策要把哪些地方放上 $2 \times 1$ 的纸条。思考转移有哪些限制，如何进一步优化？

总结

本次[YDRS#006] 日拱一卒，功不唐捐 · 云斗四月 Silver Round 中有一些选手脱颖而出，取得较好成绩的选手有 @LoverInTime、@275307894a、@tevenqwq、@fzj2007、@000000、@10circle 等等等等。这其中有备战 NOI 2024 的省队队长，有 OI 强校的重量级选手，有刚刚展露头角的黑马小将，还有阅题无数身经百战的老面孔。他们中不乏 NOI 金牌、NOI 银牌、WC 金牌、APIO 银牌等高含金量比赛的奖牌获得者。

似乎每次比赛后，我们常会惊叹。我们感叹并仰望别人已经触碰到的高度，正如登山翁在疲惫时，也会擦擦汗，抬头仰望其他登山者如磐石般渐渐远去的背影——

“好高、好远、好羡慕！”。

学习 OI 的你我，其实像极了在崇山峻岭之间攀登的旅人。

重峦叠嶂，峰回路转，路比天险，或许你总是在抬头仰望那些已经或即将登顶的登山者，羡慕他们的成功和强大。殊不知，飞瀑乍泄，彩虹或许就在下一个路口为你绚丽，阳光普照之下，仰望他人的你，早已挺立在山势险要之处，成为更多后来者眼中如磐石般不断攀升的背影。

所以，不论身处巅峰还是洼地，既然选择了远方，便只顾风雨兼程。勇敢的 OIer 们，继续攀登吧！

附题解如下：