Studying Father's luogu blog

Focus on interest!

模拟赛组题日志

前言

我校之前的不少校内模拟赛历史都较为悠久,考察的内容与现在 OI 发展的程度间产生了不小差异,不再适合现阶段训练的要求。

对于现阶段冲刺联赛的学弟学妹来讲,使用整套的 BalticOI,CEOI,JOISC 等试题又不契合联赛的考察难度和范围。一种折衷的方案便是从这些真题中,挑选难度适中,启发性较强的题目,组建尽可能接近现今 NOIp 风格的模拟赛。

于是就有了这个日志。

尽量做到比赛结束当天就更新,如果各位有比较好的建议也欢迎留言~

10.2

三道题里只有 T3 我之前做过,其他两道都是组题时偶然翻到的。

美术展览

一道需要推式子的贪心题,思维量适中,放在 T1 这个位置还算不错。

(注:个人认为像格雷码这样的纯模拟题目得分率一般较高,在比赛中为这样的题目安排一个位置意义不算太大,所以没有安排这样纯粹的签到题)

游戏

容易想到使用并查集维护联通性,再去树上倍增。

和 T1 一样还是一道重思维考察的题。

实验比较

本人之前省队训练期间做的一道树形背包题,和前两道小清新题相比要重口味了许多。

10.3

这三道题应该是我做过的题目中,最喜欢的几道题吧。

餐厅

经过一番转化,可以转化为背包的模型求解。

这里 是更详细的题解。

摩天楼

因为 NOI Online 里考察了一道根号分治题,所以把这道题拿了出来。

本题有两种建图方式,各有其局限性。

将这两种建图方式结合起来就可以实现效率平衡。

这里 是更详细的题解。

寻宝游戏

是 myy 的题。

其实这题更接近 IOI 风格一些(

这里 是更详细的题解。

10.4

这次比赛考察内容偏向套路向了,算是对参赛者所学知识的直接检验。

最小圈

容易发现是 0/1 分数规划板子题。

火车旅行

常规的思路是直接建图。

换个思路,发现一个站跳一次能到的站的范围是一段区间,可以倍增算出跳 $k$ 次能到的站的区间范围。

将这些区间展开成树形结构,就变成了计算树上两点间距离的过程。

这里 是更详细的题解。

序列分割

可以证明分割顺序对答案无影响,从而实现一个 $O(n^2)$ 的算法。

可以利用斜率优化将其优化为 $O(n)$。

10.5

今天休息一天。

10.6

年轮蛋糕

二分答案+双指针即可。

最差记者

See this.

聚会

考察了选手观察题目性质的能力。

两个关联不大的问题能够出现在一道题里,表明这两个问题间可能存在内在联系。

See this.

10.7

花式围栏

重点考察了单调栈。

港口设施

容易想到建立二分图染色的模型,这样可以拿到 $22$ 分。

满分做法需要在连边上作出一些优化。

这里 是更详细的题解。

音游

考虑一种贪心做法。

先将原序列从大到小排序。容易发现一个子树内的数一定对应序列的一个连续区间。

为了达到靠前的数尽可能大的目的,递归到点 $u$ 时,优先将靠前的区间分配给编号较小的子树,而该子树的根节点则取得该子区间右端点的数(小根堆性质)。

可以证明在 $d_i$ 互不相同时,该做法是正确的。

在 $d_i$ 不同的时候,需要对上面的做法作出一些改良。

这里 是更详细的题解。

10.8

今天休息一天。

10.9

不少人都表示题出难了,所以今天把难度降了,放了几道送分题。

食物链

容易发现是一个 DAG 上的递推题。

云计算

可以设法建立背包的模型求解。

这里 是更详细的题解。

区间

考虑排序后双指针维护区间集合,用线段树维护一个点的覆盖次数。

这里 是更详细的题解。

10.18

PDF

与前几次比赛不同,这次比赛是给所有准备参加 CSP-S2 和 NOIp 的人准备的。所以难度与前几次相比有所降低。

馒头

显然装馒头的时候优先装最贵的。

设 $f_i$ 表示装 $i$ 个馒头需要花费的最小包装费用。这个显然可以背包解决。

求和

$k$ 很小,考虑预处理出当前点到根节点路径上所有点的 $k$ 次方和。然后即可 $O(\log n)$ 回答每一组询问。

装置

容易发现所求具有周期性,找出周期后变成了经典的线段覆盖问题。

这里 是更详细的题解。

11.13

CSP 之后组题工作重启,也是第一次准备四道题的比赛。

PDF

11.20

PDF

也许 T3 和 T4 换个顺序更好?

2021.7.21

给新高一和新高二的学弟学妹们组的模拟赛,也是这个暑假第一次比赛。

题目重点聚焦于他们新学的知识,同时帮助他们复习以前学习的内容。

总体来说代码实现难度较低,有一定建模难度,考察选手转化与化归思想,以及对经典算法本质的理解。

最后的得分情况不甚理想。最高分 207,均分只有 53.1,离理想状态还差很远。

以及,这次比赛暴露了不少考场经典错误:

  • freopen("art.in", "r", "stdin");
  • art.cpp.cpp

希望正式比赛的时候别踩这些坑(


2020-10-03 20:11:44 in 未分类