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




![洛谷P3856 [TJOI2008] 公共子串 题解](/qwq/img/p212.webp)

![洛谷P9871 [NOIP2023] 天天爱打卡 题解](/qwq/img/p9.webp)

![洛谷P3181 [HAOI2016] 找相同字符 题解](/qwq/img/p96.webp)
![洛谷P4051 [JSOI2007] 字符加密 题解](/qwq/img/p208.webp)
![洛谷P2870 [USACO07DEC] Best Cow Line G 题解](/qwq/img/p140.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)