【游记】NOI2021 游记

7KByte · 2021-07-29 22:41:16 · 个人记录

随便写点记录（语文拉了轻喷

Day -?

被拉去外校训练，水土不服就回来了（

比赛前两天通知报道提前一天，临时出发，下午到了

被教练问到多大把握拿 Au（这不是搞人心态），答个四五成吧。赢了就是rp，输了就是脸黑（

下午参加练习赛，发现题目是去年的题，看来是没有非传统题了。

写笔试，写完没感觉有不确定的选项，开分看发现挂了一题，才知道原来开考前不能碰鼠标键盘（

被通知 8:30 到考场集合。

我寻思这时间不大像是要比赛啊（

进了考场被通知 9:00 考试，硬着头皮上吧。

先开 T1，LCT 动态链划分？不大会写。

再看 T2，DAG 上数数，感觉像是线性代数，想了一下矩阵树定理和BEST定理发现没有关联啊。

开 T3，发现强连通分量缩点后就是一颗外向树，讨论一下就有 64。仔细想一下发现发相关点拆出来跑虚树貌似就能过了。

细节没有想明白，继续想 T1。

感觉直接暴力将链推平，然后将相邻的实边改为虚边的复杂度是正确的，貌似可以势能分析一下。

然后开始码，码了快两个小时还过不去最小的样例，还有几个细节一直没想明白，感觉要崩盘啊。

弃了看 T2 ，手算了几个发现交点个数就是逆序对数，但是后面就不会了，直接状态压缩 DP 貌似有 40 分。

回去看 T1，突然想到对链的操作应该放到点上，修改操作就是将一条链推平成一种新颜色，查询操作就是询问一条链上颜色改变了多少次。以前做过一样的省选题，直接码，大概在 12 : 00 左右过了所有样例，不开 O2 能跑进 0.8 秒稳得很。

然后开始码 T3，大概在12 : 30 的时候把建树完成了，能过 k = 0，然后跑虚树，但是大样例一直 WA，一看时间已经 1:00。

赶紧回去写 T2 的 40 分状压，大概在 1:30 左右过了样例。

回去调 T3，修了几个 sb 错误能过 k = 1 的样例，k = 2 一直 WA 死活过不去（我吐了啊

还有 5 分钟，一直在人眼 Debug，最后还是没有找出问题，只有离场了。

出来发现好几个人满分，看来今天是没了。

下午查分，没有挂分 100 + 40 + 64 = 204 。全场有二十多个满分，队线大概 260，吐了（

正常时间考试，特意带了一瓶 1.5 L 的快乐水（

直接开题，感觉这个 T1 很魔幻，想了一下发现自己只会 256NM 的做法。

看一眼 T2 发现非常的 splay，那么猜一手结论 W/E 分别对应两个矩阵。

手推一下发现分别对应 1,1,0,1 和 2,-1,1,0 。

然后开始码，在 10:30 的时候能过所有样例，但是最大样例要 3s。

手动卡常，把矩阵乘法循环展开一下就能跑进 2s。

接着看 T3，题面真的是又臭又长，看完之后还是没有什么想法。不过读题分有 8 分。

试图写 m = 1 的部分分，结果写完后发现自己想假了。

再抬头发现只剩下 1 个小时了，剩下的时间在 T1 和 T3 之间反复横跳。

想到 T1 的 k\le 15 ，不就是把 256 分成 16 个长度为 16 的块，一定有一个块完全相同。然后，然后就不会了（吐了啊

最后写了一个非常玄学的 Trie 上暴搜剪枝，k 很小的时候效率很高，但是 n 大一点就被卡空间了。

考完离场，快乐水一口都没有喝。听 LHQing 说 T1 很简单，第一感觉是 Day2 也没戏了（

下午查分 44 + 100 + 8 = 152，总分 99 + 204 + 152 = 455 没戏了，输了。

晚上出队线 498，差一个 D1T2 或 D2T1。很想说如果当时想到就 win 了，可是没有那么多如果，所以我还是说明年再来吧 RP++。