2024 10.5&10.6模拟赛总结

一句话总结：打的稀烂。

10.6

\(T1\) 没什么好说的。

\(T2\) 是我不喜欢的类型。首先看到前 \(K\) 大马上就想到了二分和堆，但是想了半天也不知道堆怎么由一种状态推广到多种状态，并且要不重不漏、效率高，二分也没想出来怎么 \(check\)。赛后听了评讲才发现堆可以记录一个三元组 \((l,x,r)\) 分别表示左边的第一个 \(1\)、上一步操作位置、右边的第一个 \(1\)，然后就可以由一种状态推到两种状态。二分也可以直接进行 \(DFS\)，搜到大于等于 \(mid\) 的就直接方案加一，否则就直接返回，由于每次都能扩展出新的状态，所以时间复杂度也是对的。考试的时候就是卡在这里了，导致最后一分没得。

\(T3\) 看了一下，不会处理交换，暴力肯定会 \(TLE\)，遂没看多久就放弃了。正解有点贪心的思想，先按价格排序，然后用前面价格小的去替换后面口感值打的，然后分讨一下再跑个背包就行了。对于与贪心相关的东西还是有点无能为力，总是想不到怎么贪。

\(T4\) 没想到 \(O(n^2 \log_2 n)\) 能得到 \(O(n^2)\) 的 \(45\) 分。正解其实就是推出一个性质：如果两个序列都选，则必定至少有一个选择区间的权值和大于其整个序列权值和的一半，就是要经过那个序列的带权中点，然后就维护一下每个数所能取到的最大左端点、最小右端点，上一棵线段树维护一下就行了。主要是没有发现性质，导致也想不出来后面的步骤。

总结

对于一些套路的掌握能力（\(T2\)）还不够，还需要继续多做相关的题目。贪心相关还是很不行，可能是因为我的思维能力差，看来还是要注重提升自己的思维能力。性质总是推敲不出来，可能需要分配更多的时间给这种题，再加上一些深层次的思考。

10.7

\(T1\) 差点把我搞死。马上就想到了二维 \(DP\)，但是由于脑子比较混乱就一直推不出来，还推了一些奇怪的转移。最后好歹还是推出来了，写出了 \(O(n^3)\) 的做法，但是不知道怎么了，写 \(O(n^2)\) 的优化时老是写错，最后重构了三遍才写对，也不知道之前是哪里写错了。而且由于做法常数太大（没有除以 \(3\)）而导致被卡常（\(98 pts\)）。

\(T2\) 马上就知道是贪心，但是不知道最小值怎么搞。感觉最大值的求法比较显然，然后就写了一个我也不知道是什么东西的做法（反正既不是单调栈也不是笛卡尔树），最后过不了样例，评测喜提 \(0pts\)。正解比较神奇，先把它转化成差分序列，然后就变成了在上面选一个数加一，选一个数减一（其实我想到了，但是没想到后面怎么做）。由于平方相加交叉小于等于包含，所以直接用离自己最远的负数和自己这个整数操作就行了，时间复杂度线性。

\(T3\) 看着就是一个难写的东西，看了一眼就没看了（理解题意还花了一些时间）。正解肯定是 \(DP\)，因为涉及对一个大模数取模。直接对于以一个点为左上角的横竖方案进行 \(DP\)，但是这样可能有状态之间互相重叠的情况，会算重，所以容斥一下就行了（手玩系数）。

\(T4\) 就是一个比较板的仙人掌，感觉会很难写就没怎么想。可以先建一棵 \(Block-Cut \space Tree\) 或者圆方树，然后对于每一条树边/环边分讨一下这条边带来的变化量就行了。可能对于学过的人来说就是纯纯码农题。

总结

计数 \(DP\) 总是要想很久（包括9.25的 \(NOIP\) 模拟赛也是），感觉还是不太熟练，还是要多做题增加熟练度。贪心是真的不行，连着两场考试都没做出来，说明思维还有很大的提升空间，而且想象力可能还不够，猜结论（但是前提还是要经过一些推导）能力很弱。网格图上的问题一直不擅长，甚至有点恐惧，还是要多练题才行。