专栏文章
NOIP2025模拟赛3总结
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miow3rhr
- 此快照首次捕获于
- 2025/12/03 02:06 3 个月前
- 此快照最后确认于
- 2025/12/03 02:06 3 个月前
模拟赛3总结
前言
太吵了，有人问题面，有人问小的知识点，甚至有人问老师自己过了没，逆天。
一眼搜索，直接搜肯定会，需要预处理一下。
考虑到终点的特殊性，想到可以把重点当作特殊的墙。
然后没过第个大样例。
第一次因为自己没考虑到刚开始时可能会掉一下，后来想到，但还没过样例。
然后把数组由二维改为三维，就对了。
看来数组还是要按照的队列来设才对。
看完题和数据规模，想到先打，再用矩阵快速幂加速。
打完后，突然不会了，觉得好像需要满足条件才能转移，周期条件不太会用。
于是打了分走人。
首先，看到区间，先想贪心。
发现包含的可以直接删去，然后就是左右端点均单调递增。
考虑，首先必须至少两维，然后发现必须知道连续删了几个才能转移。
于是，我设了三维的状态……
复杂度，显然过不去。
但是状态是三维，感觉非常不能优化，于是放弃，预计分。
刚开始题面有问题，以为在移动过程中必须保证非负。
然后就完全不会，暴力都不会，一分没打。
赛后
分，原因是在考虑刚开始掉一下时，没考虑到可能直接掉下去，于是RE了一个点。
分，正解有两种。
一种是矩阵快速幂，可以先算一个周期内的转移矩阵，然后再矩阵加速。这我都想不到!
一种是直接推式子，考虑最后一个0计算就行。
感觉加深了我对矩阵的认识。
分，多的分是因为前面的贪心。
正解是设二维状态，第三维完全可以用循环替代。这我都想不到!。
这样卡卡常可以过，但我的三维连开都开不下，自然过不去。
然后可以用单调队列优化，复杂度是。
据说还可用二分来做。
分，赛后才知道改题面了。
正解是树上前缀和与，就是细节较多。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...