Q779’s Blog

洛谷P3856 [TJOI2008] 公共子串 题解 题目链接：P3856 [TJOI2008] 公共子串 题意： 题目虽然叫公共子串，但实际上求的是公共子序列。 给定三个只有小写字母的字符串，求他们不同的公共子序列的个数（不含空串）。 两个子序列不同当且仅当这两个子序列中有字符不相同。 输入格式： 三行，字符串。 输出格式： 一行，答案。 数据范围： 字符串长度 \(\le 100\) 。 才知道这个东西叫子序列自动机，就下面这个 for(int i = len - 1; ~i; i--) { for(int j = 0; j < 26; j++) ch[i][j] = ch[i + 1][j]; ch[i][s[i + 1] - 'a'] = i + 1; } 这个东西维护了每个位置的下一个 \(c\) 字符在哪里。 那就很简单了，设 \(f(i,j,k)\) 为仅考虑「 \(i\) 到 \(|A|\) 、\(j\) 到 \(|B|\) 、\(k\) 到 \(|C|\) 」的公共子序列。 这样从 \(f(0,0,0)\) 开始搜，...

AT_dp_w Intervals 题解 题目链接：AT_dp_w Intervals 题意： 给定 \(m\) 条规则形如 \((l_i,r_i,a_i)\)，对于一个 01 串，其分数的定义是： 对于第 \(i\) 条规则，若该串在 \([l_i,r_i]\) 中至少有一个 \(1\)，则该串的分数增加 \(a_i\)。 你需要求出长度为 \(n\) 的 01 串中的最大分数。 输入格式： 第一行 \(n,m\) ，接下来 \(m\) 行 \(l_i,r_i,a_i\) 。 输出格式： 输出字符串的最大得分。 数据范围： \(1 \le n,m \le 2\times 10^5\) 且 \(1\le l_i \le r_i\le n,~|a_i|\le 10^9\) 这道题和 P9871 [NOIP2023] 天天爱打卡 思路挺像的。 设 \(f(i,j)\) 为前 \(i\) 个位置中，上一个 \(1\) 放在 \(j\) 的最优方案，则 \[ f(i,0) = 0,\ f(i,i) = \max_{0 \le j < i} f(i-1,j) \\[6pt] f(...

洛谷P9871 [NOIP2023] 天天爱打卡 题解 题目链接：P9871 [NOIP2023] 天天爱打卡 题意： 小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。 开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 \(n\) 天，编号为从 \(1\) 到 \(n\)。 对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 \(d\)。初始时，他的能量值是 \(0\)，并且试运行期间他的能量值可以是负数。 而且大 Y 不会连续跑步打卡超过 \(k\) 天；即不能存在 \(1\le x\le n-k\)，使得他在第 \(x\) 到第 \(x+k\) 天均进行了跑步打卡。 小 T 同学在软件中设计了 \(m\) 个挑战，第 \(i\)（\(1\le i \le m\)）个挑战可以用三个正整数 \((x_i,y_i,v_i)\) 描述，表示如果在第 \(x_i\) 天时，用户已经连续跑步打卡至少 \(y_i\) 天（即第 \(x_i-y_i+1\) 到第 \(x_i\) ...

SP10570 LONGCS - Longest Common Substring 题解 题目链接：LONGCS - Longest Common Substring 题意： 子串是字符串的连续部分。一个通常用动态规划解决的问题是找到最长公共子串问题，即找到两个字符串的最长子串（或多个最长子串）。你的任务是找到 \(K\) 个字符串的最长公共子串的长度。 输入格式： 第一行包含一个整数 \(T\)，表示测试用例的数量 \((1 \le T \le 20)\) 。 每个测试用例包含一行，包含一个整数 \(K(1 \le K \le 10)\) 以及接下来的 \(K\) 行，每行包含一个字符串（字符串长度 \(\le 10^4\)），这些字符串只包含字符 a 到 z。 输出格式： 输出 \(T\) 行，每行对应一个测试用例，包含所需的序列，每个连续的项之间用一个空格分隔。 保证序列中的所有项都是整数。 这道题的思路和 洛谷P3181 [HAOI2016] 找相同字符 很相似。 考虑将所有的串用特殊字符拼接成一个串，然后构建后缀数组。 于是问题转化为：找到 \(K\) 个后缀（且没...

洛谷P3181 [HAOI2016] 找相同字符 题解 题目链接：P3181 [HAOI2016] 找相同字符 题意： 给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 两个方案不同当且仅当这两个子串中有一个位置不同。 输入格式： 两行，两个字符串 \(S,T\)，长度分别为 \(n,m\)。 输出格式： 输出一个整数表示答案。 数据范围： \(1\le n,m\le 2\times 10^5\)，字符串中只有小写字母。 建议先去看一下 洛谷P4248 [AHOI2013] 差异 题解 主要是要知道下面这个东西以及怎么算。 \[ \begin{aligned} \sum_{1 \leq i<j \leq n} \operatorname{lcp}\left(\mathrm{Suf}(i), \mathrm{Suf}(j)\right) &=\sum_{1 \leq i<j \leq n} \operatorname{LCP}\left(i,j\right) \\[6pt]&= \sum_{1 \leq i<j \l...

洛谷P4248 [AHOI2013] 差异 题解 题目链接：P4248 [AHOI2013] 差异 题意： 给定一个长度为 \(n\) 的字符串 \(S\)，令 \(T_i\) 表示它从第 \(i\) 个字符开始的后缀。求 \[ \displaystyle \sum_{1\le i<j\le n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j) \] 其中，\(\text{len}(a)\) 表示字符串 \(a\) 的长度，\(\text{lcp}(a,b)\) 表示字符串 \(a\) 和字符串 \(b\) 的最长公共前缀。 输入格式： 一行，一个字符串 \(S\)。 输出格式： 一行，一个整数，表示所求值。 数据范围： 对于 \(100\%\) 的数据，保证 \(2\le n\le 5\times 10^5\)，且 \(S\) 中均为小写字母。 \(\mathcal{Part}\ 1\) 首先化简式子 \[ \begin{aligned} \mathrm...

洛谷P4051 [JSOI2007] 字符加密 题解 题目链接：P4051 [JSOI2007] 字符加密 题意： 喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。 例如 JSOI07，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？ 输入格式： 输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。 输出格式： 输出一行，为加密后的字符串。 数据范围： 数据字符串的长度不超过 \(10^5\)。 先把原题的字符串复制一遍加到后面，然后跑一遍后缀排序 依次考虑每个后缀，如果它的编号小于等于 \(n\) ，那这个串就是合法的，取 s[sa[i] + n - 1] 即...

洛谷P2870 [USACO07DEC] Best Cow Line G 题解 题目链接：P2870 [USACO07DEC] Best Cow Line G 题意： Farmer John 打算带领 \(N\)（\(1 \leq N \leq 5 \times 10^5\)）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。 今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。 FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。 他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。 现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。 输入格式： 第一行一个整数 \(N\)。 接下来 \(N\) 行每行一个大写字母，表示初始队列。 输出格式： 输出一个长度为 \(N\) 的字符串，表示可能的最小字...

异或版哥德巴赫猜想 来源于洛谷讨论区 异或版哥德巴赫猜想 猜想：任何一个正偶数可以表示为两个质数的异或。 下面讲讲我的思路吧，不知道对不对。 波利尼亚克猜想 (Polignac’s conjecture)：对于任意偶数 \(2k\) ，存在无穷多组以 \(2k\) 为间隔的素数。 假设波利尼亚克猜想成立，只需要构造一组素数对 \((p, p+2k)\) ，其中 \(\mathrm{lowbit}(p) > 2k\) 即可。 这里 \(\mathrm{lowbit}(p)\) 定义为 \(p\) 二进制下最低的那一位对应的十进制数，比如 \(\mathrm{lowbit}(5)=2^1\) 。 说实话我不知道这个猜想和哥德巴赫猜想有没有关系，但是波利尼亚克猜想好像确实可以推出来。

洛谷P4762 [CERC2014] Virus synthesis 题解 题目链接：P4762 [CERC2014] Virus synthesis 题意： 病毒通常对您的健康有害。那么用……其他病毒来对抗它们怎么样呢？在这个问题中，您需要找出如何合成这种好的病毒。 我们为您准备了一组由字母 \(\texttt{A}, \texttt{G}, \texttt{T}\) 和 \(\texttt{C}\) 组成的字符串。它们对应于我们想要合成的病毒的 DNA 核苷酸序列，使用以下操作： 在现有序列的开头或末尾添加一个核苷酸。 复制序列，反转复制的片段，并将其粘贴到原始序列的开头或末尾（例如，\(\tt AGTC\) 可以变成 \(\tt AGTCCTGA\) 或 \(\tt CTGAAGTC\)）。 我们关心的是效率，因为我们有很多这样的序列，其中一些非常长。找出一种方法，以最少的操作次数合成它们。 输入格式： 输入的第一行包含测试用例的数量 \(T\)。接下来的每一行描述一个测试用例： 每个测试用例由一行非空字符串组成。字符串仅使用大写字母 \(\texttt{A}, \t...

韦达跳跃法 Vieta jumping 来源于1988年IMO第6题   设 \(a,b\) 满足 \(ab+1 \mid a^2 + b^2\) ，求证 \(\frac{a^2+b^2}{ab+1}\) 是完全平方数。 被称为韦达跳跃法 (Vieta jumping) 的解法由当时的保加利亚选手 Emanouil Atanassov 给出 韦达跳跃法利用韦达定理 (Vieta’s formulas) 和无穷递降法 (Proof by infinite descent) 证明原命题。 本题解法如下： 考虑反证法。设 \(\frac{a^2+b^2}{ab+1}=k \in\mathbb{N}\) 且 \(k\) 不为完全平方数。 令 \((A,B)\) 为上述方程的一组解，并且满足 \(A+B\) 的值最小，规定 \(A \ge B\) 。 将 \(A,B\) 代入方程，得到 \(A^2 + B^2 = k(AB+1)\) ，则 \[ A^2-(k B) A+B^2-k=0 \] 记 \(A,A_1\) 为以下方程的两个根 \[ x^2 - (kB)x - B^2-k=0 \]...

U+200B 零宽空格 首先放两段文本 测试文本​ 和 测试文本 看出区别了吗？看得出来就离谱了。 零宽空格（英语：zero-width space, ZWSP）是一种不可打印的Unicode字符，用于可能需要换行处。 这个字符在大多数情况下都是不显示的，除了在某些软件中，比如 QQ 。 实际上在 VSCode 里打开一个 cpp 文件，输入这个字符，它会帮你标出来然后报错。 补充： 零宽空格属于零宽度字符（非打印字符）的一种 这种字符的出现是为了文字控制排版作用的，但是由于它拥有肉眼无法观察到的特性， 零宽度字符可作为识别某些用户身份的”指纹”数据，也可非常方便地追溯到某些秘密数据的泄露源。 零宽度字符能做什么？ 数据防爬，将零宽度字符插入文本中，干扰关键字匹配。爬虫得到的带有零宽度字符的数据会影响他们的分析，但不会影响用户的阅读数据。 信息传递，将自定义组合的零宽度字符插入文本中，用户复制后会携带不可见信息，达到传递作用。 传递隐密信息，利用零宽度字符不可见的特性，我们可以用零宽度字符在任何未对零宽度字符做过滤的网页内插入不可见的隐形文本。 隐形水印，通过零宽度字符我...