Q779’s Blog

CF125E MST Company 题解 题目链接：CF125E MST Company 题意： 给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足节点 \(1\) 正好连了 \(k\) 条边。 输出最优方案所选的边 \(1 \le n,k \le 5000,~0 \le m \le 10^5,~1 \le w \le 10^5\) 这道题的加强版，题解（下文我摘抄过来了一部分，反正都是我写的） 我们把与 \(s\) 相连的所有边标记为白边，其他边为黑边 然后问题就转化为了选恰好 \(k\) 条白边的最小花费 考虑wqs二分，最好用归并优化一下 这题的难点在无解的情况如何判断 白边不够用，如果与 \(s\) 相连的边小于 \(k\) 条，无解 黑边不够用，也就是生成树不得不包括大于 \(k\) 条白边，无解 那道弱化版的题目只要求输出最优解的花费 但是我们都知道wqs二分的那个切线可能同时切到多个点 然后我的代码的写法是权值相等时优先取白边 所以答案中选了 \(k\) 条白边后就不要再选白边了（当然这样不会改变权值...

洛谷P5633 最小度限制生成树 题解 题目链接：P5633 最小度限制生成树 题意： 给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 \(s\) 的节点正好连了 \(k\) 条边。 可能会出现无解的情况，如果无解，则输出 Impossible。 对于 \(100\%\) 的数据，\(1\leq n \le 5\times 10^4\)，\(1\leq m \le 5\times 10^5\)，\(1\leq k \le 100\)，\(0\leq w\leq 3\times 10^4\)。 如果做过这道题应该会觉得很简单了 我们把与 \(s\) 相连的所有边标记为白边，其他边为黑边 然后问题就转化为了选恰好 \(k\) 条白边的最小花费 考虑wqs二分，最好用归并优化一下 这题的难点在无解的情况如何判断 白边不够用，如果与 \(s\) 相连的边小于 \(k\) 条，无解 黑边不够用，也就是生成树不得不包括大于 \(k\) 条白边，无解 时间复杂度 \(O(n\log n + n\log {\max\{w_...

洛谷P2619 [国家集训队]Tree I 题解 题目链接：P2619 [国家集训队]Tree I 题意： 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(\text{need}\) 条白色边的生成树。 题目保证有解。 对于 \(100\%\) 的数据，\(n\leq 5\times10^4,m\leq 10^5\)。 所有数据边权为 \([1,100]\) 中的正整数。 直接 \(O(nm)\) 的dp肯定是不行的，考虑wqs二分。 在这题中，wqs二分做的其实就是给白边增加额外权值 使最优方案恰好选满 \(\text{need}\) 条白边 。 假设二分的权值为 \(\text{mid}\) ， 若选了大于 \(\text{need}\) 条白边，则将白边边权增大，反之同理。 具体的，设选 \(x\) 条白边的最小花费 \(f(x)\) 注意到点集 \((x,f(x))\) 形成一个下凸壳 也就是 \(f(x)\) 为一个整数域的下凸函数 我们二分一个斜率 \(k\) ，用这条直线去尝试切凸壳 显然这条直线在不确定 \(y\) 轴截距时可以与这个...

洛谷P2607 [ZJOI2008] 骑士 题解 题目链接：P2607 [ZJOI2008] 骑士 题意： Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。 最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。 骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。 战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。 为了描述战斗力，我们将骑士按照 \(1\) 至 \(n\) 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所...

洛谷P1453 城市环路 题解 题目链接：P1453 城市环路 题意： 整个城市可以看做一个 \(n\) 个点，\(n\) 条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有 \(2\) 条简单路径互通。图中的其它部分皆隶属城市郊区。 现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 \(2\) 个点不能同时开店，每个点都有一定的人流量，第 \(i\) 个点的人流量是 \(p_i\)，在该点开店的利润就等于 \(p_i×k\)，其中 \(k\) 是一个常数。 Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？ 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq p_i \leq 10^4\)，\(0 \leq u, v < n\)，\(0 \leq k \leq 10^4\)，\(k\) 的小数点后最多有 \(6\) 位数字。 显然这是一个基环树dp 对于基环树dp， 基本思想就是在那个环上找两个相邻点 分别作为根节点跑树形dp 因为本题中这两个点不能同时选，所以这么...

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 不想费时间去检验另一...