Q779’s Blog

洛谷P3295 [SCOI2016] 萌萌哒 题解 题目链接：P3295 [SCOI2016] 萌萌哒 题意： 一个长度为 \(n\) 的大数，用 \(S_1S_2S_3 \cdots S_n\)表示，其中 \(S_i\) 表示数的第 \(i\) 位， \(S_1\) 是数的最高位。 告诉你一些限制条件，每个条件表示为四个数 \(l_1,r_1,l_2,r_2\) ，即两个长度相同的区间，表示子串 \(S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}\) 与 \(S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}\) 完全相同。 比如 \(n=6\) 时，某限制条件 \(l_1=1,r_1=3,l_2=4,r_2=6\) ，那么 \(123123\)，\(351351\) 均满足条件，但是 \(12012\)，\(131141\) 不满足条件，前者数的长度不为 \(6\) ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。 输入格式： 第一行两个数 \(n\) 和 \(m\)，分别表示大数的长度，以及限制条件...

洛谷P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题解 题目链接：P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题意： 大中锋有一个长度为 \(n\) 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。 但是由于字符串很长，大中锋很难将这些子串一一尝试。 这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。 在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 \(k\) 次的子串”。 但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 \(k\) 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。 大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。 输入格式： 第一行一个正整数 \(T\) ，表示有 \(T\) 组测试数据。 接下来 \(T\) 行每行包含一个字符串和一个正整数 \(k\) 。 输出格式： 一共输出 \(T\) 行，每行一个整数表示在出现 \(k\) 次的子串中出现次数的最多的长度。 如果不存在子串...

