符号及基本定义及约定
整除、取模、质数、算术基本定理等的定义。这部分直接 skip 了。
以下无特殊说明则默认变量为正整数，函数为数论函数。
以下用 P\mathbb{P}P 表示素数集合。
数论函数
定义域为正整数的函数被称为数论函数。
积性函数
若数论函数 f(x)f(x)f(x) 满足对于任意 a⊥ba \bot ba⊥b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为积性函数。
若数论函数 f(x)f(x)f(x) 满足对于任意 a,ba, ba,b，有 f(ab)=f(a)f(b)f(ab) = f(a) f(b)f(ab)=f(a)f(b)，则称 f(x)f(x)f(x) 为完全积性函数。
性质
若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也是积性函数。
h(x)=f(xp)h(x) = f(x ^ p)h(x)=f(xp)。
h(x)=fp(x)h(x) = f ^ p(x)h(x)=fp(x)。
h(x)=f(x)g(x)h...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1137C Museums Tour [!]
tags: 图论, Tarjan, 拓扑排序\verb|tags: 图论, Tarjan, 拓扑排序|tags: 图论, Tarjan, 拓扑排序
建分层图，然后缩点，对于每个强连通分量求出其中有多少个地方。
然后直接拓扑排序求最长路就是答案。
问题在于为什么同一天不会被重复统计。
发现天数是循环的，也就是说如果某个城市第 xxx 天和第 x+yx + yx+y 天不在同一个强连通分量里，且能从第 xxx 天到达第 x+yx + yx+y 天，那一定能从第 x+yx + yx+y 天到达第 x+2yx + 2yx+2y 天，以此类推，一定能到达 (x+dy) mod d=x(x + dy) \bmod d = x(x+dy)modd=x 天，所以 xxx 和 x+yx + yx+y 一定在同一个强连通分量里。
CF1137E Tr...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是 Ad-hoc 或构造或结论题，标 + 的是比较有意思的思维题。根据牛牛程度会增减数量。
CF1037G A Game on Strings [!!!]
观察发现，如果某次我选择了字符 ccc，则剩下的子串要么左边是 ccc，要么右边是 ccc。
也就是说，对于每个字符 ccc，设其出现的位置为 posc,1,posc,2,…,posc,kpos _ {c, 1}, pos _ {c, 2}, \ldots, pos _ {c, k}posc,1,posc,2,…,posc,k，那么有用的串就是所有 sposc,i,posc,i+1s _ {pos _ {c, i}, pos _ {c, i + 1}}sposc,i,posc,i+1 及其所有前缀和后缀。这样的串的个数为 O(n∣Σ∣)O(n \left|\Sigma\right|)O(n∣Σ∣)。
我们考虑预处理出所有有用的串的 SG 函数。
考虑将所有串按长度排序，对于每个串暴力转移。
很可惜，这样复杂...
打算系统性地学习和复习一下字符串算法。
一些算法内容比较多会拆到别的文章里。
符号与约定
首先让我们形式化地定义一下字符串的各个概念。
字符集为一个建立了全序关系的集合，用符号 Σ\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 也是个简单题，但是也没有想出来。
整场模拟赛都不在状态，实力又严重下滑。难道上了三星期文化...