Q779’s Blog

AcWing4699 如此编码 题解 题目链接：AcWing4699 如此编码 题意： 给定长度为 \(n\) 的数组 \(a_i\) 和 \(m\) ，求 \(b_i\) ，其中 \(m\) 的定义如下： 记 \(c_i = \prod_{j = 1}^{i}a_i\) ，定义 \(c_0=1\) ，则 \(m = \sum_{i = 1}^{n} c_{i-1}\times b_i\) 输入格式： 第一行给出 \(n,m\) ，第二行给出 \(a_i\) 。 输出格式： 一行，\(n\) 个数，表示 \(b_i\) 。 数据范围： \(1\le n\le 20,~a_i\ge 2,~0\le b_i\le a_i,~ c_n \le 10^9\) 把 \(m\) 的定义式展开 \[ \textstyle m = b_1 + b_2a_1 + b_3a_1a_2 + \cdots + b_n\times\prod_{i=1}^{n}a_i \] 可以发现，当所有 \(a_i\) 相等时，这就是一个 \(a_i\) 进制的数。 因此我们从进制的角度出发。因为 \(b_i &l...

AcWing5203 数学作业 题解 题目链接：AcWing5203 数学作业 题意： 你的数学老师布置了一项作业。 给定一个整数 \(N\) ，请你构造一个长度为 \(N\) 的整数序列 \(A_1,A_2, \ldots, A_N\) ，其中 \(1 \leq A_i \leq 10^9\) 。 构造序列需要同时满足 \(M\) 个要求，其中第 \(i\) 个要求是构造序列的连续子序列 \(A_{X_i}, \cdots, A_{Y_i}\left(1 \leq X_i \leq Y_i \leq N\right)\) 的最大公约数必须恰好等于 \(Z_i\) 。 请你输出一个满足所有要求的有效序列。 输入格式： 第一行包含两个整数 \(N, M\) 。 接下来 \(M\) 行，每行包含三个整数 \(X_i, Y_i, Z_i\) 。 输出格式： 如果满足所有要求的有效序列不存在，则输出 Impossible。 如果满足所有要求的有效序列存在，则在一行内输出该序列。 如果方案不唯一，输出任意合理方案均可。 数据范围： \(1 \leq N, M \leq 1.5 \time...

洛谷P9089 「SvR-2」Work 题解 题目链接：P9089 「SvR-2」Work 题意： 给定 \(n\) 个由小写字母组成的字符串，定义第 \(i\) 个字符串的价值为其有意义的子串的数量（如果有多个本质相同的子串也统计多次），第 \(i\) 个字符串的一个子串有意义，当且仅当这个子串能被分成若干个串，其中每个串都是这 \(n\) 个字符串中任意一个字符串的任意一个后缀。 这里有一个 \(n=4\) 的例子： int printf scanf ntnt 对于 printf 这个字符串而言，intf 是有意义的，因为可以表示成 int 和 f ，分别是 int 和 scanf 的后缀，而 rint 则不是。 对于 ntnt 这个字符串而言，ntnt 也是有意义的，因为可以表示成 nt 和 nt，它们都是 int 同一个后缀，或者可以表示成 ntnt，是 ntnt 的一个后缀。 现在，小 Z 想知道这 \(n\) 个字符串价值之和。 输入格式： 第一行一个整数 \(n\)。 之后 \(n\) 行，每行一个字符串。 输出格式： 一行一个整数，表示价值之和。 数据范围：...

note[13] 刷帖子看到个迷惑操作，差点上套了 我猜他应该是想表达 \(\prod_{p_i \le x} p_i + 1(p_i\in\mathbb{P})\) 可以构成素数？ 差点被搞了。我们知道有一个著名的证明，即证明素数是无限多的，它是这么证明的 反证法：设素数有 \(n\) 个，那么 \(x = \prod_{i=1}^{n} p_i + 1\) 无法被任何一个 \(p_i\) 整除，因此素数是无限多的。 注意加粗的部分，这只是证明了素数是无限多的，没有说明 \(x\) 是素数啊！ 讨论区有个巨佬发的 可以发现， \(x\) 不能被小于等于 \(p_n\) 的素数整除，但是它为什么不可能被比 \(p_n\) 大的素数整除呢？ 注：这里 \(-1\) 是因为一开始那位小朋友以为自己记错了 \(+1\) 或 \(-1\) ，其实是一样的。 可恶，迷惑性还蛮大的，特别对于是我这种没怎么仔细想过的人。

洛谷P9753 [CSP-S 2023] 消消乐 题解 题目链接：P9753 [CSP-S 2023] 消消乐 题意： 小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。 现在，他有一个长度为 \(n\) 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。 其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。 小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。 输入格式： 输入的第一行包含一个正整数 \(n\)，表示字符串的长度。 输入的第二行包含一个长度为 \(n\) 且仅由小写字母构成的的字符串，表示题目中询问的字符串。 输出格式： 输出一行包含一个整数，表示题目询问的答案。 数据范围： \(1 \leq n \leq 2 \times 10^6\) ，且询问的字符串仅由小写字母构成 解法一： 这个解法适合从 dp 角度出发的思考的同学（比如我）。 容易发现，若 \(s[i\,..k-1]\) 合法，且 \(s[k\,....

洛谷P9088 「SvR-2」1+2=3 题解 题目链接：P9088 「SvR-2」1+2=3 题意： 你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 \(0,1,2\)，你要将所有木棒拼起来，使相邻的数和为 \(3\) 的对数最大。 例如，\(1\text{ - }2\) 和 \(1\text{ - }0\) 两个木棒，如果按 \(1\text{ - }0,1\text{ - }2\) 这样拼，相邻的数和为 \(3\) 的对数是 \(0\)；而按 \(1\text{ - }{\textbf2},{\textbf1}\text{ - }0\) 这样拼相邻的数和为 \(3\) 的对数是 \(1\)，因为 \(2+1=3\)。 输入格式： 本题有多组数据。 输入的第一行一个正整数表示数据组数 \(T\)。 对于每组数据，一行 \(9\) 个非负整数，分别表示 \(0\text{ - }0,0\text{ - }1,0\text{ - }2,1\text{ - }0,1\text{ - }1,1\text{ - }2,2\text{ - }0,2\text{ - }1,2\...

CF710F String Set Queries 题解 题目链接：CF710F String Set Queries 题意： 维护一个字符串集合，支持三种操作： 加字符串 删字符串 查询集合中的所有字符串在给出的模板串中出现的次数 操作数 \(m \leq 3 \times 10^5\)，输入字符串总长度 \(\sum |s_i| \leq 3\times 10^5\)。 本题强制在线，应该在每次输出后调用fflush(stdout)。 你只有在输出上一个询问的答案后才能读入下一组询问。 过了好几天了才开始写题解，着实有些懒。（最近两只手都腱鞘炎了） 这道题就是 二进制分组 + AC 自动机 ，下面我们来分析这个想法是怎么来的。 先考虑暴力，我们每次删除的时候都对原字符串进行重构，显然这是一种低效的方式。 这个其实很好解决。由于贡献是可以加减的，所以我们考虑把删除操作改为在另一个 Trie 上面插字符串 我们称原先的 Trie 是 Add 树，另外的是 Sub 树，那么答案就是 Add 树的贡献减 Sub 树的贡献。 思考一下这样的时间复杂度是多少：最坏情况下，字符长...

SP19568 PRMQUER - Prime queries 题解 题目链接：SP19568 PRMQUER - Prime queries 题意： 这是一个简单的题目 给定 \(N\) 个数，你需要对它们依次进行 \(Q\) 次操作。每次操作的格式如下。 三个整数 \(A\) \(V\) \(l\) 表示给第 \(l\) 个数加上 \(V\) 。 四个整数 \(R\) \(a\) \(l\) \(r\) 表示把区间 \([l,r]\) 的数都变为 \(a\) 。 三个整数 \(Q\) \(l\) \(r\) 表示询问区间 \([l,r]\) 里，小于等于 \(10^7\) 的素数有多少个。 数据保证任何时刻这 \(N\) 个数都不会有一个数大于 \(10^9\) 。 输入格式： 第一行两个整数 \(N\) 和 \(Q\) 分别表示数的个数和操作的个数，第二行有 \(N\) 个整数，表示这些数的初始大小。之后 \(Q\) 行每行一次操作，输入格式如题目描述所述。 输出格式： 对于每个操作 \(3\) 输出一行整数表示这个操作的答案。 数据范围： \(1\leq N\leq...

CF1359E Modular Stability 题解 题目链接：CF1359E Modular Stability 题意： 求有多少个长度为 \(k\) 的序列 \(a\)，满足以下条件： \(\forall 1 \le i < k,a_i < a_{i+1}\) \(\forall 1 \le i \le k,1 \le a_i \le n\) 对于任意一个 \(1\) 至 \(k\) 的排列 \(p\)，满足 \[ \begin{aligned} &( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) \\[6pt]= &((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3} )\bmod \cdots \bmod a_{p_k}) \end{aligned} \] 其中 \(x\) 为任意非负整数。 结果对 \(998244353\) 取模。 输入格式： 输入一行两个整数 \(n,k\)，意义如题目描述所示。 输出格式： 输出一个...

CF605E Intergalaxy Trips 题解 题目链接：CF605E Intergalaxy Trips 题意： 给定 \(n\) 个点的有向完全图。 \(i \to j\) 的边每天出现的概率均为 \(p_{i,j}\)，若 \(i = j\)，有 \(p_{i,j} = 1\)。 每天可以选择一条存在的出边走过去或停留在原地不动。 求最优策略下从 \(1\) 到 \(n\) 的期望天数，\(n \le 10^3\)。 完整题意： 最近，科学家们发现了虫洞 —— 宇宙中的一种物体，可以让你在星系和恒星系统之间旅行很长的距离。 科学家们知道有 \(n\) 个星系可以到达。你位于星系编号 \(1\)，你需要到达星系编号 \(n\)。从星系 \(i\) 到星系 \(j\)，你需要乘坐虫洞 \((i,j)\)，并在恰好一个星系日内，你将出现在星系 \(j\)。 不幸的是，所需的虫洞并不总是可用的。每个星系日它们会随机消失和出现。然而，虫洞的状态在一个星系日内不会改变。从星系 \(i\) 到星系 \(j\) 的虫洞每天分别存在的概率为 \(p_{ij}\)。你可以随时了解当前...

CF1334E Divisor Paths 题解 题目链接：CF1334E Divisor Paths 题意： 给出正整数 \(D\) 和一张图 \(G\) ，满足： \(G\) 中每个节点都与 \(D\) 的因子一一对应 存在无向边 \((x, y)\) 当且仅当 \(y\) 整除 \(x\) 且 \(\frac{x}{y}\) 是质数 边 \((x, y)\) 的长度为 \(d_x-d_y\) ，其中 \(d_k\) 代表正整数 \(k\) 的 因子个数 共 \(q\) 次询问，每次给出 \(D\) 的因子 \(u\) 和 \(v\)，求 \(G\) 中节点 \(u, v\) 之间的最短路条数 输入格式： 第一行包含一个正整数 \(D\) （ \(1 \le D \le 10^{15}\) ）— 构建图的数。 第二行包含一个正整数 \(q\) （ \(1 \le q \le 3 \times 10^5\) ）— 查询数量。 接下来的每行，每行包含两个整数 \(v\) 和 \(u\) （ \(1 \le v, u \le D\) ）。保证 \(D\) 能同时被 \(v\)...

模拟赛题讲解[34] 来自 yukuai26 2023-08-06 noi.ac #3281 题目描述： 给你一个长度为 \(n\) 的序列，以及一个数字 \(k\)。 每次你可以选择一对 \((i,j)\)，使得 \(a_i\) 加一，\(a_j\) 减一。 问最少经过多少次操作，使得数列中任意两个数的差不超过 \(k\)。数据保证有解。 输入格式： 第一行两个整数 \(n,k\) 第二行 \(n\) 个整数，表示 \(a_i\) 输出格式： 输出最小的答案 输入样例： 4 3 1 5 1 10 输出样例： 4 数据范围： 保证 \(1 \leq n \leq 100000,1 \leq K \leq 100000,1 \leq a_i \leq 100000\)，且在该范围内等概率随机生成。 题解： 显然我们每次修改的两个数分别为最大值和最小值。 并且每次修改一定会把最小值和最大值中出现次数最少的那个给灭掉。 那么就模拟一下这个过程就好了。 时间复杂度 \(\mathcal{O}(n+\max\{a_i\})\) 代码： #include <bits/stdc++.h>...