2025 sysu 校赛

_Diu_ · 2025-10-13 09:49:56 · 个人记录

A

sort

B

问题是找最长路，直接贪心，拿出 a_i 的前缀最大值算一算。

C

假设没有内切的圆，那么切点个数是 O(n) 的，分析等价于平面图边数。

加上内切的圆，切点个数还是 O(n) 的，因为每次新增一个大圆，相当于把包含在内部的圆都删掉，然后最多新增包含的圆的个数的切点。

把所有切点找出来然后暴力连边跑最短路。

没有实现，可能会卡精度。

D

考虑 ARC131F 状物，对序列最终形态 dp，覆盖后最后一定是若干个 W 形，从两边往中间或从中间往两边 dp，复杂度 O(|S||T|^2)。

注意到状态是 bool 值，采用 bitset 优化掉一个 |T| 即可通过。

E

容易写出矩乘转移，但是 O(n^3m\log n) 无法接受。有两种优化：

• 大力 MTT 版常系数线性齐次递推。。。
• 采用奴隶主优化，预处理 A^{2^k}，每次询问用一个向量乘矩阵，复杂度是 O(n^3\log n+mn^2\log n)。

F

直接哈希，要求 l-1 和 r 区间无其他字母，要求 u,y 之差相同，要求 s 奇偶性相同，要求 s/2-u 相同，用个 map 数一数即可。

G

改版前版本。

注意到做一次格雷码等价于 f_i=f_{i+1}\oplus f_i，相当于 \bmod 2 意义下加法。

注意到一次询问只关心前面有几次 \ge len 的操作。

然后是转移是组合数，直接大力 NTT 可以做到 O(nq\log n+m)，注意到转移时 01，因此也可以 bitset 做到 O(\dfrac{n^2q}w+m)。

H

手动贪心一下，队友做的。

I

注意到答案不超过 \log n，数据分治：

• 若 B^3\le n 直接暴力。
• 否则最多只有三位，枚举这三位分别是啥，列方程 ax^2+bx+c=n，求根公式解一下。

J

注意到答案只能是 ABBA' 或者 ABcBA'。

然后我们上优秀的拆分数中间的 BB 串。在滑动窗口的过程中，只有两侧有机会扩展 A/A'，否则 B 首尾相同，存在回文子串。

K

离线，每次操作暴力找到所有数操作，相同的数合并，询问到 l 的时候 push 进去，在 r 处拿出来，因为 p 互不相同，所以复杂度是调和级数。

L

我是傻*。

直接 dp，首先要求没有 i=p_i，最后套个组合数统计即可。增量构造新增一个 n 号点，要么把前面一个环拆开，要么新增一个二元环。

M

改版前版本。

这个东西很强几乎只能分快乐。

先建重构树再做差分把要求的变成树上链加树上链和。

整块整块之间和整块散块之间容易预处理。

散块散块之间咋办。我们赛时直接树剖两个 log。平衡后是一个 log。

实际上可以直接建虚树然后树上 dp 即可做到不带 log。