Q779’s Blog

洛谷P5283 [十二省联考 2019] 异或粽子 题解 题目链接：P5283 [十二省联考 2019] 异或粽子 题意： 小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。 小粽面前有 \(n\) 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 \(1\) 到 \(n\)。第 \(i\) 种馅儿具有一个非负整数的属性值 \(a_i\)。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 \(k\) 个粽子。 小粽的做法是：选两个整数数 \(l\), \(r\)，满足 \(1 \le l \le r \le n\)，将编号在 \([l, r]\) 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符） 小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的 粽子。 小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！ 输入格式： 第一行两个正整数 \(n\...

CF995E Number Clicker 题解 题目链接：Number Clicker 题意： 有三种操作： 令 \(u \gets u + 1 \pmod p\) 令 \(u \gets u - 1 \pmod{p}\) 令 \(u \gets u^{p-2} \pmod{p}\) 给定 \(u,v\) 和质数 \(p\) ，构造一种方案让 \(u\) 变成 \(v\) ，操作数不超过 \(200\) 次。 输入格式： 一行， \(u,v,p\) 。 输出格式： 第一行输出操作次数，第二行输出每次操作的序号 \(c_i(1\le c_i \le 3)\) 。 数据范围： \(0 \le u,v \le p - 1,~3 \le p \le 10^9 + 9\) 。 直接 bfs 的话肯定是过不了的，不过因为这里的操作都是可逆的，所以我们可以尝试双向 bfs 。 因为 \(u^{p-2} \bmod{p}\) 的值难以预测，所以 \(u \gets u^{p-2} \pmod{p}\) 这个操作可以近似看作随机的。 由于我们的算法可以看作在 \([0,p-1]\) 随机...

[AGC006E] Rotate 3x3 题解 题目链接：[AGC006E] Rotate 3x3 题意： 有一个 \(3\) 行 \(N\) 列的初始矩阵，\((i,j)\) 位置的数为 \(i+3\times j-3\)。 然后有一个这样的操作：选择一个 \(3 \times 3\) 的子矩阵，将这个子矩阵旋转 \(180°\)（具体见下面的图）。 现在给出一个 \(3\) 行 \(N\) 列的矩阵（矩阵中的数各不相同） 问能否通过若干次上述操作将初始矩阵变为给定的矩阵。 输入格式： 第一行给出 \(n\) ，然后三行共 \(3 \times n\) 个数表示初始矩阵。 输出格式： 一行，答案。 数据范围： \(1\le n \le 10^5,~1 \le a_{i,j} \le 3n\) 。 看题解区好多 \(\mathcal{O}(n)\) 的神仙解法，我来讲一讲好理解的 \(\mathcal{O}(n \log n)\) 解法吧。 首先判掉明显不对的情况，这样每一行就可以看作一个数，并且有正负之分 注意到一次旋转只会交换奇偶性相同的相邻两列，即 \(i\) 和 ...

[AGC003C] BBuBBBlesort! 题解 题目链接：[AGC003C] BBuBBBlesort! 题意： 给定一个序列 \(a\)，元素两两不同，可以使用两种操作。 翻转相邻两个元素。 翻转相邻三个元素。 问怎么操作使这个序列变成升序，并使操作一的次数最少。输出这个最少的次数。 输入：\(n\) 和 \(a_i\) 。输出：答案。 数据范围： \(1\le n \le 10^5,~0 \le a_i \le 10^9\) ​。 先离散化一下（不用去重），这样权值就是正确的编号。 可以发现，只使用操作二可以将奇数位&偶数位的数分别排序 但是在奇数位上的数编号可能不是偶数， 这种情况必须用一下操作一，把奇数位和偶数位上错位的两个憨憨交换一下。 时间复杂度 \(\mathcal{O}(n \log n)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x, ...

洛谷P4691 Nephren Ruq Insania 题解 本题和 P3934 [Ynoi2016] 炸脖龙 I 完全一致。 题目链接：P4691 Nephren Ruq Insania（本题没有数据，需要在 P3934 提交） 题意： 奈芙莲·卢可·印萨尼亚 (Nephren-Ruq-Insania) 威廉想要救下奈芙莲，但是他自己也已经处于崩溃的边缘。 冥冥之中他想起了曾经学习过的一种魔法。在这最后一刻，或许已经是唯一的办法了。 这种魔法操作的对象是一个咒语组成的序列，每一个单独的咒语拥有自己的法力值。 威廉需要不断地按照之前的记忆，对某一段区间的法力值加上一个数，或者求出某一段区间的法咒共鸣。 法咒共鸣具体而言是这么计算的： 对于区间 \([l,r]\) ， 查询 \[ \mathrm{pow}(a_l,\,\mathrm{pow}(a_{l+1},\,\mathrm{pow}(a_{l+1},\,\cdots))) \bmod p \] 一直到 \(\mathrm{pow}(a_r,\,1)\) 。其中 \(\mathrm{pow}(a,b)\) 表示 \(a^b\...

洛谷P5043 【模板】树同构（[BJOI2015]树的同构） 题解 题目链接：P5043 【模板】树同构（[BJOI2015]树的同构） 题意： 树是一种很常见的数据结构。 我们把 \(N\) 个点，\(N-1\) 条边的连通无向图称为树。 若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。 对于两个树 \(T_1\) 和 \(T_2\)，如果能够把树 \(T_1\) 的所有点重新标号，使得树 \(T_1\) 和树 \(T_2\) 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。 现在，给你 \(M\) 个无根树，请你把它们按同构关系分成若干个等价类。 输入格式： 第一行，一个整数 \(M\)。 接下来 \(M\) 行，每行包含若干个整数，表示一个树。第一个整数 \(N\)表示点数。接下来 \(N\) 个整数，依次表示编号为 \(1\) 到 \(N\) 的每个点的父亲结点的编号。根节点父亲结点编号为 \(0\)。 输出格式： 输出 \(M\) 行，每行一个整数，表示与每个树同构的树的最小编号。 数据范围： \(1\leq N,M\leq...

洛谷P5926 [JSOI2009] 面试的考验 题解 题目链接：P5926 [JSOI2009] 面试的考验 题意： 求区间最接近且不相等的两数之差的绝对值。最接近指数值上最接近。 输入格式： 第一行输入两个整数 \(N,Q\)，分别代表序列的长度和询问的个数。 第二行包含 \(N\) 个由一个空格分开的正整数，代表了整个序列，从左向右依次编号为 \(A_1, A_2……A_n\)。 接下来 \(Q\) 行，每行两个整数 \(i,j\) 表示了一个询问区间。 输入数据保证 \(1\le i<j\le N\)。 输出格式： 对于每一个询问输出一行，为所问区间中最接近两个数之差的绝对值。 数据范围： \(1\le N,Q\le10^5,1\le A_i\le10^9\)。数据为全部纯随机生成。 思路是考察对答案有贡献的点对。 对于 \(i < j,~a_i < a_j\) 的点对，其中 \(i\) 固定。 如果 \(x\) 是 \(i\) 之后对答案有贡献的第一个点，则 \(a_x \in [a_i + 1, +\infty)\) 且 \(x\) 是 \([i...

note[19] 题：问 \[ \mathcal{O}(\log (n!)) \] 解： \[ \begin{aligned} \mathcal{O}(\log (n!)) &= \mathcal{O}\left(\int_1^n \log x \, \mathrm{d} x\right) \\[8pt] &= \mathcal{O}\left( {(x-1)\log x\Big|_1^n} \right) \\[8pt] &= \mathcal{O}(n \log n) \end{aligned} \] 这里用到了 \(\int \log x \, \mathrm{d}x\) 的公式 \[ \int \log x \, \mathrm{d}x = (x - 1) \log x + C \] 证明： 考虑分部积分法 \[ \int u \, \mathrm{d} v = uv - \int v \, \mathrm{d} u \] 其中 \(u = \log x,~ \mathrm{d}u = \frac{1}{x}\mathrm{d}x,~v = x,...

洛谷P2408 不同子串个数 题解 题目链接：P2408 不同子串个数 题意： 给你一个长为 \(n\)​ 的字符串，求本质不同的子串的个数。 输入格式： 第一行一个整数 \(n\)。 接下来一行 \(n\) 个字符表示给出的字符串。 输出格式： 一行一个整数，表示不一样的子串个数。 数据范围： 保证 \(1 \leq n \le 10^5\)，字符串中只有小写英文字母。 不要把这题跟 P3181 搞混了，反正我自己搞混了 考虑构建后缀数组，那么对于排名为 \(i\) 的后缀，它的贡献为 \(n-\texttt{sa[i]}+1-\texttt{height[i]}\) 。 因为所有的后缀按字典序排序，不存在前缀 \(S\) 不为 \(\mathrm{LCP}(i-1,i)\) 却为 \(\mathrm{LCP}(i-k,i)\) ，其中 \(k > 1\) 。 所以这样计算贡献不重不漏。于是答案就是 \[ \frac{n(n+1)}{2} - \sum_{i=2}^n \texttt{height[i]} \] 时间复杂度 \(\mathcal{O}(n \log n...

SP2059 CERC07S - Robotic Sort 题解 题目链接：CERC07S - Robotic Sort 题意： 你要为一个机器人编写软件，来对一些物品进行排序。 这个机器人每次能够选择任意数量的连续物品将其旋转。它的操作遵循一个简单的原则： 第一次操作时，找到高度最低的物品的位置 \(P_1\) ，然后把区间 \([1,P_1]\) 翻转； 第二次操作时，找到剩余物品中高度最低的物品的位置 \(P_2\) ，然后把区间 \([2,P_2]\) 翻转； 以此类推，第 \(i\) 次操作时，找到剩余物品中高度最低的物品的位置\(P_i\)，然后把区间 \([i,P_i]\) 翻转。 注意，如果有高度相同的物品，则应保持其排序后的相对顺序与初始的相对顺序相同。 精美插图： 输入格式： 输入包含多个场景。每个场景由两行描述。第一行包含一个整数 \(N\)，表示样本数量，\(1 \le N \le 10^5\)。第二行列出了恰好 \(N\) 个用空格分隔的正整数，这些整数指定了每个样本的高度及其初始顺序。 最后一个场景以包含零的一行结束。（scenario 在这里翻译...

洛谷P3391 【模板】文艺平衡树 题解 题目链接：P3391 【模板】文艺平衡树 题意： 您需要写一种数据结构（可参考题目标题），来维护一个有序数列。 其中需要提供以下操作：翻转一个区间。 例如原有序序列是 \(5\ 4\ 3\ 2\ 1\)，翻转区间是 \([2,4]\) 的话，结果是 \(5\ 2\ 3\ 4\ 1\)。 输入格式： 第一行两个正整数 \(n,m\)，表示序列长度与操作个数。序列中第 \(i\) 项初始为 \(i\)。 接下来 \(m\) 行，每行两个正整数 \(l,r\)​，表示翻转的区间。 输出格式： 输出一行 \(n\) 个正整数，表示原始序列经过 \(m\) 次变换后的结果。 数据范围： 对于 \(100\%\) 的数据，$1 n, m $，\(1 \le l \le r \le n\)。 文艺平衡树其实蛮好理解的。它和平衡树的区别在于，维护的是每个权值的编号。 也就是说我们不关心权值（权值不就是输出用么），我们只关心他们编号的顺序。 那么翻转一个区间只需要把 \(l\) 的前驱 splay 到根节点，再把 \(r\) 的后继 splay 到 \...

洛谷P5826 【模板】子序列自动机 题解 题目链接：P5826 【模板】子序列自动机 题意： 给定一个长度为 \(n\) 的正整数序列 \(a\) ，有 \(q\) 次询问。 第 \(i\) 次询问给定一个长度为 \(L_i\) 的序列 \(b_i\)，请你判断 \(b_i\) 是不是 \(a\) 的子序列。 序列 \(a\) 和所有 \(b_i\) 中的元素都不大于一个给定的正整数 \(m\)​​。 省流：给定一个主序列，每次给出一个序列，判断是否为其子序列。 输入格式： 每个测试点有且仅有一组数据。 输入的第一行是四个用空格隔开的整数，分别代表 \(type,~n,~q,~m\)。其中 \(type\) 代表测试点所在的子任务编号，其余变量的含义见题目描述。 输入的第二行是 \(n\) 个用空格隔开的整数，第 \(i\) 个数字代表序列 \(a\) 的第 \(i\) 个元素 \(a_i\)。 第 \(3\) 行至第 \((q + 2)\) 行，每行代表一次询问。第 \((i + 2)\) 行的输入格式为： 第 \((i + 2)\) 行的行首有一个整数 \(l_i\)，...