Q779’s Blog

洛谷P1608 路径统计 题解 题目链接：P1608 路径统计 题意： 一句话题意：最短路计数。 “RP 餐厅” 的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让 HZH,TZY 去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有 \(N\) 个地方，而且他们目前处在标注为 “1” 的小镇上，而送餐的地点在标注为 “N” 的小镇。（有点废话）除此之外还知道这些道路都是单向的，从小镇 \(I\) 到 \(J\) 需要花费 \(D[I, J]\) 的时间，为了更高效快捷的将快餐送到顾客手中，他们想走一条从小镇 \(1\) 到小镇 \(N\) 花费最少的一条路，但是他们临出发前，撞到因为在路上堵车而生气的 FYY，深受启发，不能仅知道一条路线，万一。。。于是，他们邀请 FYY 一起来研究起了下一个问题：这个最少花费的路径有多少条？ 对于 \(100\%\) 的数据 \(1\leq N\leq 2000\)，\(0\leq E\leq N\times (N-1)\)，\(1\leq C\leq 10\). 最短路计数据说不能用spfa（spfa已死）...

洛谷P5440 【XR-2】奇迹 题解 题目链接：P5440 【XR-2】奇迹 题意： 我们称一个日期为一个八位数，第 1~4 位构成年，第 5~6 位构成月，第 7~8 位构成日，不足位数用 0 补足。同时，要求日期所代表的这一天真实存在，且年的范围为 1~9999。 出现奇迹的日期都存在相同的特点：由“日”组成的两位数，由“月+日”组成的四位数，由“年+月+日”组成的八位数均为质数。但并不是所有存在这样特点的日期都一定会出现奇迹。 现在，你得到了一个可能会出现奇迹的日期，然而不幸的是这个日期却是残缺的，八位中可能有若干位无法确定。你需要知道这个日期有多少种可能，这样你才能做好充足的准备去迎接奇迹的到来。 对 \(100\%\) 的数据保证 \(1 \le T \le 10\)。 一个朴素的解法： 预处理所有合法日期， 然后对于每个询问暴力枚举所有合法日期 常数巨大，但是写起来不容易错 其实我也想了很多剪枝方法不过懒得写 代码是学的这篇题解 ，感觉十分简洁 代码： #include <iostream> #include <string> #include &l...

洛谷P1514 [NOIP2010 提高组] 引水入城 题解 题目链接：P1514 [NOIP2010 提高组] 引水入城 题意： 在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个\(N\) 行\(\times M\) 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。 因此，只有与湖泊毗邻的第\(1\) 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第\(N\) 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。 首先可以想到我们直接在每个岸边的点跑dfs 同...

洛谷P1535 [USACO08MAR]Cow Travelling S 题解 题目链接：P1535 [USACO08MAR]Cow Travelling S 题意： 奶牛们在被划分成 \(N\) 行 \(M\) 列（\(2 \leq N,M \leq 100\)）的草地上游走， 试图找到整块草地中最美味的牧草。 Farmer John 在某个时刻看见贝茜在位置 \((R_1, C_1)\)，恰好 \(T\)（\(0 \lt T \leq 15\)）秒后，FJ 又在位置 \((R_2, C_2)\) 与贝茜撞了正着。FJ 并不知道在这 \(T\) 秒内贝茜是否曾经到过 \((R_2, C_2)\)，他能确定的只是，现在贝茜在那里。 设 \(S\) 为奶牛在 \(T\) 秒内从 \((R_1, C_1)\) 走到 \((R_2, C_2)\) 所能选择的路径总数，FJ 希望有 一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动 \(1\) 单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。 ...

洛谷P1378 油滴扩展 题解 题目链接：P1378 油滴扩展 题意： 在一个长方形框子里，最多有 \(N\) 个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 \(N\) 个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合） 注：圆的面积公式 \(V = \pi r^2\)，其中 \(r\) 为圆的半径。 对于 \(100\%\) 的数据，\(1 \le N \le 6\)，坐标范围在 \([-1000, 1000]\) 内。 数据范围告诉我们这就是一道暴搜题 枚举油滴扩展的顺序，然后和已经扩散好的油滴算一下距离 注意距离可能为负，此时新油滴在某油滴内部，此时认为 \(r=0\) 即可 最后的答案就是总面积减去油滴面积并 时间复杂度 \(O(n\times n!)\) 代码： #include <iostream> #include <string> #include <vector> #inclu...

洛谷P4983 忘情 题解 题目链接：P4983 忘情 题意： “为什么要离开我！” “因为你没玩儿转！” “我玩儿转了！” “那好，你现在就给我维护这么一个式子！” “为什么要出这么毒瘤的东西。” “为了恶心你。” “……” \(……………………………\) 你的 \(npy\) 为了恶心你，特地请了四位大神和一个辣鸡！ \(\rm hdxrie\) 说：“我们得求和。”于是有了 \(\sum\limits_{i=1}^{n}x_i\) 。 \(\rm Imagine\) 说：“我们得有平均数。”于是有了 \(\bar x\) 。 \(\rm TimeTraveller\) 说：“我们得有加减乘除。”于是有了一些恶心的组合。 \(\rm Althen·Way·Satan\) 说：“我们还得有平方。”于是我们将它平方。 最垃圾的 \(\rm ZredXNy\) 说：“那我帮你们整合一下。” 于是，我们得到了这么一个式子 \(:\) \[ \frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2}...

洛谷P3195 [HNOI2008]玩具装箱 题解 题目链接：P3195 [HNOI2008]玩具装箱 题意： 有 \(n\) 个玩具，第 \(i\) 个玩具的价值为 \(c_i\) 。要求将这 \(n\) 个玩具排成一排，分成若干段。对于一段 \([l,r]\) ，它的代价为 \((r-l+\sum_{i=l}^{r}c_i-L)^2\) ，其中 \(L\) 为一个常量，求分段的最小代价。 \(1 \leq n \leq 5 \times 10^4\)，\(1 \leq L \leq 10^7\)，\(1 \leq C_i \leq 10^7\) upd. 新增斜率优化新的理解。 令 \(f_i\) 表示前 \(i\) 个物品分成若干段的最小代价，则 \[ f_i = \min_{j < i}\left\{f_j + (S_i + i -S_j -j -L-1)^2\right\} \] 其中 \(S_i\) 为前 \(i\) 个物品的价值和，即 \(S_i = \sum_{j=1}^{i}c_j\) 直接去做是 \(O(n^2)\) ，考虑斜率优化 令 \(a_i ...

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 因为本题中这两个点不能同时选，所以这么...