专栏文章

2025 sysu 校赛

__Diu_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmf2gf
此快照首次捕获于
2025/12/02 04:47
3 个月前
此快照最后确认于
2025/12/02 04:47
3 个月前
查看原文

A

sort

B

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

C

假设没有内切的圆，那么切点个数是 O(n)O(n) 的，分析等价于平面图边数。
加上内切的圆，切点个数还是 O(n)O(n) 的，因为每次新增一个大圆，相当于把包含在内部的圆都删掉，然后最多新增包含的圆的个数的切点。
把所有切点找出来然后暴力连边跑最短路。
没有实现，可能会卡精度。

D

考虑 ARC131F 状物，对序列最终形态 dp，覆盖后最后一定是若干个 W 形，从两边往中间或从中间往两边 dp，复杂度 O(∣S∣∣T∣2)O(|S||T|^2)。
注意到状态是 bool 值，采用 bitset 优化掉一个 ∣T∣|T| 即可通过。

E

容易写出矩乘转移，但是 O(n3mlog⁡n)O(n^3m\log n) 无法接受。有两种优化：
  • 大力 MTT 版常系数线性齐次递推。。。
  • 采用奴隶主优化，预处理 A2kA^{2^k}，每次询问用一个向量乘矩阵，复杂度是 O(n3log⁡n+mn2log⁡n)O(n^3\log n+mn^2\log n)。

F

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

G

改版前版本。
注意到做一次格雷码等价于 fi=fi+1⊕fif_i=f_{i+1}\oplus f_i，相当于  mod 2\bmod 2 意义下加法。
注意到一次询问只关心前面有几次 ≥len\ge len 的操作。
然后是转移是组合数，直接大力 NTT 可以做到 O(nqlog⁡n+m)O(nq\log n+m)，注意到转移时 01，因此也可以 bitset 做到 O(n2qw+m)O(\dfrac{n^2q}w+m)。

H

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

I

注意到答案不超过 log⁡n\log n，数据分治：
  • 若 B3≤nB^3\le n 直接暴力。
  • 否则最多只有三位，枚举这三位分别是啥，列方程 ax2+bx+c=nax^2+bx+c=n，求根公式解一下。

J

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

K

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

L

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

M

改版前版本。
这个东西很强几乎只能分快乐。
先建重构树再做差分把要求的变成树上链加树上链和。
整块整块之间和整块散块之间容易预处理。
散块散块之间咋办。我们赛时直接树剖两个 log。平衡后是一个 log。
实际上可以直接建虚树然后树上 dp 即可做到不带 log。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...