2025牛客暑期多校训练记录

• 2025牛客暑期多校训练营1

【省流版】
I 题是正解却被卡常的，H 是比赛结束后 2s 以后过的……

---

上机情况如图

【Zlw】上来先开始看 E，看到平方差想到化成 $(a+b)(a-b)$ ，但是一开始以为是质数不合法。不过后面细想一下发现分奇偶考虑，$(a+b),(a-b)$ 奇偶性要相同，然后就能得到答案了。

【Scy】G 题题意有点迷惑，看了一遍仍然没懂，于是让 zlw 先开始敲题，趁着他卡住了一下的间隙签到完毕。

【*】前两题在 16/18 min 的时候通过。

【Zlw】接着开了 L。发现满足条件的 $a_i$ 大致是小于中位数。稍微细想可以发现是严格小于 $a_{中位+1}$ 。于是套点数据结构就可以单 $\log$ 了，不过一开始没想离散树状数组被孙✌怒骂一通，后面想想虽然离散化麻烦总归没有平衡树麻烦。还好写了离散化，据说平衡树被卡常了。

【*】但是 L 爆 int 没有发现浪费了一点时间，1h 多一点 $-1$ 通过 L，之后 zlw 和 sky 看了 K 题，scy 开始 D。D 题应该是想到第一步大与根号的质数幂次为 $1$，但是发现不太会高级筛法，加上看榜提交数量过百但无人通过，于是放弃了这题。大概空机了 15 min，sky 说大致会 K，于是开始写。

【Sky】题目大意就是有一个节点数为 $n$ 的无向图，但每个点的度数最大为 $3$，而且给定了遍历图时的走法，可以理解为固定路线。要求从节点 $i$ 出发能走到的最多边数。

一开始我理解为线路可能是链加环的形式，想了半天怎么做这个记忆化搜索，但经过讨论后发现任何一个线路都一定是环，因为题目给了“所有走廊都是双向的，因此如果从房间 $u$ 到房间 $u$ 有一扇门，那么从房间 $v$ 到房间 $u$ 也有一扇门”，然后就好做很多了，只需要遍历这个固定路线，发现环之后把环上的所有点的这个路线状态都更新答案为环的边的数量即可，然后记忆化，总复杂度 $O(n)$。

这个路线状态可以理解为，点 $u$ 向它的某个节点的边，因为同一个点可能在不同的线路环里，但是一个边一定只被一个环包含。

【*】这道题似乎走弯路走的挺久，写了将近两小时，还 TLE 了一发。Sky 在写这题的时候 scy 和 zlw 讨论了一下 H，然后 scy 独自开了 I 并认为得到了正解，并和 zlw 进行了两次确认。Sky 在写了 1.5 h 的时候遇到问题才进一步和我们讨论，再发现特殊性质以后 20 min 不到通过了这题。感觉这题耗时过久的原因出在前期考虑不充足，然后遇到问题没有即时的讨论。不过好在仍然有多线作战。

【Scy】过了 3 h 的时候开始写 I，差不多 40 min 写完，一个 $O(n^3\log n)$ 的区间 dp 加上二分优化。但是提交在 4s 时限的情况下依旧超时，意识到被卡常后和队友交流尝试多次修改，但是无果，折腾了快一个小时仍然没有通过。

【*】 I 这个卡常实在是有点无语（一方面可能牛客的评测机确实有点慢了，第一发提交测了好几分钟才返回 TLE，估计也是靠后的几个点）。赛后随便乱改，删掉了一个 $O(n)$ 的循环反而过了（$n=420$）。

【Zlw】H 是很快就有人通过的题，但是据说首发是暴力干过去的。

第一眼看没读懂题，孙✌中译中了一下仍然不是很懂，最终花费大量时间看完题目。然后孙✌提出了可以按照连续相等的段，然后计算 $\sum \left(\genfrac{}{}{0ex}{}{|s|}{2}\right)$ 的方式得到结果。结合奇特的时间复杂度要求想到了 bitset，但是发现要手写，没写过，遂抄板子。

还得把 unsigned long long 分成 $4$ 段处理，看着很复杂，遂没敢写。队友写题的时候想了一下，发现 $1$ 操作可以将差分操作延迟处理，然后处理 $[0,65535]$ 每个数做前缀和之后的结果，以及前后缀 $0$ 个数、中间的对答案的贡献，然后根据上述说的每个 ull 拆成 $4$ 份合并。最后 1h 开写，挂了一点点，查出错再交，又删了一会调试，赛后 2s 过题QAQ。

【*】说实在 I 的卡常确实有点红温了，还时不时地抢了 zlw 的机位，导致他最后几分钟才开始提交，然后发现错误的时候是 59 分，删完注释提交发现已经 too late 了。

【Scy】看题解的时候才发现 B 是和 H,I 一个难度的，是构造题，我可能会更擅长这一类题目，可以由于赛时通过人数不多，并未发现这道题目。