A. 最小公倍树时间限制： 1.0 秒 空间限制： 512 MiB 相关文件： 题目目录 题目背景听说有人嫌题面描述都太长了。 题目描述对于任意 $V\subset\mathbb{N}^*$，$|V|<+\infty$，构造一张无向完全图 $G=(V,E)$，其中 $(u, v)$ 的边权为 $u,v$ 的最小公倍数 $\mathrm{lcm}(u, v)$。称 $G$ 的最小生成树为 $V$ 的最小公倍树（LCT, Lowest Common Tree）。 现在给出 $L, R$，请你求出 $V={L, L+1, \cdots, R}$ 的最小公倍树 $LCT(V)$。 输入格式从标准输入读入数据。 输入仅一行，包括两个正整数 $L, R$。 输出格式输出到标准输出。 输出一个正整数，表示 $LCT(V)$ 的边权和。 样例1输入13 12 样例1输出1126 样例2输入16022 14076 样例2输出166140507445 样例3输入113063 77883 样例3输出13692727018161 样例4输入1325735 425533 ...

Problem - D - Codeforces 好玩题。 首先考虑如果我们已经知道了 $n$ 的划分这个题应该怎么做。 我们可以考虑枚举每一段的 $\tt gcd$ 不妨设为 $d$，之后考虑进行计算。 $$\begin{aligned}& \sum_{d = L} ^ {R} \sum_{k = 1} ^ {\lfloor \frac{R}{d} \rfloor} \mu(k) \times\binom{\lfloor \frac{R}{kd} \rfloor}{2} \\\end{aligned}$$ 也就是考虑枚举每一个公约数，之后考虑两个数的公约数是当前的 $\tt gcd$ 的贡献。 当然还要加上每个数自身的贡献。 我们既然要考虑其最小值，我们考虑上面这个式子能取到最小值的是尽量让其 $= 0$。 考虑对于一个 $[L, R]$ 只要让后面的组合数等于 $0$ 即可，我们考虑取 $d = L$ 保证限制进行考虑，可以得到 $1 \le k$，那么只需要让 $k = 1, \lfloor \frac{R}{L} ...

Problem - 1603C - Codeforces 首先很容易想到从后向前进行 $\tt Dp$，但是这个复杂度是 $O(n ^ 2)$ 的。 我们考虑我们究竟算的是什么东西，对于当前位置 $y$ 后面的位置为 $x$，如果 $y > x$ 显然要对 $y$ 进行拆分，如何拆分呢？我们肯定需要保证拆出来的若干个数不降，而且最靠左的值是尽量大的。 可以得到我们至少需要拆成 $K$ 个数 $K \ge \lceil \frac{y}{x}\rceil$，那么设最靠左的值为 $b$ 有 $b \le \lfloor\frac{y}{K}\rfloor$。 我们发现这个可以进行数列分块，也就是考虑 $a_i, a_{i + 1}$ 所进行的一种拆分，我们 $a_i$ 后面的值显然是通过 $a_{i + 1}$ 进行拆分得出的，所以我们考虑将 $a_{i + 1}$ 得出的所有拆分计算出来，这个东西是根号级别的，可以通过。 123456789101112131415161718192021222324252627282930313233343536373839404142434445 ...

Problem - 1641C - Codeforces 一道不是很会的数据结构题。 这里很明显的就是变成 $0$ 的区间是不需要考虑的，我们只需要考虑变成 $1$ 的区间。 这里会有一个问题，如果新加入了一个变成 $0$ 的区间，那么我们之前变成 $1$ 的区间就是有可能产生贡献的，所以我们要不离线要么就是通过数据结构进行存储。 笔者发现离线一下子不是很好想，所以考虑使用数据结构进行维护，根据上述的条件发现我们不能时刻保证手上都有答案，所以需要再进行询问的时候来计算答案。 不妨考虑进行询问 $x$，显然如果 $x$ 已经被明确说明过没有病直接回答 NO 即可，剩下的就是可能有病的情况，考虑什么样的一个区间才可能能确认 $x$ 是有病的，显然就是一个区间只有 $x$ 是不确定的，我们考虑找到这个区间的范围，就是最左边连续的确定没病的位置 $L$ 和最右边的 $R$，我们考虑对于 $1$ 区间的左端点在 $[L, x]$ 之间如果右端点 $\le R$ 那么肯定是合法的。 显然右端点肯定不会 $< x$ 不然区间之间就会产生矛盾。 我们通过维护区间最小的右端点即可，使用线段 ...

