Q779’s Blog

SP1716 GSS3 - Can you answer these queries III 题解 题目链接：SP1716 GSS3 - Can you answer these queries III 题意： \(n\) 个数， \(q\) 次操作 操作0 x y把 \(A_x\) 修改为 \(y\) 操作1 l r询问区间 \([l, r]\) 的最大子段和 \(n \le 5\times 10^4,~q \le 5 \times 10^4\) 线段树维护最大子段和（去年就看到了一直没去学） 考虑两个相邻区间合并，设答案为 \(\text{res}_u\) 若不考虑中间的分界线，则有 \[ \text{res}_u = \max\{\text{res}_l , \text{res}_r\} \] 若考虑中间的分界线，于是尝试合并，则？ 可是我们并不知道 \(\text{res}_l\) 和 \(\text{res}_r\) 对应的序列，也不知道可否合并等等 注意到合并后的区间包含三种本质不同的子段 全部在左区间 全部在右区间 被中间线分割 在进一步，中间线分割意味...

洛谷P1083 [NOIP2012 提高组] 借教室 题解 题目链接：P1083 [NOIP2012 提高组] 借教室 题意： 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问题。 我们需要处理接下来 \(n\) 天的借教室信息，其中第 \(i\) 天学校有 \(r_i\) 个教室可供租借。共有 \(m\) 份订单，每份订单用三个正整数描述，分别为 \(d_j,s_j,t_j\)，表示某租借者需要从第 \(s_j\) 天到第 \(t_j\) 天租借教室（包括第 \(s_j\) 天和第 \(t_j\) 天），每天需要租借 \(d_j\) 个教室。 我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 \(d_j\) 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满...

