Q779’s Blog

洛谷P3966 [TJOI2013]单词 题解 题目链接：P3966 [TJOI2013]单词 题意： 小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。 \(1 \leq n \leq 200\)，单词总长度不超过 \(10^6\)。 瞎搞做法能跑到最优解前3页也是有趣 这个文章看样例应该是单词间有空格的 于是我们就把所有单词全部加上去，用#分隔 然后就变成 P5357 AC自动机二次加强版 了 具体的就是把暴力跳fail数组改成topo排序更新 时间复杂度 \(O(26 \times \sum s_i)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <...

洛谷P4407 [JSOI2009] 电子字典 题解 题目链接：P4407 [JSOI2009] 电子字典 题意：人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选择。 字符串a与字符串 \(b\) 的编辑距离是指：允许对 \(a\) 或 \(b\) 串进行下列“编辑”操作，将 \(a\) 变为 \(b\) 或 \(b\) 变为 \(a\) ，最少“编辑”次数即为距离。 删除串中某个位置的字母； 添加一个字母到串中某个位置； 替换串中某一位置的一个字母为另一个字母； 给定 \(n\) 个不同的单词，\(m\) 次询问，对于一个待查询字符串，如果它是单词，则返回 \(-1\)；如果它不是单词，则返回字典中有多少个单词与它的编辑距离为 \(1\) 。 \(n,m \le 10,000\) ，每个单词长度 \(\le 20\) ，每个待查询字符串长...

洛谷P2922 [USACO08DEC]Secret Message G 题解 题目链接：P2922 [USACO08DEC]Secret Message G 题意： 一句话题意：\(m\) 次询问，查询已有的 \(n\) 个 \(\tt{01}\) 串中，有多少串 \(t_i\) 能使询问串 \(s\) 成为其前缀。 贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息． 信息是二进制的，共有 \(M\)（\(1 \le M \le 50000\)）条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 \(i\) 条二进制信息的前 \(b_i\)（\(l \le b_i \le 10000\)）位，他同时知道，奶牛使用 \(N\)（\(1 \le N \le 50000\)）条暗号．但是，他仅仅知道第 \(j\) 条暗号的前 \(c_j\)（\(1 \le c_j \le 10000\)）位。 对于每条暗号 \(j\)，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。 在输入文件...

