魂骸-CSDN博客

原创搜索总结）（深搜和广搜）

一．个人理解（以下只是个人理解，觉的有问题就忽略他）搜索本质就是对图的遍历，也就是考虑全部的情况后找出需要的结果。这和动态规划思想基本一样，不一样的在于优化的方向不同。搜索优化在于剪枝，也就是把不需要的情况减去从而优化（还有对结果预测如A*算法，现在还不大会以后会了在总结吧）。而动态规划则是利用空间记录重复过程的值，从而减少重复遍历而达到优化（有点像递推，从小往大推，保存小的推大时候不用再...

2018-04-26 11:14:58 2070

原创并查集

并查集并查集顾名思义，并查集分为合并和查询。在图中给定n点问你n个点组成多少部分，如：4 2 1 3 4 3 第一行告诉你，一共有4个点，2条路。下面两行告诉你，1、3之间有条路，4、3之间有条路。那么整幅图就被分成了1-3-4和2两部分。合并的思想：主要使用树型来维护在同一个树代表同一个部分，用个pre数组来表示没个点的父亲节点，一开始每个人父亲节点都是自己，但有两个点相连...

2017-08-12 17:14:11 270

尺取法尺取法顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，

2017-08-12 11:05:59 220

原创拓扑排序

拓扑排序概念对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。通俗点就是：按一定条件进行排序，完成前提条件才可以进行后面事件（如：在日常工作

2017-08-07 11:31:01 161

转载矩阵快速幂

矩阵快速幂在讲矩阵快速幂之前，先引入整数快速幂的概念。整数快速幂为了引出矩阵快速幂，以及说明快速幂算法的好处，我们可以先求整数的幂。如果现在要算X^8: 则X*X*X*X*X*X*X*X*X 按照寻常思路，一个一个往上边乘，则乘法运算进行7次。用(X*X)*(X*X)*(X*X)*(X*X)这种求法，先进行乘法得X^2，然后对X^2再执行三次乘法，这样去计算则乘法运算执行4次。已经比七次少。所

2017-08-07 11:19:53 284

原创归并排序

百度词条跳转思路描述：把一个数组细分成单个元素，每个元素看做一个数组，在把这些元素数组按顺序不断合并，1个和并成2个，2个合并成4个…直到全部合并完成。如：用途： 1 排序：归并排序的时间复杂度 O(n log n) ，空间复杂度 O（n) 2 求逆序对数：这也是归并排序的主要用途代码部分#include<iostream>using namespac

2017-06-14 21:17:53 195

原创 poj 3281 Dining（最大流）

【题目链接】http://poj.org/problem?id=3281题目意思有F中食物，D种饮料，n头牛。每种牛吃不同种类的食物和饮料，每种食物饮料只能一只牛吃，问最多满足多少头牛？解题思路把食物和饮料分两边，一头牛分成两个点放中间，容量为1.最后建立两个虚点代码部分include <iostream>#include <algorithm>#inc...

2019-04-14 22:47:57 173

原创 HDU 4289 Control（最大流）

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=4289题目意思有n个城市，m条边。每个城市用有花费权值。花费对应权值可以去除这个城市问断绝s-t连通的最少花费解题思路最小割值上等于最大流，把每个城市拆成p，p’.<p,p’>权值为城市权值，其他边p进p’出权值为无限大代码部分#include <iostream&gt...

2019-04-14 22:44:21 225

原创 poj 3436 ACM Computer Factory(最大流)

【题目链接】http://poj.org/problem?id=3436题目意思没台电脑有P个部件和n台机器，每台机器最大能生产p[i]台电脑，每台机器有输入和输出（加工前后），每个部件输入用0,1,2表示，0表示不能有接受的电脑对应的部件没装好,1表示装好，2表示无所谓。每个部件输出用0,1表示，0表示输出电脑对应的部件没装好，1表示装好满足输入才能输出。问最多能说出多少台电脑？并输出一种...

2019-04-14 22:38:27 131

原创问题 1426: [蓝桥杯][历届试题]九宫重排（map处理）

【题目链接】http://www.dotcpp.com/oj/problem1426.html题目意思如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。解题思路用BFS非常容易求出最小步数，但是怎么标记图呢？看了一些用二维标记的，感觉麻烦。所以把图变成字符串，用map处理。需要...

2019-03-10 19:34:57 322

原创计蒜客 Give Candies (2的高次幂取模)

【题目链接】 https://nanti.jisuanke.com/t/31716题目意思大数输入，求2的n-1次方解题思路2的n次方对mod取模会产生mod/2的循环，所以在大数数组转换成LL的时候取模要用mod/2，如果直接用mod在1e9+8时候出错。不理解的可以把mod取小点输出。代码部分#include<cstdio>#includ...

2018-09-16 20:55:18 606