洛谷P4552 [Poetize6] IncDec Sequence 题解 题目链接：P4552 [Poetize6] IncDec Sequence 题意： 给定一个长度为 \(n\) 的数列 \({a_1,a_2,\cdots,a_n}\)，每次可以选择一个区间\([l,r]\)，使这个区间内的数都加 \(1\) 或者都减 \(1\)。 请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。 对于 \(100\%\) 的数据，\(n\le 100000, 0 \le a_i \le 2^{31}\)。 这道题思路比较有趣，代码很简单但是相对来说不好想 本文比较长，建议耐心阅读（当然也可以直接 ⌘+w 或者 ctrl+w 啦） 差分，常用于 \(O(1)\) 区间加减，全局询问 对于这种看上去也不是用数据结构做的题目， 考虑差分。差分数组 \(b_i\) 的定义为 \(b_i = a_i-a_{i-1}\) 容易发现 \(a_i = \sum_{1 \le j \le i}b_i\) ，值得注意的是， \(a_1 = b_1...

洛谷P5521 [yLOI2019] 梅深不见冬 题解 题目链接：P5521 [yLOI2019] 梅深不见冬 题意： 给定一棵树，根节点为 \(1\) ，有点权 \(w_i\) ，cxy 想在在结点上放满梅花。 她从这棵树的 \(1\) 号节点出发，沿着树上的边行走。 设当前在 \(u\) ，则 cxy 每次只能走到一个没有走过的儿子结点 \(v\) ，或者回到 \(u\) 的父亲。 当且仅当一个结点 \(u\) 的所有儿子 \(v\) 都放满了 \(w_v\) 朵，才可以在 \(u\) 上放置梅花。 梅花可以随时收回，求每个结点放上梅花的最小花费。 数据范围： \(1 \leq n \leq 10^5 + 4,~1 \leq w_i \leq 1000\)。 设第 \(i\) 个结点放梅花的最小花费为 \(f_i\) ，不难发现 \[ f_u = \max\left\{ \max_{v \in \text{son(u)}} \left\{f_v + \sum_{k \in \text{son}(u)\, \land \,k \text{ before } v} w_k\r...

洛谷P3131 [USACO16JAN]Subsequences Summing to Sevens S 题解 题目链接：P3131 [USACO16JAN]Subsequences Summing to Sevens S 题意：给你n个数，分别是a[1],a[2],…,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],…,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。 属于简单萌萌题叭。思路还是挺有趣的。 区间和用个前缀和 \(S_i\) ，直接枚举 \(l,r\) 肯定不行 这里用个小技巧，如果存在 \(j < i\) 满足 \[ S_i \equiv S_j \pmod 7 \] 则 \[ S_i-S_j \equiv 0 \pmod 7 \] 所以我们把所有前缀和都去模一下 \(7\) 然后找一下最长的区间就好啦 时间复杂度 \(O(n)\) 注意这里有个坑，\(j\) 可以为 \(0\) 代码： #include <iostream> #include <string>...

洛谷P2678 [NOIP2015 提高组] 跳石头 题解 题目链接：P2678 [NOIP2015 提高组] 跳石头 题意： 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。 对于 \(100\%\)的数据,\(0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000\)。 求最小值最大，二分经典题。 为什么是二分呢？因为我们并不知道最小值是多少 我们可以枚举一个最小值，然后使它尽可能的大 对于有单调性的题目可以使用二分，显然这题有单调性 然后就没啥了，二分一下就好了 注意终点不是 \(N\) 。时间复杂度 \(O(N \log L)\) 相信大家做这题的时候应该二分不太熟， 这...

洛谷P1314 [NOIP2011 提高组] 聪明的质监员 题解 题目链接：P1314 [NOIP2011 提高组] 聪明的质监员 题意： 小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是： 1 、给定 \(m\) 个区间 \([l_i,r_i]\)； 2 、选出一个参数 \(W\)； 3 、对于一个区间 \([l_i,r_i]\)，计算矿石在这个区间上的检验值 \(y_i\)： \[ y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j \] 其中 \(j\) 为矿石编号。 这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即：\(\sum\limits_{i=1}^m y_i\) 若这批矿产的检验结果与所给标准值 \(s\) 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一...

洛谷P3647 [APIO2014] 连珠线 题解 题目链接：P3647 [APIO2014] 连珠线 题意： 在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 \(1\) 到 \(n\)。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子： Append(w, v)：一个新的珠子 \(w\) 和一个已经添加的珠子 \(v\) 用红线连接起来。 Insert(w, u, v)：一个新的珠子 \(w\) 插入到用红线连起来的两个珠子 \(u, v\) 之间。具体过程是删去 \(u, v\) 之间红线，分别用蓝线连接 \(u, w\) 和 \(w, v\)。 每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。 给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。 你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。 \(1 \leq n \leq 200000\)。 开学前两天准...

洛谷P3047 [USACO12FEB]Nearby Cows G 题解 题目链接：P3047 [USACO12FEB]Nearby Cows G 题意： 给你一棵 \(n\) 个点的树，点带权，对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 「数据范围」 对于 \(100\%\) 的数据：\(1 \le n \le 10^5\)，\(1 \le k \le 20\)，\(0 \le c_i \le 1000\) 换根dp，也叫二次扫描法 这题随便找一个根当做树根，然后扫两遍才能出答案 首先设 \(f[u][j]\) 表示 \(u\) 所在子树，与 \(u\) 相距恰好 \(j\) 的结点个数，则 \[ f[u][j]=\sum_{v \in \text{son}[u]} f[v][j-1] \] 这是第一遍dfs，可以发现我们没有从非 \(u\) 所在子树获取答案 考虑第二遍dfs，设 \(g[u][j]\) 表示在整棵树中与 \(u\) 相距恰好 \(j\) 的结点个数 这个答案一定是从父节点的 \(g\) 转移而来 但是这里会有一个问题，\...

洛谷P4037 [JSOI2008]魔兽地图 题解 题目链接：P4037 [JSOI2008]魔兽地图 题意： DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。 DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。 比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无...

洛谷P1272 重建道路 题解 题目链接：P1272 重建道路 题意： 一场可怕的地震后，人们用 \(N\) 个牲口棚（编号 \(1\sim N\)）重建了农夫 John 的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。 John 想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有 \(P\) 个牲口棚的子树和剩余的牲口棚分离，John 想知道这些道路的最小数目。 \(1\le N\le 150\)，\(1\le P\le N\)，保证给出的是一棵树。 题目有点难懂，意思就是说切最少刀切出一个大小为 \(p\) 的块，显然树上背包 设 \(dp[u][j]\) 表示 \(u\) 所在子树切出大小为 \(j\) 的块并强制包含 \(u\) 的最小花费，则 \[ dp[u][j+k]=\min(dp[u][j+k],\text{tmp}[j]+dp[v][k]-1) \] 其中 \(\text{tmp}[j]\) 为上一轮的 \(dp[u][j]\) 。 后面一个柿子比较难懂 考...

洛谷P1734 最大约数和 题解 题目链接：P1734 最大约数和 题意：选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。 设 \(dp[i][j]\) 表示只考虑前 \(i\) 个数总和不超过 \(j\) 的最大价值，则 \[ dp[i][j]= \max(dp[i-1][j],dp[i-1][j-i]+v[i]) \] \(v[i]\) 可以 \(O(n \log n)\) 预处理 时间复杂度 \(O(n^2)\) 代码： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f...