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

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