原创 poj 3186 Treats for the Cows (区间dp)

【题目链接】 http://poj.org/problem?id=3186题目意思一个长度为n的数列，每次都可以从两端取一个值，每次获得的权值等于数列值乘取的次数。问全部取完最大权值。解题思路dp[i][j]表示从i到j最大的权值，这样正的没办法计算第几次取的，所以只能从中间往两边扩，也就是从最后一次取往前推。注意循环i要倒着，不知道为什么要倒着想想01背包。代码...

2018-09-16 16:08:21 122

原创 poj 1661 Help Jimmy (动态规划)

【题目链接】 http://poj.org/problem?id=1661题目意思场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy...

2018-09-13 20:48:20 115

原创 poj 3279 Fliptile(搜索，枚举)

【题目链接】 http://poj.org/problem?id=3279题目意思给一个n*m的矩阵，1代表黑色方块，0代表白色方块。现在一只牛要把全部方块翻成白色，它一脚下去能把白变黑，黑变白。由于蹄子太大当它踩某格时候周围上下左右都将根随变换。问牛最少踩的次数的方案，如果有多种输出字典序小的。无法则输出 “IMPOSSIBLE”解题思路因为白的踩一变黑的，黑的踩一次变...

2018-09-12 20:18:02 133

原创 HDU 6315 Naive Operations （线段树）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6315题目意思给定长度n的数列b[i]，m次操作，1：给a[i]一个区间内都加上1；2：求和一个区间a[i]/b[i]向下取整。解题思路区间更新和区间查询，不难想到用线段树。现在就是怎么处理a[i]/b[i]。让线段树维护一个b[i]的最大值，一个a[i]的最小值,sum=...

2018-07-31 10:40:16 516 3

原创 HDU 6324 Problem F. Grab The Tree(博弈，异或)

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6324题目意思Q与T玩游戏，在一棵树上每个节点都有一个权值，Q能取任意个节点，但是这些节点不能相连，剩下的都归T。比较两个人节点权值全部的异或和。如果相同输出’D’解题思路根据异或的性质Q异或T会等于全部异或和。所以Q只要取异或总和最高为为1的那部分。剩下肯定比他小。但如果...

2018-07-31 10:17:05 472

原创 HDU 6319 Problem A. Ascending Rating （单调队列）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6319题目意思给定一个长度为n的序列，给出前k个值，后面根据公式自己算。现在问你每个区间长度为m的子序列最大值异或上i和最大值变化次数异或上i的求和。解题思路用单调队列来维护，只要把序列倒过来维护递减序列。这样队列中元素个数就是count个数（倒的是递减正的就是递增所以每两...

2018-07-31 10:09:21 480

原创 HDU 6299 Balanced Sequence （贪心）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6299题目意思给你n个‘(’‘)’组成的字符串，“（）”算平衡，现在问你将n个字符串重新组合，能达到的最大平衡值。一个“（）”算2.解题思路一个字符串括号用栈来模拟，遇到‘(’压人栈，遇到‘)’如果栈中有‘（’则弹出（‘（’注定在栈的最顶端）。每个字符串都这么处理后剩下都为...

2018-07-26 11:26:45 244

原创 HDU 6305 RMQ Similar Sequence（笛卡尔树，期望）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6301题目意思定义RMQ(A,l,r)为：序列A中，满足A[i] = max(A[l],A[l+1],…,A[r])的最大的i。如果对于任意(l,r)都满足RMQ(A,l,r)=RMQ(B,l,r)则为A和B是RMQ Similar。现在出A序列，B序列的每个数都是0~1之间的实数，问...

2018-07-26 11:03:56 177

原创 HDU 6301 Distinct Values （set）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=6301题目意思让你寻找一个长度为n的最小字典序数组，数组满足m个区间任意两数值不同。解题思路用数组pre[i]记录以i为右区间的最左区间，也就是i能覆盖的最大区间。然后用set来记录能使用的数值。从左往右填值。在一个区间的不断弹出数值，如果在区间左边也就是小于pre[i],...

2018-07-24 11:39:33 144

原创 HDU 6300 Triangle Partition

【题目链接】 http://poj.org/problem?id=6300题目意思给3*n个点（不存在3点共线）问你怎么划三角形任意两三角形都不相交。解题思路题解给的是用凸包做，但是题目既然三点不共线那么直接排序从左到右划分就好了代码部分#include &lt;iostream&gt;#include &lt;algorithm&gt;#inclu...

2018-07-24 10:08:18 182

原创 HDU 6308 Time Zone（模拟）

【题目链接】 http://poj.org/problem?id=6308题目意思给你+8的时区的时间，问你uct的时间？解题思路模拟就可以了，如果转化成分钟相减再化成时间要注意负数。代码部分#include &amp;lt;iostream&amp;gt;#include &amp;lt;algorithm&amp;gt;#include &amp;lt;stdio.h&