洛谷P3586 [POI2015] LOG 题解 题目链接：P3586 [POI2015] LOG 题意： 维护一个长度为 \(n\) 的序列，一开始都是 \(0\)，支持以下两种操作： U k a 将序列中第 \(k\) 个数修改为 \(a\)。 Z c s 在这个序列上，每次选出 \(c\) 个正数，并将它们都减去 \(1\)，询问能否进行 \(s\) 次操作。 每次询问独立，即每次询问不会对序列进行修改。 【数据范围】 对于 \(100\%\) 的数据，\(1\leq n,m\leq 10^6\)，\(1\leq k,c\leq n\)，\(0\leq a\leq 10^9\)，\(1\leq s\leq 10^9\)。 不是区间询问。注意了嗷。 先考虑2操作 对于大于 \(s\) 的数，显然最多只能减 \(s\) 次 对于小于等于 \(s\) 的数，肯定要把它全部减成 \(0\) 设 \(S=\sum x_i [x_i\le s]\) ，则剩下的 \(c\times s - S\) 由大于 \(s\) 的数贡献 设 \(\text{cnt} = \sum [x_i...

洛谷P3879 [TJOI2010] 阅读理解 题解 题目链接：P3879 [TJOI2010] 阅读理解 题意： 英语老师留了 \(N\) 篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。 第一行为整数 \(N\) ，表示短文篇数，其中每篇短文只含空格和小写字母。 按下来的 \(N\) 行，每行描述一篇短文。每行的开头是一个整数 \(L\) ，表示这篇短文由 \(L\) 个单词组成。接下来是 \(L\) 个单词，单词之间用一个空格分隔。 然后为一个整数 \(M\) ，表示要做几次询问。后面有 \(M\) 行，每行表示一个要统计的生词。 对于 \(100\%\) 的数据，\(1\le M\le 10^4\)，\(1\le N\le 10^3\) 。 每篇短文长度（含相邻单词之间的空格）\(\le 5\times 10^3\) 字符，每个单词长度 \(\le 20\) 字符。 要写 \(\tt{trie}\) 也不是不行。但是懒。 直接用 \(\tt{unordered\_map+vector}\) 水...

洛谷P1168 中位数 题解 题目链接：P1168 中位数 题意： 给出一个长度为\(N\)的非负整数序列\(A_i\)，对于所有\(1 ≤ k ≤ (N + 1) / 2\)，输出\(A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}\)的中位数。即前\(1,3,5,…\)个数的中位数。 数据范围： 对于\(100\%\)的数据，\(N ≤ 100000\)。 当然可以用vector来搞啦，但是这样就常数大而且没劲了 考虑对顶堆（那篇讲对顶堆的是在绕口令吧。明明很好懂的） 维护两个堆，分别是大根堆和小根堆 有个性质：大根堆q1里的所有值小于小根堆q2里的所有值 然后每次把比q1堆首元素大的元素扔到q2里去，反之塞进q1里 这样还是满足性质的 但是我们要中位数，这就需要q1和q2的size只相差一，才好处理 怎么搞呢，比如q1的size太大了，那我们就把q1的堆首一个个扔到q2里去 这样仍然是满足性质的 注意到每个元素最多入堆2次，因此单次插入操作是 \(O(\log n)\) 的 时间复杂度 \(O(n\log n)\) 代码： #includ...

洛谷P3958 [NOIP2017 提高组] 奶酪 题解 题目链接：P3958 [NOIP2017 提高组] 奶酪 题意： 现有一块大奶酪，它的高度为 \(h\)，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 \(z = 0\)，奶酪的上表面为 \(z = h\)。 现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。 位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑 到奶酪的上表面去? 空间内两点 \(P_1(x_1,y_1,z_1)\)、\(P_2(x_2,y_2,z_2)\) 的距离公式如下： \[ \mathrm{dist}(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_...

洛谷P1816 忠诚 题解 题目链接：P1816 忠诚 题意：区间min。 BIT写法也就图一乐（其实不建议） 主要在询问上有些区别， 例如如果 x-lowbit(x) 小于 \(l\) ，则此时不能直接 x-=lowbit(x) 因为这样会把 \([l,r]\) 之外的东西给弄进来，所以这部分直接暴力处理 复杂度不清楚，应该还是 \(O(\log n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e6...

洛谷P4185 [USACO18JAN]MooTube G 题解 题目链接：P4185 [USACO18JAN]MooTube G 题意： 给出一棵无根树， \(m \le 10^5\) 次询问，给出 \(k,v\) ，询问共有多少结点 \(u\) 满足 \(u\) 到 \(v\) 的路径上最小边权不小于 \(k\) 。 考虑把所有相互满足条件的结点用并查集合并 注意到当 \(k\) 减小时，合并后的连通块数量单调递减 考虑将询问按 \(k\) 降序排序，离线处理 每次去找没合并过的边显然太麻烦 继续利用单调性，将所有边按边权降序排序 这样我们扫一遍就能处理所有询问了 复杂度瓶颈在于排序。 时间复杂度 \(O(m \log m)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cma...

洛谷P2085 最小函数值 题解 题目链接：P2085 最小函数值 题意： 有 \(n\) 个函数，分别为 \(F_1,F_2,\dots,F_n\)。定义 \(F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N^*)\)。给定这些 \(A_i\)、\(B_i\) 和 \(C_i\)，请求出所有函数的所有函数值中最小的 \(m\) 个（如有重复的要输出多个）。 \(1 \leq A_i\le10,~10 \le B_i\le100,~100 \le C_i\le10^4\)。 这是一篇随机化优化的奇怪题解 题面十分不清楚。所以稍微修改了一下下。 注意这里的数据范围 根据二次函数对称轴 \(x=-\dfrac{b}{2a}\) 不难发现这些函数均在 \([0,+\infty)\) 单调递增 那就很简单了，直接用个大根堆维护 \(k\) 大值的方法搞一搞就好了 然后发现时间复杂度最坏似乎 \(O(nm\log m)\) 因此我们可以用随机化乱搞一下，防止特意构造的数据 \(😎\) 时间复杂度上界其实还是 \(O(nm\log m)\) 但是实际的复杂度比这...

洛谷P2679 [NOIP2015 提高组] 子串 题解 题目链接：P2679 [NOIP2015 提高组] 子串 题意： 有两个仅包含小写英文字母的字符串 \(A\) 和 \(B\)。 现在要从字符串 \(A\) 中取出 \(d\) 个互不重叠的非空子串，然后把这 \(d\) 个子串按照其在字符串 \(A\) 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 \(B\) 相等？ 注意：子串取出的位置不同也认为是不同的方案。 输出答案对 \(10^9+7\) 取模的结果。 对于所有 \(10\) 组数据： \(1\le n \le 1000,~1 \le m \le 200,~1 \le d \le m\)。 显然的字符串类型dp 一个原始的思路是： 设 \(f_{i,j,k}\) 表示仅考虑 \(A\) 的前 \(i\) 个字符，\(B\) 匹配到第 \(j\) 个字符，用了 \(k\) 个子串的方案数。 然后发现我们并不知道 \(A_i\) 是否与 \(B_j\) 匹配，无法转移 于是状态就变成了 设 \(f_{i,j,k}\) 表...

洛谷P1868 饥饿的奶牛 题解 题目链接：P1868 饥饿的奶牛 题意： 有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。 现用汉语翻译为： 有 \(N\) 个区间，每个区间 \(x,y\) 表示提供的 \(x\sim y\) 共 \(y-x+1\) 堆优质牧草。你可以选择任意区间但不能有重复的部分。 对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。 \(1 \leq n \leq 1.5 \times 10^5\)，\(0 \leq x \leq y \leq 3 \times 10^6\)。 设 \(f_i\) 表示只考虑前 \(i\) 个位置能吃到的最多牧草 \[ f_i = \max_{j \in \text{Edge}(i)}\left\{f_{j-1} + i-j+1\right\} \] 这里的 \(\text{Edge}(i)\) 表示以 \(i\) 结尾的所有区间组成的集合 对于每个区间 \([x,y]\) ，我们建一条 \(y \to x\) 的边 这样就可以枚举 \(j\) 了 时间复杂度 \(O(m)...