Q779’s Blog

UVA11362 Phone List 题解 题目链接：UVA11362 Phone List 题意：给定\(n\)个长度不超过\(10\)的数字串，判断是否有两个字符串\(A\)和\(B\),满足\(A\)是\(B\)的前缀，若有，输出NO，若没有，输出YES。 其实可以去建个 \(\tt{trie}\) 树然后dfs的 但是方便起见，直接sort就能过 时间复杂度 \(O(Qn^2)\) 代码： #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 #d...

洛谷P4052 [JSOI2007]文本生成器 题解 题目链接：P4052 [JSOI2007]文本生成器 题意： JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。 该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。 也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 \(s\) 包含单词 \(t\)，当且仅当单词 \(t\) 是文章 \(s\) 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？ 答案对 \(10^4 + 7\) 取模。 对于全部的测试点，保证： \(1 \leq n \leq 60\)，\(1 \leq m \leq 100\)。 \(1 \leq |s_i| \leq 1...

洛谷P4113 [HEOI2012]采花 题解 题目链接：P4113 [HEOI2012]采花 题意：萧薰儿是古国的公主，平时的一大爱好是采花。 今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。 花园足够大，容纳了 \(n\) 朵花，共有 \(c\) 种颜色，用整数 \(1 \sim c\) 表示。且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴。同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。 由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了 \(m\) 个行程，然后一一向你询问公主能采到的花共有几种不同的颜色。 \(1 \leq n, c, m \leq 2 \times 10^6\)。 对于全部的测试点，保证 \(1 \leq x_i \leq c\)，\(1 \leq l \leq r \leq n\)。 其实就是 P1972 [SDOI200...

洛谷P3294 [SCOI2016]背单词 题解 题目链接：P3294 [SCOI2016]背单词 题意：给定 \(n\) 个不同的字符串，求一个最优顺序使得花费最小 设当前字符串为 \(a\) ，位于排列中的 \(x\) 位置 如果 \(a\) 存在后缀且 \(a\) 的后缀在 \(a\) 之后，花费增加 \(n^2\) 如果 \(a\) 不存在后缀，则花费增加 \(x\) 设 \(y\) 为 \(a\) 之前与其相距最小的，且是 \(a\) 的后缀的字符串的位置（前提是 \(a\) 存在后缀），则花费增加 \(x-y\) 根据贪心，前两个条件基本上没有用 同时为了方便处理，把所有字符串反转，考虑其前缀。 原问题转化为： 设某个字符串为 \(a_i\) ，位于排列中的 \(x_i\) 位置 \(a_i\) 所有前缀必须在 \(a_i\) 之前 设 \(y_i\) 为 \(a_i\) 之前与其相距最小的，且是 \(a_i\) 的前缀的字符串的位置 如果 \(a\) 不存在前缀，则 \(y_i=0\) ，记 \(v_i=x_i-y_i\) 给定 \(n\) 个字符串，...

洛谷P2444 [POI2000]病毒 题解 题目链接：P2444 [POI2000]病毒 题意： 二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。 示例： 例如如果 \(\{011, 11, 00000\}\) 为病毒代码段，那么一个可能的无限长安全代码就是 \(010101 \ldots\)。如果 \(\{01, 11, 000000\}\) 为病毒代码段，那么就不存在一个无限长的安全代码。 现在给出所有的病毒代码段，判断是否存在无限长的安全代码。 \(1 \leq n \leq 2000\)，所有病毒代码段的总长度不超过 \(3 \times 10^4\)。 不难发现这是一个 \(\tt{AC}\) 自动机的题目 考虑一个安全代码在 \(\tt{AC}\) 自动机上是怎么跑的 显然它会从 \(0\) 结点开始跑，然后最后在一个环上面跑 这个环显然不能包含「是字符串结尾的结点」 仔细想一想，其实不止...

洛谷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_...