2026牛客暑期多校3
Bleeding unabated
比赛概况
\(4/14\)
这次比赛比上一次简单，或者说比上一次更套路。但是还是有一些关键点当时没有想明白，并且实现能力太差了。依旧坐牢。
部分题目
A
比较套路，看的第一道签到题，秒了。
K
就是给一条路径，判断每次转弯是左转，右转还是直走。一开始是队友在做，但是貌似队友不知道计算几何，分类讨论卡了很久，还吃了几发罚时。然后我也调试得受不了了，用叉乘重构过了。
L
也非常简单，一眼记忆化搜索，但是打了20分钟，还错了，然后调试了很久也不知道为什么错了，队友也不知道，在经历了千辛万苦，队友重构之后，终于发现了是vector的原因，具体原因还是不知道。 赛后才发现resize的时候不会清除原来的数。多测不清空，（）（）（）（）（）。应该改用assign,等效于clear+resize。啊
G
看错题了，打了个凸包，赛时一直以为自己凸包打错了，下来发现是题目看错了，根本不用凸包，想好一个点的贡献就行了。找到每一个点的最左上，最上左，最下右和最右下的点就行了。赛后就这样过？？？过了之后转念一想不对！构造反例，轻而易举。不过在数据足够大的，足够随机，不专门卡的情况下，通过的概率确实很高，这道题非要说的话出题人要构造很多种特殊数据来卡各种各样奇怪的概率正确的算法。看了一下正解，确实👌好啊，也确实经典，还是我太弱了。
类似于离散化，对每个相同的数的坐标进行离散化，然后枚举每一行，然后这一行的贡献就是上面的最左边的点的横坐标和下面的最右边的点的横坐标围起来的区间，统计依然用差分。
B
我不明白。为什么这么这么多人过。我觉得很难啊。还是说我太笨了，或者说因为我只学了一年多，别人都学过这个定理，就我没学过。唉。一开始队友做了一个多小时，貌似推了个错误的结论。然后我看着B题过了这么多人，我也试着做了一些，对队友的公式进行了修正，但是还是错误的。各种理解，甚至用dp做想着能不能化简，但是毫无效果还很复杂。最后另一个队友提议用卡特兰数，做了发现答案不对，想了想卡特兰数的边界斜率为1，但是这里的斜率为1/c。最后晚上看题解，看了很久，也问了ai很久终于弄明白了。
本质上就是一个带漂移的一维随机游走
Cycle Lemma：在所有 \(\binom{m}{w}\) 种输赢序列中，中途不破产的占 \(\dfrac{n}{m}\)
对任意一种情况进行轮换，然后在这种情况找到倒数n个最小点，作为结尾，同时这n个点还要满足在这种情况中前面没有比它更小的点。可以从开头看和结尾看来证明，并且其他点作为结尾是不可能满足条件的，画个图很容易证明。就是ai写得太抽象了。
F
很容易看出来用矩阵快速幂。但是我是比赛开始时看的第一题。想了一下状态有很多，但是合法的状态很少，一想到又要打表又要映射的话很麻烦，一看就不是签到题。然后我试图寻找能不能类似分治地dp，想了一会儿不会。于是去打A了。事实证明确实难打，还有很多细节。
others
在补了在补了
策略
在做前面签到题的时候，实现能力太垃了。导致占了后面很多时间有一点影响心态。
做题也不能完全跟榜死磕，毕竟知道的东西太少了，很有可能就是很经典但是很难想到的一个东西，没学过或者以前没有怎么想到思考方向的经验的话，就是想不出来，只能靠积累。
不过感觉现在也做不了什么，只能好好补题，在题目中尽可能地多榨取一些知识。