2018-07-24 09:38:01 263

原创 HDU 6298 Maximum Multiple（思维）

【题目链接】 http://poj.org/problem?id=6298题目意思给定一个整数。问这个整数是否能等于自身3个因数的加和。如果能输出最大的3个因数乘积，不能则输出-1.解题思路要满足自身3个因数加和等本身只有3个因数相同和1:1:2的两种情况。否则就无法找出。代码部分#include &lt;iostream&gt;#include &l...

2018-07-24 09:02:11 200

原创 HDU 1465 不容易系列之一（错排）

【题目链接】 http://poj.org/problem?id=1465题目意思给定n个封信，问n封信都装错有多少种错误方式。解题思路错排公式：F（n）=（n-1）[F（n-1）+F（n-2）] 解释:假定A,B,C,D为已经排列的。当E加入时候就会出现两种情况让排列为错排。 1. A，B，C，D已经为错排，那么只要将E与其中任意一个（4种选择）互换就可以使排列为错...

2018-07-23 08:40:19 175

原创迟到的感想

省赛结束也一周了，由于状态问题一直拖着这篇感想。这是第二次去省赛，但是第一次比赛（第一次去观光）。对于比赛成绩拿了个银还是有些遗憾的，毕竟今年大佬少了总队伍人数多了。0.0! 说说最近心态吧。省赛前经历过天梯赛和蓝桥杯两个比赛也都比预期的差，如果说前面比赛还为自己找个借口，那么省赛也让全部的借口变成了笑话。一直觉的自己是个比较乐观的，善于调节情绪的。但发现以前的“乐观”“善于调节情绪”非...

2018-06-03 20:13:42 413

原创 POJ 3159 Candies（差分约束）

【题目链接】 http://poj.org/problem?id=3159题目意思一群小朋友分糖，但是不同小朋友乖巧程度不一样，所以分的糖不一样。但是小朋友A虽然认为自己不如小朋友B，但是他觉的差距只值C个糖。不然他要他要找校长（现在小孩真凶残，直接找校长了），问你为了区分不同小朋友的乖巧程度尽可能让区间大，问你最大是多少。解题思路最基础的差分约束，不用管图是否有负环是否...

2018-04-25 20:32:50 107

原创 POJ 1511 Invitation Cards（双向最短路）

【题目链接】 http://poj.org/problem?id=1511题目意思给n个点，m条有向边。问你从1到其他n-1各点的最短路和加上从n-1各点到1的最短路。解题思路因为是有向边而且一次终点在1，一次起点在1，所以只要跑一遍正的图在跑遍反的地图，总和就是要的答案。坑点在于数据比较大总和要用long long，邻接表开两个时间就会wa，要用优先队列优化。...

2018-04-25 19:02:34 222

原创 POJ 3169 Layout（差分约束）

【题目链接】 http://poj.org/problem?id=3169题目意思一群编号1~n牛排队。按编号排(多头牛可以站在同一位置)。由于不同牛关系不同，有ML对恋爱牛要求排的队伍距离不超过w，有MD对仇牛要求距离超过w。现在问你队伍最大长为多少？如果无法找到满足要求的安排输出-1，如果最长无法求输出-2。解题思路第一题的差分约束，差分利用最短路的缩点时候d[v] ...

2018-04-25 16:57:24 126

原创 HDU 4370 0 or 1（最短路djs）

【题目链接】 http://poj.org/problem?id=4370题目意思给你一个矩阵，让你找到一个由0和1组成的矩阵，满足 1.X12+X13+…X1n=1 2.X1n+X2n+…Xn-1n=1 3.∑Xki (1<=k<=n)=∑Xij (1<=j<=n).解题思路迷一样的题目意思。总的就是把矩阵看做图，那么条件1就可以看出节点1...

2018-04-24 16:46:23 146

原创 HDU 4725 The Shortest Path in Nya Graph （最短路djs+优先队列优化）

【题目链接】 http://poj.org/problem?id=4725题目意思题意说有n个节点，这些节点分布在n个平面上，两两相邻的平面直接的距离为c。而节点与节点也有m条边，距离为w。问你从节点1到n最短路。解题思路题意看了半天，才明白节点与面的关系。一开始觉的直接把面也当成节点来构图就可以了（面与面里的节点距离为0）。但是后来发现题目并没有说一个面就一个节点，当一...

2018-04-24 15:49:44 177

原创 POJ 3660 Cow Contest （最短路弗洛伊德）

【题目链接】 http://poj.org/problem?id=3660题目意思有一群等级从1到n的牛比赛，现在告诉你m次比赛结果A B（A大于B），问你能确定某牛等级的只数。解题思路某头牛能确定和其他n-1头牛的关系就能确定自己的等级。（只要确定几胜几负就可以了，当胜数加负数等于n-1，那么这只牛的等级一定为负数加1）。所以用弗洛伊德把两两关系求出。在判断有多只是...

