HBOI 2021 游记

HB初一 OIer。

Day0

hsy在搞运动会。

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

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

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

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

看到了很多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暴力比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$，说不定比这还要低。

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

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

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

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

省选分出来了。

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

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

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