MENU

HBOI 2021 游记

HB初一 OIer。

Day0

hsy在搞运动会。

说起来运动会之后就马上要省选也是真心离谱。

一整天就做了一下去年省选的题目,然后整理了一下要上交的做题总结,差不多就这样了。

晚上回宿舍huangyikun还在复习莫反,不愧是hsy高一信息组天花板,晚上还在卷。。。

我顺便复习了一下二项式反演和斯特林数,别的啥都没干。

Day1

看到了很多HBOI的神犇。

然后就顺序开题,T1一眼发现可以把所有正反面放在一起排个序,然后考虑从每个位置$i$开始向后扫,扫到第一个位置$j$使得区间$[i,j]$中包含了所有牌,并且存在一种选牌方案使得反面的数量$\le m$,复杂度$O(n^2)$,$40pts$。

实际上T1有一个特别显然的结论就是选的牌一定是一段前缀加上一段后缀,不知道为什么考试的时候没有发现,这样做复杂度是$O(m^2)$的,可以多拿$20pts$。

T2构造题,没有什么思路,纯粹就是乱搞。

说实话$n\le 3$,$m\le 3$的部分分我都没有把握能拿,对于一般情况我就考虑把每个值均摊到四个格子里去,这样大概能够混对一些点吧(?)。

如果$m=2$的话,很容易发现首先第一列和第二列之间的关系我们没必要管,所以先把这两列当成一列考虑,最后把值均摊到两边就好。又发现我们只要确定了这一列的第一个值,就能够算出后面的每一个值,所以枚举第一个数就好了,大概这档分是能拿到的吧,复杂度是$O(TVn)$,$V$是值域。

01矩阵的部分分就先把0全部覆盖上,然后乱搞搜索一下。

T3直接打一个最暴力的搜索,$16pts$。

估分$40+30(+20+25)+16=86pts$。

Day2

不知道Day2是怎么搞的,明明都说Day2暴力比Day1好打,但是我Day2却考的原地爆炸。

T1大概是字符串题,没什么思路,一个暴力$O(qn)$算法拿$25pts$走人。

T2和T3我直接原地爆炸。原 地 爆 炸。

T2应该很好想$60pts$的暴力吧,枚举所有排名,然后考虑贪心的让$b_i$最小,如果比$m$大,就判断这种排名不合法,这样做复杂度$O(n!)$,据说还能对搜索进行上下界剪枝,Vamper的搜索跑$n=13$的数据只需要$1.2s$,说不定就能把这题直接切掉,orz。

然而,我的神奇做法是,枚举所有$b_i$,然后判断是否合法,还需要$hash$判断是否有重复的排名。

这样做复杂度高达$O(m^n)$,当然实际上复杂度不会这么高,并且我的搜索也有优化,不过也只能拿到$25pts$。

T3跟sb一样。对于每个点它的支配集都可以$O(n^2)$的求出,具体而言就是对于结点$u$枚举每一个点,然后$dfs$一下如果不经过这个点,能否到达$u$,而我的做法是,枚举所有$1\to u$的路径,然后将经过的结点取个交集,这样做的复杂度非常爆炸,因为一个点不一定只能够走一次。

T3直接挂成了$10pts$。

F7487T3也是我这么打的,但是他的T1T2做的都还十分理想,有点可惜。

不用估了Day2必然只有$25+25+10=60pts$,说不定比这还要低。

Ending

这波省选真的考的非常差,翻遍全$Luogu$省选联考A卷选手的游记好像没有和我考的一样差的人了。

如果我是高一选手,我估计会选择直接$AFO$,但是毕竟才初一,时间还多,我没有$AFO$的理由。

希望明年省选能够进E队,继续努力吧,至少得发挥出自己的水平,不能像今年一样打挂两道题的暴力。

同时祝愿我们hsy高一信息组的的其他人能够$250pts+$吧,也祝愿高二的学长学姐们能够顺利进队。

Updated on 2021.4.20

省选分出来了。

和估分相差不多,省Rank31,在初一学生中也只能排到Rank3,并且和他们省选分差距相当大,NOIP的优势也没能填补这一漏洞。

这次确实应该好好总结经验,成绩与预期相差太大。

另外%huangyikun,如果没有1/3限制他是可以进队的,等到高二湖北省主力大概就是他了,tql。

Last Modified: March 16, 2022
Archives Tip
QR Code for this page
Tipping QR Code