PKU-NOI WC 2024 游记 || HNOI 2024 rp++

· · 生活·游记

标记

不打标记。

我不是二百五。

希望 HNOI 2024 也能两天都有 250 分。

PKUWC 2024

前言

感觉是一次不错的经历。

正式比赛大多有遗憾，因为所有人的实力在考场上都会打折扣。

于是获得的分数就是在这个赛制和题目下的考场水平。

Day0

卷帆 \mathcal{FETCHED}！

在高铁上首次打了可持久化加点凸包的低配板子，命名为 \mathcal{ZYFSTCT}！

4\mathcal{KB\ used.}

Day1

上午观看北大的介绍。

在雨中拍了合照！

在 CQYC 的食堂用餐，都觉得不可思议，CJ 的根本没法比！

试机题是板的矩阵快速幂，做了二十分钟。

因为网络延迟，所以每天的测试时间是 13:00\sim17:05。

13:00\rightarrow()=0

ゲーム始まり
game start!
游戏开始！

当我在草稿纸上写了这三句话，游戏真的开始了！

T1 一看就是签到，写了一个暴力，交了两发才过第一档。

然后发现了一种归约方式，将复杂度做到了 O(n)。

13:13\rightarrow100=100

T2 和 T3 题面都是挂的，过了一会儿终于修正了。

感觉 T3 不可做，尝试 T2。

推了好久性质，没有找到，写了一个暴搜。

13:40\rightarrow100+11=111

继续找不到。

15:00\rightarrow100+11=111

已经没有什么希望了。

尝试输出所有方案，发现 \min a_i=0,1,2,3 猜想如果有解，全体减一依旧有解，写完之后过了前两档。

15:20\rightarrow100+28=128

后面会答案错误，然后我发现这样根本过不了拍。

结论不对，然后我想了一会儿，觉得可以减到还剩 \le up。

结果速度也不够。

于是加了卡时。

把 map<vector<int>,vector<int> > 换成了 unordered_map<unsigned long long,vector<int>，使用随机哈希，多过几档。

至少不会被倍杀了！

等于是挽回了一点局面。

16:00\rightarrow100+59=159

发现 up=2 就能过拍，这样非常快。

我觉得最后一档没什么希望，就不管了，做 T3。

16:20\rightarrow100+81=181

写了一发暴搜。

16:30\rightarrow100+81+10=191

发现可以更快地模拟。

16:40\rightarrow100+81+40=221

感觉特殊性质可以写，O(n\log^kn)，然后写了一段时间。

16:59\rightarrow100+81+60=241

然后我发现中间的一档也可以写，五分钟写完了，但已经结束了。

发现 T3 的部分分就是正解。

Day2

上午听了语言讲座！

13:00\rightarrow(241)=241

T1 一看就是签到，发现那个贪心很平凡，居然直接交就过了。

13:10\rightarrow(241)+100=341

T2 以为 m=2 的性质是对的，结果拍挂了，然后不会了，准备去做 T3。

14:10\rightarrow(241)+100+28=359

T3 一看就是线段树套平衡树板子。

写起来有些难受，不过稍微调了一下就过了样例，直接交过了几档性质。

15:10\rightarrow(241)+100+28+55=424

后来发现是平衡树写假了，换了好几种写法，又卡了很久的常，从卡时间变成了卡空间，最后把 size 去掉才过。

16:20\rightarrow(241)+100+28+100=469

一直找不到 T2 的规律，还剩 10 分钟时忽然想可不可以状压，发现可以！

还剩一分钟写完了，虽然被卡常了，但多过了一个子任务！

17:04:40\rightarrow(241)+100+55+100=496

显然那个状压又是正解，合理状态数只有 O(\lfloor\dfrac n k\rfloor^k),k\le10 不超过 3^{10}=59049。

总之就是经验不够。

晚上打 CF 成功下 \color{orange}{master}！

Day+1

卷帆 \mathcal{FETCHED}！

祝卷帆进国家队！

NOIWC 2024

Day0

打了云斗杯，题目很神秘，分数全暴力，但这都有 rank1？

试机，感觉文件夹全在主目录有些不习惯。

Day1

T1 有点水，然后去看 T3，发现一点都不会，写了一个暴力过不了样例，发现结论假了，这下连 O(poly(n,m)) 的都不会了。

写完 O(nm2^n) 的大暴力之后看 T2，觉得是一个连续段背包。

写完之后发现是 O(ans) 的，但样例的 ans 很大，十分良心。

加上一个分治，写了 4k，然后大样例跑飞快。

不过我一直怀疑这是指数级的，但自己不会卡，就跳了。

一直在想 T3 的 O(nF(m)) 的做法，先是做 m=1，然后加状压，连 FWT 都用上了，复杂度 O(nm4^m)，能过 m\le4。

最后几分钟打了特殊性质，不然就成大众分了（特殊性质比 O(nF(m)) 水太多）。

实际得分：100+100+50=250。

不过这么写暴力风险还是太大了，之后还是要调整一下状态。

据说这样的复杂度可以证明是 O(2^4n\log n) 的，所以本来就能过。

HNOI 2024 rp++