模拟赛组题日志

## 前言 我校之前的不少校内模拟赛历史都较为悠久，考察的内容与现在 OI 发展的程度间产生了不小差异，不再适合现阶段训练的要求。 对于现阶段冲刺联赛的学弟学妹来讲，使用整套的 BalticOI，CEOI，JOISC 等试题又不契合联赛的考察难度和范围。一种折衷的方案便是从这些真题中，挑选难度适中，启发性较强的题目，组建尽可能接近现今 NOIp 风格的模拟赛。 于是就有了这个日志。 尽量做到比赛结束当天就更新，如果各位有比较好的建议也欢迎留言~ ## 10.2 - 美术展览：[[JOI 2018 Final]美术展览](https://loj.ac/problem/2348) - 游戏：[[COCI2017-2018#5]Pictionary](https://www.luogu.com.cn/problem/P4616) - 实验比较：[[HNOI2015]实验比较](https://www.luogu.com.cn/problem/P3240) 三道题里只有 T3 我之前做过，其他两道都是组题时偶然翻到的。 ### 美术展览 一道需要推式子的贪心题，思维量适中，放在 T1 这个位置还算不错。 （注：个人认为像格雷码这样的纯模拟题目得分率一般较高，在比赛中为这样的题目安排一个位置意义不算太大，所以没有安排这样纯粹的签到题） ### 游戏 容易想到使用并查集维护联通性，再去树上倍增。 和 T1 一样还是一道重思维考察的题。 ### 实验比较 本人之前省队训练期间做的一道树形背包题，和前两道小清新题相比要重口味了许多。 ## 10.3 - 餐厅：[[BalticOI 2019 Day2]汤姆的餐厅](https://www.luogu.com.cn/problem/P6228) - 摩天楼：[[APIO2015]雅加达的摩天楼](https://www.luogu.com.cn/problem/P3645) - 寻宝游戏：[[HNOI/AHOI2018]寻宝游戏](https://www.luogu.com.cn/problem/P4424) 这三道题应该是我做过的题目中，最喜欢的几道题吧。 ### 餐厅 经过一番转化，可以转化为背包的模型求解。 [这里](https://studyingfather.blog.luogu.org/solution-p6228) 是更详细的题解。 ### 摩天楼 因为 NOI Online 里考察了一道根号分治题，所以把这道题拿了出来。 本题有两种建图方式，各有其局限性。 将这两种建图方式结合起来就可以实现效率平衡。 [这里](https://studyingfather.blog.luogu.org/solution-p3645) 是更详细的题解。 ### 寻宝游戏 是 myy 的题。 其实这题更接近 IOI 风格一些（ [这里](https://studyingfather.blog.luogu.org/solution-p4424) 是更详细的题解。 ## 10.4 - 最小圈：[[HNOI2009]最小圈](https://www.luogu.com.cn/problem/P3199) - 火车旅行：[[JOISC 2017 Day2]火车旅行](https://loj.ac/problem/2395) - 序列分割：[[APIO2014]序列分割](https://www.luogu.com.cn/problem/P3648) 这次比赛考察内容偏向套路向了，算是对参赛者所学知识的直接检验。 ### 最小圈 容易发现是 0/1 分数规划板子题。 ### 火车旅行 常规的思路是直接建图。 换个思路，发现一个站跳一次能到的站的范围是一段区间，可以倍增算出跳 $k$ 次能到的站的区间范围。 将这些区间展开成树形结构，就变成了计算树上两点间距离的过程。 [这里](https://studyingfather.com/archives/3078) 是更详细的题解。 ### 序列分割 可以证明分割顺序对答案无影响，从而实现一个 $O(n^2)$ 的算法。 可以利用斜率优化将其优化为 $O(n)$。 ## 10.5 今天休息一天。 ## 10.6 - 年轮蛋糕：[[JOI 2014 Final]年轮蛋糕](https://loj.ac/problem/2758) - 最差记者：[[JOISC 2016 Day4]最差记者 2](https://loj.ac/problem/2740) - 聚会：[[SDOI2019]热闹的聚会与尴尬的聚会](https://www.luogu.com.cn/problem/P5361) ### 年轮蛋糕 二分答案+双指针即可。 ### 最差记者 See [this](https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d4-worst_reporter2-review.pdf). ### 聚会 考察了选手观察题目性质的能力。 两个关联不大的问题能够出现在一道题里，表明这两个问题间可能存在内在联系。 See [this](https://studyingfather.com/archives/3110). ## 10.7 - 花式围栏：[[CEOI2020]花式围栏](https://www.luogu.com.cn/problem/P6801) - 港口设施：[[JOISC 2017 Day1]港口设施](https://loj.ac/problem/2391) - 音游：[[九省联考2018]IIIDX](https://www.luogu.com.cn/problem/P4364) ### 花式围栏 重点考察了单调栈。 ### 港口设施 容易想到建立二分图染色的模型，这样可以拿到 $22$ 分。 满分做法需要在连边上作出一些优化。 [这里](https://studyingfather.com/archives/3045) 是更详细的题解。 ### 音游 考虑一种贪心做法。 先将原序列从大到小排序。容易发现一个子树内的数一定对应序列的一个连续区间。 为了达到靠前的数尽可能大的目的，递归到点 $u$ 时，优先将靠前的区间分配给编号较小的子树，而该子树的根节点则取得该子区间右端点的数（小根堆性质）。 可以证明在 $d_i$ 互不相同时，该做法是正确的。 在 $d_i$ 不同的时候，需要对上面的做法作出一些改良。 [这里](https://studyingfather.blog.luogu.org/solution-p4364) 是更详细的题解。 ## 10.8 今天休息一天。 ## 10.9 - 食物链：[[HAOI2016]食物链](https://www.luogu.com.cn/problem/P3183) - 云计算：[[CEOI2018]云计算](https://loj.ac/problem/3182) - 区间：[[NOI2016]区间](https://www.luogu.com.cn/problem/P1712) 不少人都表示题出难了，所以今天把难度降了，放了几道送分题。 ### 食物链 容易发现是一个 DAG 上的递推题。 ### 云计算 可以设法建立背包的模型求解。 [这里](https://studyingfather.com/archives/2598) 是更详细的题解。 ### 区间 考虑排序后双指针维护区间集合，用线段树维护一个点的覆盖次数。 [这里](https://studyingfather.com/archives/2873) 是更详细的题解。 ## 10.18 [PDF](https://studyingfather.com/uploads/contests/10.18.pdf) - 馒头：[[JOI 2014 Final]IOI 馒头](https://loj.ac/problem/2757) - 求和：[[BJOI2018]求和](https://www.luogu.com.cn/problem/P4427) - 装置：[[APIO2019]奇怪装置](https://www.luogu.com.cn/problem/P5444) 与前几次比赛不同，这次比赛是给所有准备参加 CSP-S2 和 NOIp 的人准备的。所以难度与前几次相比有所降低。 ### 馒头 显然装馒头的时候优先装最贵的。 设 $f_i$ 表示装 $i$ 个馒头需要花费的最小包装费用。这个显然可以背包解决。 ### 求和 $k$ 很小，考虑预处理出当前点到根节点路径上所有点的 $k$ 次方和。然后即可 $O(\log n)$ 回答每一组询问。 ### 装置 容易发现所求具有周期性，找出周期后变成了经典的线段覆盖问题。 [这里](https://studyingfather.blog.luogu.org/solution-p5444) 是更详细的题解。 ## 11.13 CSP 之后组题工作重启，也是第一次准备四道题的比赛。 [PDF](https://studyingfather.com/uploads/contests/11.13.pdf) - 生成数：[[JOI 2020 二次予選]桁和](https://www.ioi-jp.org/joi/2019/2020-yo2/2020-yo2-t3.html) - 单词：[[COCI 2019.10]Bajka](https://hsin.hr/coci/contest1_tasks.pdf) - 喷泉：[[eJOI2020]喷泉](https://loj.ac/p/3373) - 考试：[[eJOI2020]考试](https://loj.ac/p/3375) ## 11.20 [PDF](https://studyingfather.com/uploads/contests/11.20.pdf) - 领带：[[JOI 2020 Final]只不过是长的领带](https://loj.ac/p/3252) - 准高速电车：[[JOI 2017 Fianl]准高速电车](https://loj.ac/p/2333) - 关灯：[[六省联考 2017]分手是祝愿](https://www.luogu.com.cn/problem/P3750) - 排序：[[HEOI2016/TJOI2016]排序](https://www.luogu.com.cn/problem/P2824) 也许 T3 和 T4 换个顺序更好？ ## 2021.7.21 - 灯光秀：[[JOIG 2021]イルミネーション 2](https://www.ioi-jp.org/joig/2021/tasks/2021-joig-t3.html)（前缀和） - 美术展：[[JOIG 2021]展覧会 2](https://www.ioi-jp.org/joig/2021/tasks/2021-joig-t4.html)（二分答案） - 云计算：[[CEOI2018]云计算](https://loj.ac/problem/3182)（背包） - 游行：[[JOIG 2021]パレード](https://www.ioi-jp.org/joig/2021/tasks/2021-joig-t5.html)（最短路） 给新高一和新高二的学弟学妹们组的模拟赛，也是这个暑假第一次比赛。 题目重点聚焦于他们新学的知识，同时帮助他们复习以前学习的内容。 总体来说代码实现难度较低，有一定建模难度，考察选手转化与化归思想，以及对经典算法本质的理解。 最后的得分情况不甚理想。最高分 207，均分只有 53.1，离理想状态还差很远。 以及，这次比赛暴露了不少考场经典错误： - `freopen("art.in", "r", "stdin");` - `art.cpp.cpp` 希望正式比赛的时候别踩这些坑（