NOIP2025模拟赛3总结
liujuhan
·
·
个人记录
NOIP2025模拟赛3总结
前言
太吵了，有人问题面，有人问小的知识点，甚至有人问老师自己过了没，逆天。
T1
一眼搜索，直接搜肯定会 T ，需要预处理一下。
考虑到终点的特殊性，想到可以把重点当作特殊的墙。
然后没过第 2 个大样例。
第一次因为自己没考虑到刚开始时可能会掉一下，后来想到，但还没过样例。
然后把 vis 数组由二维改为三维，就对了。
看来 vis 数组还是要按照BFS的队列来设才对。
T2
看完题和数据规模，想到先打 n=1 ，再用矩阵快速幂加速。
打完 n=1 后，突然不会了，觉得好像需要满足条件才能转移，周期条件不太会用。
于是打了 20 分走人。
T3
首先，看到区间，先想贪心。
发现包含的可以直接删去，然后就是左右端点均单调递增。
考虑 DP ，首先必须至少两维，然后发现必须知道连续删了几个才能转移。
于是，我设了三维的状态……
复杂度O(nk^2)，显然过不去。
但是状态是三维，感觉非常不能优化，于是放弃，预计 50 分。
T4
刚开始题面有问题，以为在移动过程中必须保证非负。
然后就完全不会，暴力都不会，一分没打。
赛后
$T2$ $ 20 $分，正解有两种。
一种是矩阵快速幂，可以先算一个周期内的转移矩阵，然后再矩阵加速。~~这我都想不到!~~
一种是直接推式子，考虑最后一个0计算就行。
感觉加深了我对矩阵的认识。
$T3$ $ 70 $分，多的$ 20 $分是因为前面的贪心。
正解是设二维状态，第三维完全可以用循环替代。~~这我都想不到!~~。
这样卡卡常可以过，但我的三维连开都开不下，自然过不去。
然后可以用单调队列优化，复杂度是$O(nk)$。
据说还可用$wqs$二分来做。
$T4$ $ 0 $分，赛后才知道改题面了。
正解是树上前缀和与$LCA$，就是细节较多。