Q779’s Blog

洛谷P1792 [国家集训队]种树 题解 题目链接：P1792 [国家集训队]种树 题意： A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。 园林部门得到指令后，初步规划出 \(n\) 个种树的位置，顺时针编号 \(1\) 到 \(n\)。并且每个位置都有一个美观度 \(A_i\)，如果在这里种树就可以得到这 \(A_i\) 的美观度。但由于 \(A\) 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（\(i\) 号位置和 \(i+1\) 号位置叫相邻位置。值得注意的是 \(1\) 号和 \(n\) 号也算相邻位置）。 最终市政府给园林部门提供了 \(m\) 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将 \(m\) 棵树苗全部种上，给出无解信息。 \(m\le n \le 2\times 10^5\)，\(-1000\le A_i\le1000\)。 考虑反悔型贪心，维护一个大根堆，先把所有结点加进去 然后每次取出权值最大的点，把它加入答案 如何反悔呢？ 我们再加入一个权值为 \(a_{l_i} + a_{r_i...

洛谷P1016 [NOIP1999 提高组] 旅行家的预算 题解 题目链接：P1016 [NOIP1999 提高组] 旅行家的预算 题意： 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 \(D_1\)、汽车油箱的容量 \(C\)（以升为单位）、每升汽油能行驶的距离 \(D_2\)、出发点每升汽油价格\(P\)和沿途油站数 \(N\)（\(N\) 可以为零），油站 \(i\) 离出发点的距离 \(D_i\)、每升汽油价格 \(P_i\)（\(i=1,2,…,N\)）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。 \(N \le 6\)，其余数字$ $。 经典的反悔型贪心 每次碰到一个加油站，烧掉最便宜的油（从上一个位置到现在位置） 接着退掉比当前加油站贵的油（反悔），然后直接加满当前加油站的油 记得设一个终点站，显然它和起点的距离为 \(d_1\) ，推掉所有多的油 这个油价的维护直接用单调队列维护，这里用deque<node>来搞方便一些 时间复杂度 \(O(n)\)...

洛谷P1631 序列合并 题解 题目链接：P1631 序列合并 题意： 有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到\(N^2\)个和，求这\(N^2\)个和中最小的N个。 对于100%的数据中，满足1<=N<=100000。 维护一个大根堆，初始有 \(N\) 个极大值 贪心地选择较小的 \(A_i\) 和较小的 \(B_i\) 合并 然后有一个简单易懂的剪枝，具体见代码 时间复杂度 \(O(n \log n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> #include <queue> using namespace std; #define...

洛谷P3871 [TJOI2010]中位数 题解 题目链接：P3871 [TJOI2010]中位数 题意： 给定一个由N个元素组成的整数序列，现在有两种操作： 1 add a 在该序列的最后添加一个整数a，组成长度为N + 1的整数序列 2 mid 输出当前序列的中位数 中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个） 例1：1 2 13 14 15 16 中位数为13 例2：1 3 5 7 10 11 17 中位数为7 例3：1 1 1 2 3 中位数为1 对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000 序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复 考虑维护一个对顶堆，详细见 P1168 然后就是板子题，注意对询问分类讨论 时间复杂度 \(O((n+m) \log (n+m))\) 代码： #include <iostream> #include <string> #include <vector> #include <al...

洛谷P3522 [POI2011]TEM-Temperature 题解 题目链接：P3522 [POI2011]TEM-Temperature 题意： 某国进行了连续 \(n\) ( \(1 \le n \le 1,000,000\)）天的温度测量，测量存在误差，测量结果是第 \(i\) 天温度在 \([l_i,r_i]\) 范围内。 求最长的连续的一段，满足该段内可能温度不降。 不难发现合法区间为 \(\max\{l_i\}>r_{i+1}\) 考虑单调队列维护最大值 注意答案的更新应该用(i-1)-q[st]+1 因为如果有个 \(l_i\) 特别大，把当前维护的合法的 \(l\) 都给pop掉了 计数不应当是从现在的 \(l_i\) 开始，而是最后一个被pop掉的 这样用q[st]正好（我的代码是(l,r]的） 时间复杂度 \(O(n)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio>...

洛谷P2422 良好的感觉 题解 题目链接：P2422 良好的感觉 题意： kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 \(A_i\)，\(A_i\) 越大，表示人感觉越舒适。在一段时间 \(\left[i, j\right]\) 内，人的舒适程度定义为 \(\left[i, j\right]\) 中最不舒服的那一天的感受值 \(\times\) \(\left[i, j\right]\)中每一天感受值的和。现在给出 kkk 在连续 \(N\) 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？ 对于 \(100\%\) 的数据，\(1\le N\le 100000\)，\(1\le \texttt{感受值}\le 1000000\)。 题意简化一下就是 找到一个区间，使得区间最小值乘以区间的和最大 考虑每个最小值对区间的贡献 设当前的数为 \(a_i\) ， 它能成为最小值的区间 \([l,r]\) 满足 \(l\in [j+1,i],r\in [i,k-1]\) 其中 \(j\) 是所有 \(a_j <a_i\) 中最大的 \(j\) ，\(k\)...

洛谷P3512 [POI2010]PIL-Pilots 题解 题目链接：P3512 [POI2010]PIL-Pilots 题意：给定 \(n\) 个数，找一个最长区间，使得区间中的最大值减最小值不超过 \(k\) 题面写的太烂了 考虑用两个单调队列分别维护从 \(1\) 到 \(i\) 的最大值和最小值 注意pop()时候的判断，具体见代码 时间复杂度 \(O(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 #defin...

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\) 结点开始跑，然后最后在一个环上面跑 这个环显然不能包含「是字符串结尾的结点」 仔细想一想，其实不止...