Problem - 1641D - Codeforces 事实上有很多种做法，比如随机化等等。 我们考虑如何判断两个集合是不同的从而推广到一个集合和多个集合的情况。 显然暴力判断复杂度是不能接受的，我们考虑通过枚举集合进行判断。 我们考虑一个式子 $\sum_{S_1 \subset A} \sum_{S_2 \subset B} [S_1 == S_2] $ 表示总共有多少个集合是相同的，也就是不妨设 $A \cap B = S$，那么本质上就是 $\sum_{i \ge 0} \binom{|S|} {i} $，我们灵光一闪发现 $\sum_{i \ge 0} \binom{n} {i} (-1) ^ i = [n == 0] $，我们可以通过这种方法来快速判断集合是否有交。 那么很简单，对于判断 $A$ 和若干个集合是否有交，我们可以考虑对于若干个集合建立一个扩展 $\tt Trie$ 树，之后直接暴力枚举 $A$ 就可以了，复杂度是 $2^m$。 之后我们考虑进行贪心，我们不妨将每个数组按照 $w$ 的大小进行排序，之 ...

一些定理和定义就不说了史上最通俗的后缀自动机详解 - KesdiaelKen 的博客 - 洛谷博客这里都有。 我们具体说一下后缀自动机初学者难理解的地方。 什么是后缀自动机：本质就是一个 $\tt Trie$ 树和 $\tt parent$ 树重叠的东西。 三种分类讨论怎么理解：首先我们清楚我们加入的是一个点（字符 c ）而不是一个串，我们加入了一个点，我们通过 $\tt Trie$ 树的转移不妨设其为 $\tt trans[u][c]$ 表示在 $u$ 之后加入一个字符 c 得到的位置。 显然从空节点开始走到达某个节点 $u$ 构成一个字符串，同时也是原串的子串。 为了方便说明我们不妨设没有加入字符 c 的串是原串，加入之后为当前串。 第一种情况 我们通过跳后缀链接，尝试找到是否存在原串后缀加上节点 c 得到的节点。如果不存在那么我们新加入的 c 显然是不存在的，我们直接链接根节点即可。 为什么说是不存在的，考虑直接从根节点都走一步都走不到 c。 第二种情况 我们幸运地找到了当前串的后缀，不妨设节点为 $u$，而且更加幸运的是 $u$ 表示集合与 $\tt trans[u ...

Problem - 1634E - Codeforces 注意都是偶数的性质，我们尝试考虑建立欧拉回路。 因为欧拉回路上每个节点的入度等于出度，我们直接将限制建立成点即可。 也就是对于每个数组建一个点，每种颜色建立一个点，如果数组 $i$ 中有颜色 $j$ 那么我们就建立无向边 $(i, j)$，我们将这个位置的标号当做边权，不妨钦定 $i \to j$ 的边我们将其设为 L，否则就是 R。 我们可以发现对于同一行连出去的边肯定都是在当前数组内的，所以直接开桶统计答案即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include <bits/stdc++.h ...

Problem - 1633E - Codeforces 首先发现询问次数是很多的，但是点数和边数是很少的。 所以我们总共有两个方向可以走一个是优化生成树，但是可以发现不管是 $\tt P, K, B$ 这些算法都是不行的，我们只能考虑另一个方法减少求生成树的次数。 比较浅层来说可以发现我们可以对于边进行排序，那么如果两个询问 $x_1, x_2$ 其在两条边 $w_1, w_2$ 之间，我们设边的中点为 $\tt mid = \dfrac{w_1 + w_2}{2}$ 那么如果其在中点的同一边那么就不需要再进行操作了。 我们可以通过这个将所有的边都进行如上操作，之后离线询问即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210 ...