HBOI2023 翻盘记

· · 个人记录

HBOI2023 翻盘记

赛前

noip 寄了，120 pts，rk32，压线一等。

模拟赛状态还可以，很少挂分，除了 Dinic 优化写错挂 70pts。

codeforces 打得跟屎一样，总是被 div2.C 创死，从 1940 掉到 1713，终于在最后一场上了 100 多分。

湖北模拟赛 rk4，感觉大佬们在放水。

Day 1

花了 10 min 读题，感觉 T1 很水，求一下从每个位置出发向左向右最远能到哪，dp 即可，需要用线段树优化，想了想可以用扫描线加 \verb!set!，代码并不难写，一测样例没过，手玩了一下，“这样例有问题吧我靠” ，发现测的是 T2 样例，测了所有样例全过了，看了一下样例感觉挺强的，就没管了，T1 用了大约 35 min。

想了好久 T2，只想到子图一定联通，突然意识到自己 T1 写挂了，写了个先转移再删除，很疑惑，样例好像挺水的。

回头写完 T2 25 分暴力，想冲 O(n^3)，不会，想冲树，也不会，过了一个多小时都没啥进展，先放下去看 T3，发现用启发式合并加 \verb!multiset! 能拿 48 pts，一会儿就写完了，测了能跑的样例都过了，冲性质分一个都没冲出来，回头看 T2，想到边双，每个边双中的点要么全选，要么全不选，要么只选一个，但还是不会。

最后 30 min 检查代码，主要检查 T2 和 T3，最后检查 T1 思路有没有问题，最后 5 min 意识到求每个位置向右最远能到哪时每次用的是最小的转移，赶紧改，最后 1 min 改完，很惊险。

估分 100+25+48=173，感觉只拿到了大众分，没啥优势，靠 day 2 翻盘了。

Day 1.5

考完在步行街吃完火锅，吃完后去了植物园，周末的 wh 车是真的堵，来回坐车花了几个小时，植物园也感觉很一般，然后划一晚上水。

Day 2

发现自己坐在最后，考完核验代码要等好久，很操蛋。

同样 10 min 读完所有题，好多博弈论，废了。

感觉 T1 很水，O(n^6) 记搜 很简单，写完发现过不了样例，改了好久死都过不了，好像写假了，此时过去了一个多小时，感觉人人都会的 T1，浪费这么长时间还没做出来，“要退役了”，心态有点爆炸，想去想 T2，心根本静不下来，又回头看 T1，发现枚举一下步数就可以做了，虽然复杂度不对，但能过很多性质分，写完后已经过了两个小时多。

上了个厕所，回来想 T2，一点思路没有，只好写 20 分暴力，看 T3，神仙题，想了一会儿发现 t=n 的 dp 并不难，T2 的暴力加 T3 的 dp 一共花了一个多小时，感觉自己菜死了。

想 T2 的部分分，暴力建二分图可以拿 4 分，嫌太少了就没打，想到了 B 性质的 dp，结果调到最后都不知道哪里错了，最后花了几分钟检查代码。

比赛结束了意识到自己 T1 要挂分，10\sim 13 要求步数不超过 9，而我的代码中限制的是 9 步，但最后我的答案是步数减 1，本来稳拿的分丢了，很烦躁。

估分 ?+20+10，感觉人均 100+，要退役了。

赛后

看小图灵的 day1，d1t2 T 了一个点，觉得是机子慢了，其他一分没挂，很好，168 pts，rk 12。

想到 d1t2 也有可能不是机子的问题，我弱智用了邻接矩阵，O(n^22^n)，相信 CCF 的机子吧。

晚上用云斗测了一下全省的 day2，发现其他选手好像 day 2 比我还爆炸，能进前 10，又感觉有希望了。

最终小图灵 rk6，加权 rk8，云斗 rk7，加权 rk10。

划水到官方出成绩。