打算系统性地学习和复习一下字符串算法。
一些算法内容比较多会拆到别的文章里。
符号与约定
首先让我们形式化地定义一下字符串的各个概念。
字符集为一个建立了全序关系的集合，用符号 Σ\SigmaΣ 来表示。其中的元素被称为字符。
Tip: 有些时候全序关系不是必须的。
字符串 sss 是一个由若干字符按顺序排列而成的序列。
下文默认字符串下标从 111 开始。
定义 sis_isi 表示字符串 sss 的第 iii 个字符。
定义 ∣s∣\left|s\right|∣s∣ 为字符串 sss 的长度。
空串即为不包含任何字符，∣s∣=0\left|s\right| = 0∣s∣=0 的字符串。
我们定义字符与字符、字符与字符串、字符串与字符、字符串与字符串之间的拼接表示将这两个字符或字符串按顺序拼在一起得到的字符串，写作 s+ts + ts+t 或 ststst。sks^ksk 表示 kkk 个 sss 拼接。
字符串 sss 的一个子串 s[l,r]s_{[l, r]}s[l,r] 表示 sl,sl+1,…srs_l, s_{l + 1}, \ldots s_{r}sl,s...
感觉最近越来越摆了。
所以打算记录一下做到的好题。
联合省选 2023 Day1 T2 城市建造
称额外修建的道路连接的城市为标记点，容易发现任意两个标记点之间的边都必须是额外修建的道路。
题目要求在删除新增的道路后任意两个标记点不连通，所以对于任意一个点双，如果标记了两个点，则必须标记其余所有点。
关于为什么不是边双：
然后进一步观察发现，删除的点双必须是连通的。
于是考虑建圆方树 DP。
然后求助了 djwj233。
首先对于 k=0k = 0k=0，块的大小必须是 nnn 的因数，只有 O(n)O(\sqrt{n})O(n) 个。
对于 k=1k = 1k=1，块的大小只可能是 ⌊ns⌋\left\lfloor\dfrac{n}{s}\right\rfloor⌊sn⌋ 或 ⌈ns⌉\left\lceil\dfrac{n}{s}\right\rceil⌈sn⌉（其中 sss 为任意正整数），简单分析发现也只有 O(n)O(\sqrt{n})O(n) 种。
于是可以考虑枚举块的大小 BBB，再进行 DP。
我们发现树上连通块一定有一个深度最小的点，且其他点都在它的子...
Problem
洛谷 P7987 [USACO21DEC] Paired Up G
题目大意：
有 nnn 个点，其中第 iii 个点位置为 xix_ixi，权值为 yiy_iyi。若两个点 i,ji, ji,j 满足 ∣xi−xj∣≤k|x_i - x_j| \le k∣xi−xj∣≤k，则这两个点之间有一条边。
求一个匹配，在满足其为极大匹配的情况下匹配点的权值和最大/最小。
求总权值和与匹配点的权值和的差。
Solution
提供一种不同于洛谷题解区的解法。
结论：作为答案的匹配中的任意两对匹配 (a,b)(a, b)(a,b) 和 (c,d)(c, d)(c,d)，区间 [a,b][a, b][a,b] 与区间 [c,d][c, d][c,d] 一定不交。
这个可以用调整法证明。如果两个匹配 (a,b)(a, b)(a,b) 和 (c,d)(c, d)(c,d) 满足 a<c<b<da < c < b < da<c<b<d，则可以将匹配调整成 (a,c)(a, c)(a,c) 和 (b,d)(b, d)(b...
联合省选 2023 游记
Day -9
晚上得到消息，ZJ 初中生 CSP-S 前 202020 可以参加联合省选。感恩浙江！
Day -7
停课第一天，houzhiyuan 模拟赛。
T1 倒不是很难，但是调了 2.5h2.5h2.5h，后面两题暴力写挂，喜提 100100100 分好成绩（悲
Day -6
wcr 模拟赛。
T1 是这个题一个非常经典的 Trick：对于二进制下每一位分别计算贡献。
然后这个 Trick 在 101010 月某次 Sigma Cup 里还出现过，结果一整场完全没有想到这个东西。
最后三个暴力喜提 100100100 分。
感觉实力严重下滑了。
然后下面还有一堆 faker 法典。
Day -5
在家颓废，补了一下模拟赛。感觉精神状态非常不好。
Day -4
又是模拟赛。T1 题意转化后就是从集合中选最少的元素使得 gcd=1\gcd = 1gcd=1。然后想了一整场这个东西怎么做，最后极限写完，然而复杂度不大对劲，喜提 000 分。
T2 也是个简单题，但是也没有想出来。
整场模拟赛都不在状态，实力又严重下滑。难道上了三星期文化...