2018-04-23 19:21:10 201

原创 POJ 1502 MPI Maelstrom（最短路）

【题目链接】 http://poj.org/problem?id=1502题目意思多个主机要通信，由于各种乱七八糟的原因任意两台主机的通信时间不一样，现在给你任意两台之间的通信时间（通信是双向的所以给的是矩阵的下三角）。通信同时进行问从一号主机开始最晚收到通信的主机时间。解题思路单源最短路，输入时处理下就可以了，其他都是模板。代码部分#include &...

2018-04-23 15:57:05 131

原创 POJ 3259 Wormholes （最短路BF）

【题目链接】 http://poj.org/problem?id=3259题目意思在一个农场出现了w个虫洞，经过虫洞会从u到v并且回到t秒前。场主给了m条路径和所花费的时间。现在农场主想知道在农村是否存在一个从v到u，然后经过虫洞从u回到v看到曾今的自己。解题思路最短路判断是否存在负环，把虫洞的时间改回负的跑一遍BF看是否存在负环就可以了。（从哪个点开始跑并不影响）...

2018-04-23 15:18:27 158

原创 POJ 2912 Rochambeau（并查集）

【题目链接】 http://poj.org/problem?id=2912题目意思一群人玩石头，剪刀，布；把这群人分成3组，分别只能出石头，剪刀，布。但是其中有个是裁判可以任意出。现在给你m组两两对决的结果，问是否能找到裁判，如果能输出裁判序号和在第几个对决结果出来时找到的。不能输出对应字符串。解题思路这题是在poj1182食物链上加个裁判形成的。所以只要遍历去除某一点有关的...

2018-04-17 08:32:41 611

原创 POJ 3268 Silver Cow Party (最短路)

【题目链接】 http://poj.org/problem?id=3268题目意思有n只牛，编号从1到n，现在k号家开party，所以牛都会去，当这些牛非常懒，他们想尽可能走短的路（去时加回来），现在路是有向路，问路程最远的一只牛的路程解题思路每只牛的路程都可以分成去时和回时。可以用spfa或迪杰斯特拉单源点循环跑，找最大的。弗洛伊德会超时。上面这虽然会过但是耗时大，只要...

2018-04-16 17:45:01 108

原创 POJ 1797 Heavy Transportation（spfa）

【题目链接】 http://poj.org/problem?id=1797题目意思你要把货物从1号街口运到n号街口，但是每条街道都有载重上限，问你货物最重可以选多少。解题思路和poj2253很像的一题，poj2253是找能到n的全部路线中找一条路线，每条路线任意两点最大值为路线的权。找到最小的一个权。而这条是任意两个的最小值为权，找最大的一个权。（有点绕看看测试样例应该明...

2018-04-16 15:59:34 151

原创 POJ 2253 Frogger （最短路）

【题目链接】 http://poj.org/problem?id=2253题目意思两只青蛙，一只想跳到另一只石子上，现在给定n个石子坐标（第一和第二为青蛙坐标）问青蛙最少跳多远才能不掉入水的情况到另一只青蛙石子上。解题思路用单源最短路完成，不过dis不在存储从起点到某点最短距离，而存储这条路劲中最大距离的一段。（这题输出%lf过不了要用%f坑死了，wa到o(╥﹏╥)）...

2018-04-16 14:13:19 113

原创 POJ 2387 Language: Til the Cows Come Home（spfa）

【题目链接】 http://poj.org/problem?id=2387题目意思她想从奶牛场尽快回去睡美容觉，问你最短路径是多少？（1为家，n为奶牛场）解题思路最短路模板题，数据不大用邻接矩阵或邻接表都可以。下面是spfa的代码代码部分#include <iostream>#include <algorithm>#inclu...

2018-04-16 09:02:04 147

原创 POJ 1458 Common Subsequence（最长公共子序列）

【题目链接】 http://poj.org/problem?id=1458题目意思给两个字符串，问最长公共子子序列。（模板题）解题思路给个带图的博客：https://blog.csdn.net/sr_19930829/article/details/14058959代码部分#include <iostream>#include <algori...

2018-04-13 15:51:32 114

原创 POJ 2492 A Bug's Life （并查集）

【题目链接】 http://poj.org/problem?id=2492题目意思给你一堆情侣的关系a和b。但是这些情侣关系可能冲突，也就是有同性恋的。现在问你给你n个人m个关系里面是否有同性恋（有则输出“Suspicious bugs found!”,没有输出“No suspicious bugs found!”），每个案例后面加个换行解题思路这题一开始就死扣带权值的并...

2018-04-12 20:30:15 104

空空如也

空空如也