NOI2022游记

· · 个人记录

前面不想写了，简而言之就是颓颓颓

Day 1

8:00

surprise2022 然后开题一看一个交互，震撼我一整年。

然后看题，T1 这不是一个线段树合并板子题嘛，序列有绝对众数的话，在权值线段树上查，每次走的那个区间的内 cnt 一定大于序列长度的一半。

然后我想每次询问的时候应该是保证序列编号互不相同的吧，然后去题里面找这句话，woc 居然找到一个不保证互不相同，那得开 long long 了，不然一个长序列在询问中出现很多次直接起飞。

再想了想大概没有什么细节，就是合并序列的时候需要用一个链表或者 deque 什么的，想了想不太会用 STL::list，然后就用了 deque 启发式合并。（晚上讲题的时候说用 deque MLE 了一火车人，我没 MLE 这是为什么呢？小编也很惊讶）

然后用了一个小时五分钟把这题切了。

9:05

开始看 T2，哇这不是一个裸的 dp 套 dp 嘛，那么我只要搞出判定性问题的做法，不就可以了？脑子里闪过各种各样的想法，但是似乎没有一个能做的，我能观察到的结论只有所有二操作不会有选定区间相同的，然而并没有什么用。

75 minutes later...

10:20

cao 什么东西嘛，不做 T2 了，做 T3。

然后又开动脑筋使劲理解 T3。

30 minutes later...

10:50

cao 什么东西嘛，为什么我 n\le 2000 都不会做啊！！

心态有点小崩。

还是滚回去看 T2 吧。

首先有一个垃圾 dp 是考虑 dp[i][j][k][l] 表示到 i，从 i 开始的区间减有 j 个，从 i-1 开始的区间减有 k 个，从 \le i-2 开始的区间减有 l 个，但显然直接分析的话 j,k 是 O(n) 的，l 是 O(n^2) 的，没救、

想着想着开始猜结论，先猜了一手以每个点开始的区间减个数不会太多，打了一发表发现可以只开到 3！然后这样 j,k 就是 O(1) 的，但是 l 还是 O(n) 的，还是不够。

然后继续猜结论，一个点所接受到的区间减个数不会太多！

打了一发表发现也是至多只有 3！

好了这样就把 j,k,l 全部限制到 O(1) 了，一共会有 20 组合法的，那么 dp[i][][][] 就可以抽象为一个二十位的二进制数。

然后有一个显然的观察是当加入的数字 \ge B 时，与加入 B 的转移是一模一样的，考试的时候也没有仔细算过，开了 B=10。

然后这个自动机看起来是有 2^{20} 个状态的，然而我 BFS 一跑发现能遍历到的只有 262 个。

好耶我搞出自动机来了！

然后发现没有考虑 k

没救了，写一个 l_i=r_i，和一个 k=0 吧。

码码码

12:34

我终于全写完了，有 55 分。

然后开始写 T3，再一看发现链的部分简单，然后冲了一个分块（？所以你为什么没有想到猫树）拿到 10 分。

13:00

出来的时候几乎自闭了，估分 100+55+10=165

15:05

哦 T2 还挂了 15，变成 100+40+10=150 了。

Day 2

8:00

一看题，感觉今天的题又是不太正常。

看了看 T1 发现 76 分似乎很简单，直接树哈希，k>0 的点暴力删叶子，k 更大的时候暂时没有什么想法，先跳过。

看到了出题人不恶意卡哈希，点赞！

8:20

看了看 T2 首先一个结论是一定有一个最优解满足 a_i 都是某个 v_i 然后 v_i\le 1 的部分分直接有一个 O(n^3) 的简单 DP，更高的部分分暂时想不出来。

8:40

看了看 T3，感觉是神仙题，先写了 k^n 暴力就扔着没管了。

9:15

写完 T3，再去看 T1，发现我是 sb，这树哈希每次分儿子的时候暴力全排列都是可以的，复杂度正确，就是写起来有点恶心。

然后思考树哈希怎么做，我使用的是双哈希的版本，每个儿子的哈希值从小到大排乘上一个质数再加一，然后出来一问发现这个可以被卡，但是考试的时候我自己拍的都没问题？？

又是写啊写啊写，写到 11:15 终于写完了，深感自己太菜了。

11:15

写完 T1 看 T2，先把 40 分的部分分写了一下。

12:00

然后开始想 n^2 做法，还是各种想法一大堆但是没一个能做的。

假 1：像保序回归一样做整体二分。（太离谱了不敢做，而且似乎是错的）

假 2：各种乱七八糟贪心，随便举就有反例。

结果度过了绝望的一个小时，毫无头绪。事实证明我还是太垃圾了。

13:00

又是自闭离场，估分 100+40+13

14:45

似乎可以提早查分了？

颤抖的手一打开 pdf，100+24+21=145。？？？？我 TM T2 深搜写挂了？但是 T3 似乎多了 8 分，总的来说掉了 8 分还能接受。

然后两天加起来一共 150+145=295 不知道能不能 Au。

忐忑的不得了啊

寄了，耶