Problem - 1603E - Codeforces 找找性质的好玩题。 首先考虑顺序对于题目的要求是没有关系的 对于一个排好序的序列，如果其符合条件那么其排列也肯定符合条件。 考虑对于这个排好序的序列进行操作，可以得到如果这个序列的每一个前缀都符合条件那么这个序列肯定符合条件。 既然是排好序了我们考虑对于每一个数是否有限制，限制肯定是存在的，如何找到呢？ 明显发现对于 ${1, 1,1, 1, 1}$ 是不符合条件的，考虑 $\sum_{i = 1} ^ n a_i \le a_1 \times a_n$ 的限制。 $$\begin{aligned}\sum_{i = 1} ^ n (a_i - a_1) \le a_1 \times (a_n - n) \\\end{aligned}$$ 当 $a_n = n$ 时，$\forall i \le n, a_i = i$。 $a_n \ge n$。 我们考虑 $a_n \ge n+ 1$ 的情况，考虑边界 $a_n = n+ 1$，同样是上面的式子可以得到 $\su ...

Problem - 1603F - Codeforces 看不懂题解，自己推一下。 发现直接进行操作是不方便的，我们会想到线性基，那么我们考虑通过基底进行计算。 当 $x = 0$ 的时候也就是意味着选择的位置都是线性无关的，我们考虑一个一个进行填充可以得到 $\prod_{i = 1} 2^k - 2^{i - 1}$。 显然 $n > k$ 的时候根据向量基底的性质，不可能产生线性无关的，直接为 $0$ 即可。 如果 $x \ne 0$ 我们考虑进行 $\tt Dp$，设 $f(i, r)$ 表示考虑到了 $i$ 个数，矩阵的秩是 $r$，转移方程考虑是否通过之前的位置进行表示。 我们考虑将限制 $x$ 加入进来，我们考虑任何一个数都是不能被 $x$ 所组成的，这样就是 $(n + 1) \times k$ 的矩阵了。 考虑 $a \oplus b = c \to a = b\oplus c$。 $$f(i, r) = f(i - 1, r) \times 2^{r - 1} + f(i - 1, r - 1) \ ...

I. 分组作业时间限制： 1.0 秒 空间限制： 512 MiB 相关文件： 题目目录 题目描述老师布置了分组作业。在此之前，老师将班上 $2n$ 个学生分成了 $n$ 组，每组两个人。其中 $1$ 号和 $2$ 号为一组，$3$ 号和 $4$ 号为一组，……，$2n-1$ 号和 $2n$ 号为一组。 老师让每个队伍自行安排分工。这样是否合作就成了一个大问题。大家决定用表决的方式来确定。首先每个人决定是否愿意和队友合作。不同的人因为自己的原因和分配的队友的原因，对合作的意愿不一样，对于第 $i$ 个学生，选择“愿意”会产生 $c_i$ 的不满，选择“不愿意”会产生 $d_i$ 的不满。 如果两名队友都选择“愿意”，那么根据实际情况他们可以合作或者不合作。但是如果有一名队友选择“不愿意”，那么他们只能不合作。 学生中还有 $m$ 个单向的喜欢关系，一个关系形如“$A$ 喜欢 $B$”。在这样一个关系中，如果 $A$ 没有和队友合作，且 $B$ 选择了“愿意”，$A$ 会有略微沮丧，产生 $a_i$ 的不满；如果 $A$ 表决了“不愿意”，但 $B$ 成功与队友合作，那么 $A$ 会羡慕嫉 ...

直接 $1$ 题都没出。 A 题解 | Legendgod’s Blog D 题解 | Legendgod’s Blog I 题解 | Legendgod’s Blog

时间限制： 1.0 秒 空间限制： 512 MiB 相关文件： 题目目录 题目描述小 R 和小 C 听说贵系有一门造计算机的课之后吓得连夜提交了退学申请。 开玩笑的啦！正处于大一的他们对这门课不但不害怕，甚至有些想笑。他们超强的动手能力甚至驱使他们想造一个玩意玩玩。 当然由于他们毕竟才大一，计算机专业课基本上都没上过，经过长时间的艰苦奋战，他们终于造出了一个奇怪的玩意： 这台计算机只有 $n$ 个内存单元，反而有足够多个寄存器。内存单元的编号从 $1$ 到 $n$ ，寄存器从 $n+1$ 开始往上编号。每个内存单元和寄存器可以存储一个整数。 目前他们已经设计好了一类指令：swap i, j，表示交换编号为 $i$ 和 $j$ 的单元里的数，其中 $i$ 和 $j$ 均为正整数且 $i \neq j$ 。他们打算写一段程序来测试这条指令。 最开始， $n$ 个内存单元中乱序存放着 $1\sim n$ 这些数，且每个数恰好出现一次。而每个寄存器里存放的是它的编号。 两人打算设计一段指令序列，使得计算机依次执行完这些指令后，所有内存和寄存器中的数都归位，也就是恰好等于它自己的编号。 虽然没学 ...

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 ...