Q779’s Blog

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

洛谷P4799 [CEOI2015 Day2] 世界冰球锦标赛 题解 题目链接：P4799 [CEOI2015 Day2] 世界冰球锦标赛 题意： 译自 CEOI2015 Day2 T1「Ice Hockey World Championship」 今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。 给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。 数据组号 \(1-2\) \(3-4\) \(5-7\) \(8-10\) \(N \leq\) \(10\) \(20\) \(40\) \(40\) \(M \leq\) \(10^6\) \(10^{18}\) \(10^6\) \(10^{18}\) 首先这个 \(20\) 就很有趣 显然暴搜是吧 那么 \(4...

洛谷P3435 [POI2006] OKR-Periods of Words 题解 题目链接：P3435 [POI2006] OKR-Periods of Words 题意： 对于一个仅含小写字母的字符串 \(a\)，\(p\) 为 \(a\) 的前缀且 \(p\ne a\)，那么我们称 \(p\) 为 \(a\) 的 proper 前缀。 规定字符串 \(Q\)（可以是空串）表示 \(a\) 的周期，当且仅当 \(Q\) 是 \(a\) 的 proper 前缀且 \(a\) 是 \(Q+Q\) 的前缀。 例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。 求给定字符串所有前缀的最大周期长度之和。 \(1\le |a| \le 10^6\) 考虑如何最大化周期 \(Q\) 对于某个前缀，例如 \(s = \tt{aabaaaab}\) 不难发现它的最长周期就是 \(\tt{aabaa}\) 仔细观察 \(\tt{\color{red}{aab}\color{blue}{aa}\color{red}{a...

洛谷P4287 [SHOI2011]双倍回文 题解 题目链接：P4287 [SHOI2011]双倍回文 题意： 记字符串 \(w\) 的倒置为 \(w^R\) 。例如 \((\tt{abcd})^R=\tt{dcba}\) ， \((\tt{abba})^R=\tt{abba}\) 。 对字符串 \(x\) ，如果 \(x\) 满足 \(x^R=x\) ，则称之为回文；例如 \(\tt{abba}\) 是一个回文，而 \(\tt{abed}\) 不是。 如果 \(x\) 能够写成的 \(ww^Rww^R\) 形式，则称它是一个“双倍回文”。换句话说，若要 \(x\) 是双倍回文，它的长度必须是 \(4\) 的倍数，而且 \(x\) ， \(x\) 的前半部分， \(x\) 的后半部分都要是回文。例如 \(\tt{abbaabba}\) 是一个双倍回文，而 \(\tt{abaaba}\) 不是，因为它的长度不是 \(4\) 的倍数。 \(x\) 的子串是指在\(x\)中连续的一段字符所组成的字符串。例如 \(\tt{be}\) 是 \(\tt{abed}\) 的子串，而 \(\t...

洛谷P2375 [NOI2014] 动物园 题解 题目链接：P2375 [NOI2014] 动物园 题意： 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。 园长：“对于一个字符串\(S\)，它的长度为\(L\)。我们可以在\(O(L)\)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？” 熊猫：“对于字符串\(S\)的前\(i\)个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作\(next[i]\)。” 园长：“非常好！那你能举个例子吗？” 熊猫：“例\(S\)为abcababc，则\(next[5]=2\)。因为\(S\)的前\(5\)个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出\(next[1] = next[2] = next[3] = 0\)，\(next[4] = next[6] = ...

洛谷P4568 [JLOI2011] 飞行路线 题解 题目链接：P4568 [JLOI2011] 飞行路线 题意： Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 \(n\) 个城市设有业务，设这些城市分别标记为 \(0\) 到 \(n-1\)，一共有 \(m\) 种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 \(k\) 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？ 对于 \(100\%\) 的数据，\(2 \le n \le 10^4\)，\(1 \le m \le 5\times 10^4\)，\(0 \le k \le 10\)，\(0\le s,t,a,b\le n\)，\(a\ne b\)，\(0\le c\le 10^3\)。 分层图板子题 不写具体做法了，就总结几个易错点 无向图的e数组开 \[ M\times (K+1) \times 4 \] ...

洛谷P4551 最长异或路径 题解 题目链接：P4551 最长异或路径 题意：给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。 异或路径指的是指两个结点之间唯一路径上的所有边权的异或。 \(1\le n \le 100000,~0 < u,v \le n,~0 \le w < 2^{31}\)。 首先可以想到一个常用trick：前缀和处理边权异或和 然后对于每个异或和，我们都要找到一个和它异或值尽可能大的前缀和 直接枚举是不行的，考虑建01trie 01trie其实很简单，就是把每个数字的二进制形式看成字符串去建trie 贪心地选择高位，具体看代码就可以了，很简单 时间复杂度 \(O(n \log \max\{w_i\})\) ，其实就是 \(O(30 \times n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdi...

洛谷P3698 [CQOI2017]小Q的棋盘 题解 题目链接：P3698 [CQOI2017]小Q的棋盘 题意： 小 Q 正在设计一种棋类游戏。 在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 \(V\) 个格点，编号为\(0,1,2,\dots , V−1\)，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。 小 Q 现在想知道，当棋子从格点 \(0\) 出发，移动 \(N\) 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。 对于 \(100\%\) 的测试点，\(N,V \le 100,~0 \le a_i,b_i< V\) 。 显然树上背包 值得注意的是，我们并不知道走的路线有没有回到 \(u\) 因此要多加一维 设 \(f_{u,j,0/1}\) 表示 \(u\) 所在子树，走了 \(j\) 步，\(0/1\) 表示是/否回到 \(u\) 不难发现 \[ f_{u,j,0}=\max_{v...