考完 Day1 后本来不想写的，Day2 考完后还是勉强写一下。
Day -114514
太菜了，省选垫底，肯定是没有进队的，D类也没买。于是参加方法是把题留着vp，一切关于题的东西（u群，NOI游记等）都在vp前不看，我们机房人均赚 2w 。
Day 1
看题，T1......嗯，众数，可以摩尔投票之类的，但不慌，先想个暴力之类的.......于是没有秒T1。继续看 T2，感觉判定可以贪心，好像要递归，细节不太会......T3，可恶，又是这种题面，瞥了一眼大概后就回去看T1了。
一开始想暴力就一发不可收拾，一段时间内T1的思路竟然只有桶，连删除操作都不会，考场降智属于是。想了很久发现一个性质，查询的时候能成为答案的数一定在其中一个序列里是答案，但当时只会暴力，成功把暴力的复杂度降到了 \(\mathcal{O}(n^2+nm)\) （不知道这是啥复杂度，反正考场上想的），但优化前和优化后没有区别，都非常的憨。
没想出正解，就先没写。又去看 T2，实现了一下按值从小到大把序列分段判断的方法。好像是能过几个样例的，但调了一会儿后发现算法有一点问题，有个地方要枚举出头的长度。但想着这玩意儿没法儿做计数，就换成了暴搜，先拿点分。
T3 又读了很久题，理解了很久才懂题目到底要干啥。想了一会儿发现只会链的分块做法，于是尝试写了一下。由于技术原因，机房采用了特殊手段调试 T3 ，我不是很熟悉，所以也耽搁了点时间。写到一般发现时间复杂度有点劣，甚至到了 \(\mathcal{O}(n\sqrt n\log n)\) ，但没时间了，就把正确性调过就没管了。
回去想 T1（此时只剩不到 \(2\) 小时了），有一点慌，毕竟暴力还没打，而且感觉正解要打一会儿，于是就先把暴力打了。打完之后想到可以线段树合并做（太菜了，线段树合并该秒的），但是查询线段树合并复杂度是假的，于是又卡住了，中途想过把 \(m\) 个点一起在线段树上跑，但感觉怪怪的就没想（这就是我考后补题的写法）。还剩一个小时的时候就不敢继续想了，打了一点部分分，再检查了一下，大概就结束了。
于是直接原地爆炸。
\[55+0+0=55 \]只能用惨形容，简直跟联合省选一样。
T1 的链表细节挂了，T2 爆搜全局记忆化直接萎掉，T3 分块T了......
隔壁机房新初三新高一人均切 T1 ，我无地自容。知道算法后意识到自己很可笑，一开始就想到的摩尔投票之后便再也没有记起过。银牌要没了，保银争金变成保铜争银了。
下午补题。半个多小时就把 T1 过了，T2 是个 dp 套 dp，感觉一堆结论和细节，大概理解做法了，但没有写。晚上找了点省选题做，有、意思。
Day 2
虽然 Day1 的时候被 lzy 透露了 D2 T1 是树哈希，但是看到题目之后发现透露了没用。树同构以及那个出题人都告诉你是树哈希的提示...... 想了一会儿后就会了爆搜+树哈希的做法，感觉可以过，因为数据范围不大，而且不太能卡，正好暑假刚学了树哈希，于是一个多小时后就没管 T1 了。
T2 和 T3 感觉都需要先有点结论再做。T2 的一些基础性质都观察到了，但用处不大，于是从特殊性质入手。\(A\) 性质强但分很多，让我难以理解，于是一会儿便胡出了 \(1\) 先放，\(0\) 找第一个没有放的位置放的贪心。但是被顺序问题和没有限制的位置怎么安排卡住了。又想了一下 \(B\) 性质，感觉可以贪心地放每个位置（也就是 gyh 题解里的局部最优），但具体细节没想，因为感觉内部的逆序对没法处理。
想了一个小时左右发现 T2 没啥进展就去想 T3 了。读懂题看数据范围发现 \(k=3\) 和 \(k=4\) 的部分都分很少，应该是可以观察简单性质贪心。于是先想 \(k=3\) ，发现 \(2\) 尽量多就行了，忘了还有变量之间的约束，还以为直接输出 \(nv_2\) 就行了（。看了样例之后才想起来，但 \(2\) 尽量多的贪心还是没有问题。不到一分钟便想到了不是 \(2\) 当且仅当 \(l=r\neq2\) 或者被这样的位置限制了，并且那个限制一定是 \(b=0\) ，所以把 \(b=0\) 的限制当成边连起来，并查集搞一搞就好了。于是写完就过了样例。又想了一下 \(k=4\) ，大概就多了两个东西，一个是 \(b=1\) 的限制，一个是有的位置 \(2\) 和 \(3\) 都可以选。反正前面的部分大概是可以照搬的，然后一通贪心发现被强制成 \(1\) 和 \(4\) 的连通块连出去 \(b=1\) 的边是必须钦定成 \(2\) 和 \(3\) 的，其他只要有 \(l\le 2,3\le r\) 就可以随便选。于是写完调了一会儿就又过了样例。
剩下的时间继续地想 T2 ，但还是没有进展，就把暴力分打了。还剩半个多小时，感觉需要检查一下 T1，因为 T1 不能挂。于是写了个数据生成器造个大数据乱搞一下，发现一搞一个比较极限的数据就 T 了，还以为复杂度假了。结果是树哈希写得太憨，冲突了（被合理的哈希了（悲）），写了个双哈希，写完发现加一个子树大小判断就行，于是又注释掉了。
Day 2 还行
\[100+28+20=148 \]最后竟然还有银牌。
但看题解后发现自己 T2 又犯憨了，但也不能完全是，也有一点能力问题，感觉这种题见少了，因为考场上的想法基本都是对的，只是缺乏后续。
大概算了一下，发现自己实力勉强可以打到金牌线（但或许要 rp 拉满），但始终是技不如人，还有的练，但又没太多时间练了。
下午和晚上把两天的 T2 补了，顺便看了点游记，又去隔壁机房对着 gyh 的题解讲 D2T2，最后写我自己的游记，于是我的 NOI2022 之旅结束了。至于两天的 T3 ，暂时得咕一段时间了。
标签：NOI,于是,T2,T3,T1,2022,哈希,游记,贪心 From： https://www.cnblogs.com/Sword-K/p/16840853.html