Q779’s Blog

洛谷P3065 [USACO12DEC]First! G 题解 题目链接：P3065 [USACO12DEC]First! G 题意： Bessie一直在研究字符串。她发现，通过改变字母表的顺序，她可以按改变后的字母表来排列字符串（字典序大小排列）。 例如，Bessie发现，对于字符串串“omm”，“moo”，“mom”和“ommnom”，她可以使用标准字母表使“mom”排在第一个（即字典序最小），她也可以使用字母表“abcdefghijklonmpqrstuvwxyz”使得“omm”排在第一个。然而，Bessie想不出任何方法（改变字母表顺序）使得“moo”或“ommnom”排在第一个。 接下来让我们通过重新排列字母表的顺序来计算输入中有哪些字符串可以排在第一个（即字典序最小），从而帮助Bessie。 要计算字符串X和字符串Y按照重新排列过的字母表顺序来排列的顺序，先找到它们第一个不同的字母X[i]与Y[i]，按重排后的字母表顺序比较，若X[i]比Y[i]先，则X的字典序比Y小，即X排在Y前；若没有不同的字母，则比较X与Y长度，若X比Y短，则X的字典序比Y小，即X排在Y前。 ...

洛谷P2939 [USACO09FEB]Revamping Trails G 题解 题目链接：P2939 [USACO09FEB]Revamping Trails G 题意： 约翰一共有 \(N\) 个牧场.由 \(M\) 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 \(1\) 出发到牧场 \(N\) 去给奶牛检查身体。 通过每条小径都需要消耗一定的时间。约翰打算升级其中 \(K\) 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 \(0\)。 请帮助约翰决定对哪些小径进行升级，使他每天从 \(1\) 号牧场到第 \(N\) 号牧场所花的时间最短。 \(1 \le n \le 10^4,~1\le m \le 5 \times 10^4 ,~ 1\le k \le 20\) 考虑建分层图跑最短路 首先建 \(k+1\) 个同样的图 第 \(i\) 层的结点 \(u_i\) 向 第 \(i+1\) 层的 \(v_i\) 连边 表示已经用了 \(i\) 次修改，现在是第 \(i+1\) 次修改，修改的是 \((u,v)\) ...

洛谷P4683 [IOI2008] Type Printer 题解 题目链接：P4683 [IOI2008] Type Printer 题意： 你需要利用一台可移动的打印机打印出\(N\)个单词。这种可移动式打印机是一种老式打印机，它需要你将一些小的金属块（每个包含一个字母）放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作： 在打印机当前词的末端（尾部）添加一个字母； 在打印机当前词的尾部删去一个字母（将打印机当前词的最后一个字母删去）。仅当打印机当前至少有一个字母时才允许进行该操作； 将打印机上的当前词打印出来。 初始时打印机为空，或者说它不含任何带字母的金属块。打印结束时，允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。 由于每一个操作都需要一定时间，所以需要你尽可能减少所需操作的总数目（将操作的总数最小化）。 你需要编写一个程序，给定所要打印的\(N\)个单词，找出以任意次序打印所有单词所需操作的最小数目，并输出一种这样的操作序列。 对于所有数据，\(1\leq N\leq25000\)。 显然可以用...

洛谷P3426 [POI2005]SZA-Template 题解 题目链接：P3426 [POI2005]SZA-Template 题意：你打算在纸上印一串字母。 为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。 同一个位置的相同字符可以印多次。例如：用 aba 这个印章可以完成印制 ababa 的工作（中间的 a 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 aba 这个印章不可以完成印制 abcba 的工作。 因为刻印章是一个不太容易的工作，你希望印章的字符串长度尽可能小。 输入一个长度不超过 \(5 \times 10^5\) 的非空字符串（只包含小写字母），代表要在纸上印的字符。 因为印章可以随便印，也就是无所谓什么顺序和数量 所以我们可以考虑什么样的情况可以继续 观察样例 ababbababbabababbabababbababbaba ababbaba ababbaba ababbaba ababbaba ...

洛谷P2466 [SDOI2008] Sue 的小球 题解  题目链接：P2466 [SDOI2008] Sue 的小球 题意： Sue 和 Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue 有一支轻便小巧的小船。然而，Sue 的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue 有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue 要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响 Sue 的兴趣，因为每一个彩蛋都是不同的，Sue 希望收集到所有的彩蛋。 然而 Sandy 就没有 Sue 那么浪漫了，Sandy 希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型： 将大海近似的看做 \(x\) 轴，以 Sue 所在的初始位置作为坐标原点建立一个竖直的平面直角坐标系。 一开始空中有 \(N\) 个彩蛋，对于第 \(i\) 个彩...

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