NOI2022 E类游记

https://zhangyiming.tech/NOI-2022/ E 类，(100) + (100+15+0) + (100+8+0) = 323，Ag 感觉这届 NOI 各方面体验特别好。 ### Day ??? 提前一周到昆山，咕掉军训（甚至和第一周的课），重庆集训的时候在弄中考所以并没有见过大部分人，趁这个机会认识了好多人：hxx(hxp?),zyy,rsx... 差点弄丢行李箱。 由于马上 NOI 于是每天都睡的很早。 ### Day 1（报到） "Whenever and wherever, NOI brings us together" 报到，但是并没有东西拿。 和同省省队一个寝室，看来是按分排序而不是 ABCDE。 下午和 LN 省队的一些人打三国杀，但一个人也不认识，问别人名字感觉好奇怪 /jk 晚上迎新晚会，现场发布原创曲十分的厉害。 谁是卧底的前两个题很有意思，LCP 和 LCS 就有点奇怪了。 ### Day2 （真·报到） 领到好多东西。 很快的将徽章交换到只剩一个，如果明年有一定多买点 /kk 依然有三国杀。 ### Day3 练习赛是 NOIP2021 ，只看了一下 T3，之后写一半代码被覆盖了，于是干脆不写。 笔试，只在 ”考前能否登陆系统“ 犹豫了一下，但不碰键盘怎么登陆系统呢？ 考完笔试网站直接没了，看别人有的能登上去但并查不了成绩。 回寝室后听到了 “成绩发给领队” 的消息。（但到最后也没拿到） 晚上听 ls 预测两天题没有交互、没有数学、没有计算几何、没有 ds 、没有图论。 （那考 6 道 dp 和 adhoc？） ### Day 4（比赛日 1） 早饭只剩面条吃 /kk 考前的比赛策略是（切 T1 + T2 高分暴力 + T3 暴力）。 T1 一开始在想根号分治，但一次询问总长度可能是 $O(n^2)$，于是复杂度甚至是 $O(n^2 \log n)$。 维护每个元素出现次数的 map 是容易的，但并不知道怎么 $O(\log n)$ 求答案。 只能写随机 30 个元素判断，不知道怎么从 map 里以出现次数为权值随机找一个元素出来，于是写权值线段树，先随机在哪个线段树里再从线段树里随机找一个。 考场上没想明白线段树值域有交合并也是 $O(n \log n)$ 的而且查询复杂度无论如何 $O(\log^2)$，只写了启发式合并。 发现有了 80pts ，感觉继续想下去意义不大，开始看 T2。 T2 看起来是先找一个判定性 dp 然后 dp 套 dp，但想了 1h 想不出来，感觉 T2 不会判定的话基本就不太可能有更多分了，于是看了 T3。 看懂 T3 题面但并没有想出来为什么是这两个操作，还想了一段时间 “为什么 M 能小到 1“。 感觉链可以 ST 表，写完之后 checker 报操作次数不够。 调到最后发现算法假了，寄。 出场的时候感觉自己寄了，认为这个 T2 一车人切。 但回去交流一下发现好多人都在 100～150，T2 的判定性做法好像并不是人均会。 听 ls 说 T3 链用猫树做好简单，但赛时根本没往那边想。 下午查分发现 T1 过了，没想到数据可以水成这样，听说 `long long` 只卡掉 5pts。 同时接到昌和哲的电话，从哲那大概了解到场况，感觉自己的分可能还行（？ 并告诉了他我们这边的状况，听他讲了 T2 但并没听懂。 之后给昌打回去，被问了 "1e6 个 deque 会占多少空间" 这样的问题（之后知道 ws 因此挂成了 0+0+0） 好像 JL 严重挂分？ 我可能成了我校唯一一个过 T1 的。 晚上听讲题 T1 知道了有 “摩尔投票” 这个东西，才想到 T2 每次选的段的长度小于等于 5，感觉想到这点后观察出剩下的性质依然很神奇，T3 从树分块开始就听不懂了 /kk ### Day5（社会活动） 社会活动只有解谜，但看完热身题的题解后发现自己根本没有做出这种题的能力，Div2 A 都不会，于是直接开始颓。 下午开幕式，无人机表演十分的炫酷（想不明白这东西是怎么定位的，难道认为无误差？）。 dzd 表示他也不知道提前来七天、核酸什么的有什么意义，但规定就是这样，还提到了暴戾语言那事。 ### Day6 (比赛日 2) 感觉翻到金牌不太可能，如果 Day2 延续 Day1 的难度的话，那 3 个暴力应该就稳 Ag 了（？ 发现 T1 好像很水，${n \choose 5} *n$ 的做法显然但肯定过不去，之后想到了一个消两个节点相同子树，之后剩下不超过 5 个儿子爆搜，感觉如果剪枝一下应该能过（？ 树哈希写的是之前 zkq 讲的随机一个序列，取第 siz 位再乘上所有儿子的和的做法。 即使过不去也有很高分了，于是看 T2。 推出了一个 “如果区间两两不相交那么一定将最小值放在第一个，剩下的每个区间内数一定一样，区间间一定单调递增” 的假结论。 于是只要能把区间消成两两不交就能 $O(n^2)$ 了（？ 写完之后发现连两两不交的大样例都过不去，意识到确定最小值之后剩下的需要大于等于最小值，于是单调递增是假的。 发现消区间的做法也是假的，于是先写了 T3 的暴力。 此时还剩 1.5h。 改 T2 的做法尝试过一些 subtask，但并没有成功，留了一个假 dp 尝试骗到较小的点的分。 考试结束后广播说 “日程有变，请选手立即联系自己的领队或教练”。 出考场发现大家好像都会 T2 的性质，而自己一直从那个假 dp 改进什么都想不出来 /kk 吐槽 T1 为什么所有性质点都给到了 $k=0$, 怕有人不会树哈希吗？ 听 thu 在线的咨询会，和之前 thusc 什么的说的没啥区别，2:30 听说可以查分就直接去了。 T1 过了，T2 8 分，T3 挂成 0。 怎么纯暴力也能挂。 之后从 zkq 那里得到了明天上午回长春的消息，没了闭幕式和颓废活动很伤心。 估分数线，队线 300 左右，银牌 160，那铜牌就 100（？ 晚上发现没什么可以颓的了，于是从 ls 那里拿了一些资料就睡觉了。 ### Day7 （返程） 大部分人好像前一天就润了，于是早餐没什么人。。。 甚至我来早了 30min 以为没早饭。 航旅纵横提供了假的延误信息（？ 飞机降落之后从 ymm 的手机里看到了分数线，远高于预期。 190~ Ag, 140~ Cu 那 JL 今年可太惨了。 --- 今年感觉打的比较稳，该切的题都切了。 但 Day1 T2 和 Day2 T2 失误还是很大。 为什么我总会进入 "一直想一个和正解一点都无关、没有任何出路的做法而不是去观察一些新的性质" 这样的状态呢？ 两天的 T1 没有这样可能只是因为这两题不怎么需要思考。 --- 主办方各方面真的特别用心！ 感谢华东师大二附中！