洛谷P3975 [TJOI2015] 弦论 题解 题目链接：P3975 [TJOI2015] 弦论 题意： 为了提高智商，cxy 开始学习弦论。 这一天，她在《String theory》中看到了这样一道问题： 对于一个给定的长度为 \(n\) 的字符串，求出它的第 \(k\) 小子串是什么。你能帮帮她吗? 输入格式: 第一行是一个仅由小写英文字母构成的字符串 \(s\)。 第二行为两个整数 \(t\) 和 \(k\) ， \(t\) 为 \(0\) 则表示不同位置的相同子串算作一个。 \(t\) 为 \(1\) 则表示不同位置的相同子串算作多个。 \(k\) 的意义见题目描述。 输出格式： 输出数据仅有一行，该行有一个字符串，为第 \(k\) 小的子串。若子串数目不足 \(k\) 个，则输出 \(-1\)。 数据范围： \(1\leq n \leq 5 \times 10^5,~0\leq t \leq 1,~1\leq k \leq 10^9\)。 \(\mathcal{Part}\ 0\) 看题解区全是 SAM 的解法，少有的 SA 解法也都是 \(\mathcal...

洛谷P5854 【模板】笛卡尔树 题解 题目链接：P5854 【模板】笛卡尔树 题意： 给定一个 \(1 \sim n\) 的排列 \(p\)，构建其笛卡尔树。 即构建一棵二叉树，满足： 每个节点的编号满足二叉搜索树的性质。 节点 \(i\) 的权值为 \(p_i\)，每个节点的权值满足小根堆的性质。 输入格式： 第一行一个整数 \(n\)。 第二行一个排列 \(p_{1 \dots n}\)。 输出格式： 设 \(l_i,r_i\) 分别表示节点 \(i\) 的左右儿子的编号（若不存在则为 \(0\)）。 一行两个整数，分别表示 \(\operatorname{xor}_{i = 1}^n i \times (l_i + 1)\) 和 \(\operatorname{xor}_{i = 1}^n i \times (r_i + 1)\)。 数据范围： 对于 \(100\%\) 的数据，\(1 \le n \le 10^7\)。 笛卡尔树的构建非常简单，我们只需要维护一个单调栈即可。 虽然很简单，但是笛卡尔树在一些题目中还是很有用的，原因就在于它可以线性构建。 时间复杂度...

[ARC101E] Ribbons on Tree 题解 题目链接：[ARC101E] Ribbons on Tree 题意： 给定一个大小为 \(n(2\le N\le 5000)\) 的树，保证 \(n\) 为偶数。 您需要给树上的点两两配对，对于一组点对 \((u,v)\)，在树上将 \(u\leadsto v\) 的路径染色。 定义一个配对方案合法当且仅当所有边都有颜色，求方案数对 \(10^9+7\) 取模。 输入：第一行 \(n\) ，接下来 \(n-1\) 行 \(u,v\) 表示无向边 \(u,v\) 。输出：一行答案。 先考虑一个 \(\mathcal{O}(n^3)\) 的 dp。 设 \(f(u,i)\) 为 \(u\) 子树中有 \(i\) 个点要向上匹配的方案数。 那么这就是一个树上背包，转移考虑枚举 \(u\) 子树内的点数 \(i\) ， \(v\) 子树内的点数 \(j\) 和匹配的对数 \(k\) \[ f_{\rm now}(u,i + j-2k) = \sum_{1\le k \le j \le \min\{\operatorname{...

洛谷P3225 [HNOI2012] 矿场搭建 题解 题目链接：P3225 [HNOI2012] 矿场搭建 题意： 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。 请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 输入格式： 输入文件有若干组数据。 每组数据的第一行是一个正整数 \(N\ (N \le 500)\)，表示工地的隧道数。 接下来的 \(N\) 行每行是用空格隔开的两个整数 \(S\) 和 \(T\)，表示挖煤点 \(S\) 与挖煤点 \(T\) 由隧道直接连接。 输入数据以 \(0\) 结尾。 输出格式： 对于每组数据，输出一行。 第 \(i\) 行组数据以 \(\verb!Case i: !\) 开始（注意大小写，\(\verb!Case!\) 与 \(\verb!i!\) 之间有空格，\(\verb!i!\) 与 \(\verb!:!\)...

[ABC343G] Compress Strings 题解 题目链接：[ABC343G] Compress Strings 题意： 给你 \(N\) 个由小写字母组成的字符串 \(S_1, S_2, \ldots, S_N\) 。 找出一个母串使得它包含所有这些字符串作为它的子串，最小化该母串的长度并输出。 数据范围：\(1 \leq N \leq 20,~\sum |S_i| \leq 2 \times 10 ^ 5\) 。 考虑状压dp。首先记 \(a_{i,j}\) 为 \(i,j\) 的最长公共子串的长度，这个可以用 kmp 跑出来。 设 \(f(i,S)\) 为当前选了 \(S\) 的字符串，最后一个选的字符串是 \(i\) 时的最小值。 这里要求 \(S\) 中的字符串不存在相互包含的情况，也可以用 kmp 跑出来。 那么 \[ f(j, S \cup \{j\}) \,\operatorname{\big\downarrow}\, f(i,S) + \operatorname{len} i - a_{i,j} \] 上式 \(\downarrow\) 表示取 m...

洛谷P2322 [HNOI2006] 最短母串问题 题解 题目链接：P2322 [HNOI2006] 最短母串问题 题意： 给定 \(n\) 个字符串 \((S_1,S_2,...,S_n)\) ， 要求找到一个最短的字符串 \(T\)，使得这 \(n\) 个字符串 \((S_1,S_2,...,S_n)\) 都是 \(T\) 的子串。 输入格式： 输入文件第一行是一个整数 \(n\)，表示给定的字符串个数。 接下来 \(n\) 行，每行有一个全由大写字母组成的字符串。 输出格式： 输出文件只有一行，为找到的最短的字符串 \(T\)。 在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。 数据范围： 对于 \(100\%\) 的数据，\(n \leq 12\)，每个字符串的长度不超过 \(50\)。 由于本题要求输出字典序最小的方案，所以这题状压dp会比较麻烦。 注意到超级小的数据范围，考虑暴力出奇迹，即 bfs 所有可能的情况。 检验的话，考虑将题目给的串建一个 AC 自动机，然后预处理出每个节点包含了那些串。 由于一般的写法都是建字典图，所以...

洛谷P2617 Dynamic Rankings 题解 题目链接：P2617 Dynamic Rankings 题意： 给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作： Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数。 C x y 表示将 \(a_x\) 改为 \(y\) 。 输入格式： 第一行两个正整数 \(n,m\)，表示序列长度与操作个数。 第二行 \(n\) 个整数，表示 \(a_1,a_2 \dots a_n\)。 接下来 \(m\) 行，每行表示一个操作，都为上述两种中的一个。 输出格式： 对于每一次询问，输出一行一个整数表示答案。 数据范围： \(1\le n,m \le 10^5\)，\(1 \le l \le r \le n\)，\(1 \le k \le r-l+1\)，\(1\le x \le n\)，\(0 \le a_i,y \le 10^9\)。 请注意常数优化，但写法正常的整体二分和树套树都可以以大约 \(1000\text{ms}\) 每个点的时间通过。 ...

洛谷P2487 [SDOI2011] 拦截导弹 题解 题目链接：P2487 [SDOI2011] 拦截导弹 题意： 注意本题不是 P1020 [NOIP1999 提高组] 导弹拦截 ，本题有额外的速度限制（更科学了）。 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。 我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。 输入格式： 第一行包含一个正整数 \(n\)，表示敌军导弹数量。 下面 \(n\) 行按顺序给出了敌军所有导弹信息。 第 \...

洛谷P1117 [NOI2016] 优秀的拆分 题解 题目链接：P1117 [NOI2016] 优秀的拆分 题意： 如果一个字符串可以被拆分为 \(\text{AABB}\) 的形式，其中 \(\text{A}\) 和 \(\text{B}\) 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。 例如，对于字符串 \(\texttt{aabaabaa}\) ，如果令 \(\text{A}=\texttt{aab}\)，\(\text{B}=\texttt{a}\)，我们就找到了这个字符串拆分成 \(\text{AABB}\) 的一种方式。 一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。 比如我们令 \(\text{A}=\texttt{a}\)，\(\text{B}=\texttt{baa}\)，也可以用 \(\text{AABB}\) 表示出上述字符串；但是，字符串 \(\texttt{abaabaa}\) 就没有优秀的拆分。 现在给出一个长度为 \(n\) 的字符串 \(S\)，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字...

洛谷P4016 负载平衡问题 题解 题目链接：P4016 负载平衡问题 题意： \(G\) 公司有 \(n\) 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 \(n\) 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式： 第一行一个正整数 \(n\)，表示有 \(n\) 个仓库。 第二行 \(n\) 个正整数，表示 \(n\) 个仓库的库存量。 输出格式： 输出最少搬运量。 数据范围： \(1 \leq n \leq 100\)。 贪心题写什么网络流。原题：P2512 糖果传递 或者 P2125 图书馆书架上的书。 网上证明很多不写了，可以去看 mygr 巨佬写的文章 贴个 P2125 的代码：（这题要输出传递方案） #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x, int y) { x < y ? x = y ...