111111用户昵称不存在00000-CSDN博客

原创 PATL3-003. 社交集群-并查集

L3-003. 社交集群题目：在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。输入格式：输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好： Ki: hi[1] hi[2

2017-03-08 17:04:43 782

原创 PATL2-010. 排座位-并查集

L2-010. 排座位题目：输入第一行给出3个正整数：N（<= 100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：“宾客1 宾客2 关系”，其中“关系”为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。这里假设朋友的朋友

2017-03-08 15:38:58 667

原创 PATL2-007. 家庭房产-并查集

L2-007. 家庭房产题目：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。输入格式：输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：编号父母 k 孩子1 … 孩子k 房产套数总面积其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这

2017-03-07 23:34:27 2641

原创 PATL2-004. 这是二叉搜索树吗？

L2-004. 这是二叉搜索树吗？一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索

2017-03-01 16:52:00 1002

原创 PATL3-010. 是否完全二叉搜索树

L3-010. 是否完全二叉搜索树将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。通过线段树的构建方法对所有点建二叉搜索树，则可在构建了一棵无键值节点均为0的完全二叉树。之后通过层次遍历判断这棵树在遍历完这n个节点的过程中是否出现为空的叶子节点判断是否是完全二叉搜索树。#include

2017-02-28 23:31:47 729

原创 L2-011. 玩转二叉树

PATL2-011. 玩转二叉树给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。。题解：根据中序遍历（左中右），前序遍历（中左右）；由每次前序遍历区间的第一一个节点为跟节点，在中序遍历中找到这个节点即可将树的左子树和右子树区分，通过递归不断还原整棵树。

2017-02-28 20:17:58 470

原创 PATL2-006.树的遍历

PATL2-006.树的遍历给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。题解：根据中序遍历（左中右），后序遍历（左右中）；由每次后续遍历区间的最后一个节点为跟节点，在中序遍历中找到这个节点即可将树的左子树和右子树区分，通过递归不断还原整棵树。#include <stdio.h>#include <iostream>#

2017-02-28 20:10:03 1192

原创 LightOJ1029->Prime

LightOJ1029->Prime题意：求一棵最大生成树和最小生成树。代码：#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>using namespace std ;#define INF 0x3f3f3f3f#define MAX 110int n ;bool visi

2016-10-09 23:05:10 434

原创 LightOJ1040->最小生成树

LightOJ1040->最小生成树题意：已知一些房间之间连有线缆，求可以让这些房间连通的前提下，最多能去掉多长的线缆。题解：记录所有线缆长度，求一棵最小生成树，用总长减去最小生成树的权值和就是答案。#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>using namespa

2016-10-09 23:02:18 428

原创 UVALive6833->数据结构

UVALive6833->数据结构题意：给出一个式子，只包含乘法和加法，判断这个式子按照从左向右的顺序计算和按照乘法优先的次序计算的结果是否为所需要的答案。题解；顺序计算只需要从左向右依次处理即可，但是要按照运算符优先级计算时，需要先把中缀表达式转变成后缀表达式之后才能计算。代码：#include <stdio.h>#include <iostream>#include <str

2016-10-07 22:04:41 334

原创 UVALive6834->贪心

UVALive6834->贪心题意：某人逛商场，在进一家店A之前必须要先去另一家店B，现在给出商场的总长度，以及所有的进店的先后次序，求从商场进去逛完所有必须店铺到出去的最小耗时。题解：把每个有访问先后次序的店铺都等价成一个区间，如果区间有相交，采取贪心策略，可以先访问完所有优先级高的店铺再回过头来访问优先级较低的店铺，这样可以减小耗时。然后只要区间有连接就把这些区间进行合并，最后求访

2016-10-07 21:57:41 349

原创 HDU4791->贪心&&二分优化

HDU4791->贪心&&二分优化题意：有一家打印店，打印超过一定分数后每份的单价就会降低，你需要打印一些文件，你可以打印敲好的份数或者是多打印一些废纸以凑得更低的价格，问打印这些文件所需的最小花费。题解：采用贪心策略，从最单价低价开始计算，直到计算到数量的区间正好包含所需印刷的产品数量。但是单纯采取贪心策略遍历整个价格数组会TLE，所以需要二分优化，先二分找到包含当前价格的价

2016-10-07 21:47:19 395

原创 LightOJ1190->判断一个点是不是在一个任意多边形内

算法介绍： http://blog.csdn.net/hjh2005/article/details/9246967代码：#include <stdio.h>#include <math.h>#define max(X,Y) ((X)>(Y) ? (X) : (Y))#define min(X,Y) ((X)<(Y) ? (X) : (Y))const int INF=0x7fffffff;

2016-09-26 23:17:04 409

原创 LightOJ1292->求最多共线点数

LightOJ1292->计算几何题意：给出平面上n个点，要求最多有多少个点能共线。题解：使用map存储每个点相对于原点的不同斜率上对应的点的个数，最后输出最大值即可。代码：#include <stdio.h>#include <iostream>#include <map>using namespace std ;int GCD(int a , int b) {return

2016-09-26 23:03:17 861

原创 HDU5884->贪心

HDU5884->贪心（二分+单调队列）题意： n个有序序列的归并排序。每次可以选择不超过k个序列进行合并,合并代价为这些序列的权值和（类似果子合并）.总的合并代价不能超过T, 问k最小是多少题解：贪心算法求解。二分答案k，k可以从2取到n，由于每次将k个元素归并成了一个元素，也就是说归并一次序列长度减少了（k-1）,最后要把n个序列归并成1个序列，相当于一共要减少的长度为（n-

2016-09-20 18:54:29 486

原创 LightOJ1285->极角排序

LightOJ1285->极角排序题意：给出平面上的N个点，每个点按照给出顺序编号，问能否只用一条线连接所有的点构成一个多边形，如果可以，则以最左下角的点为起点，逆时针输出多边形边上这些点的编号，否则输出impossible。题解：其实只要点的个数大于等于3并且这些点不都在同一条直线上，就能被连出一个多边形。因此需要进行极角排序。由于极角排序时是角度相同时横纵坐标从小到大，所以

2016-09-12 23:31:09 361

原创 LightOJ1203->求凸包最小内角角度

LightOJ1203题意：被转化后的问题其实就是求凸包最小的内角角度。题解：构造一个凸包，通过余弦定理遍历所有内角，求出最小角度。代码：#include <stdio.h>#include <iostream>#include <cmath>#include <algorithm>#include <float.h>using namespace std ;#defin

2016-09-07 23:27:00 455

原创旋转卡壳->POJ2079

旋转卡壳：1.旋转卡壳求凸包直径：如上图：我们定起始点为A，首先从A点开始你顺时针找到凸包上距离A点最大距离的E点；由于A到F的距离小于A到E的距离，此时我们旋转线的左端点到B点，再去计算B到F的距离，之后旋转线段的右端点，发现BG的距离小于BF，此继续旋转左端点到下一个顶点。每次旋转卡壳的操作就是由一个固定的左端点，和旋转方向固定的右端点，求出其到一个右端点的

2016-09-03 17:56:05 395

原创 POJ2187->凸包

POJ2187->凸包题意：给出平面上n个点，求出这些点中距离最大的两个点。题解：如果逐个枚举，时间复杂度将会相当高，不能满足题目要求。可以构建一个凸包，再在凸包中枚举各个顶点之间的距离求最大值。代码：#include <stdio.h>#include <iostream>#include <cmath>#include <algorithm>#include <f

2016-08-30 23:38:52 317

原创凸包Graham扫描法->HDU3847

Graham扫描法求凸包凸包定义：点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。 Graham扫描法：首先，找到所有点中最左边的(y坐标最小的)，如果y坐标相同，找x坐标最小的. 以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并按照极角

2016-08-30 00:29:27 589

原创 HDU1730->Nim博弈

HDU1730->Nim博弈题意：游戏在一个n行m列（1 ≤ n ≤ 1000且2 ≤ m ≤ 100）的棋盘上进行，每行有一个黑子（黑方）和一个白子（白方）。执黑的一方先行，每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上，当然这过程中不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，移动最后一步的玩家获胜。判断先手的胜负情况。题解：等效于nim博弈。

2016-08-29 15:34:03 518

原创 HDU1536->SG函数

HDU1536->SG函数题意：给出n堆石子，每次只能按照规定的取石子个数取，输出先手的胜负情况。题解：递归求出sg函数就能解决问题。代码：#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>using namespace std ;int s[110] , sg[10010

2016-08-29 14:52:11 407

原创 HDU3032->SG函数

HDU3032->SG函数题意：两个人玩游戏，有n堆石子，每堆个数不等，可以进行的操作是从任一堆中取任意颗石子，或者把这堆石子分成两堆。给出一个初始的局面，判断先手胜还是后手胜。题解： sg(n)代表从当前状态到游戏结束最多需要多少步当有n堆石子时，游戏相当于一个组合博弈，当前的sg值就是每堆石子的sg值异或的结果。对于任意的一个 Anti-SG 游戏，如果我们规定当局面中所

2016-08-28 18:27:57 573

原创 HDU1700->向量旋转

HDU1700->向量旋转题意：一个圆的圆心在（0,0），已知圆上一点，求另外两点使得这三点构成的圆内接三角形周长最大。题解：圆的内接三角形中，周长最大的为正三角形。已知一点即知道了圆的半径，和一个圆心与该点构成的向量，旋转这个向量即可得到另外两个点。代码：#include <stdio.h>#include <iostream>#include <cmath>usin

2016-08-27 23:40:30 527

原创 POJ1106->叉积判断点在直线的左右

POJ1106->叉积判断点在直线的左右题意：给定平面上一些点的坐标，有一个半径固定，圆心固定且可以旋转的半圆形平面，求这个平面能覆盖到的最大点的数量。题解：由于圆心半径一定，所以有效的点的坐标即是在这个圆形区域内的点的坐标，可以开个数组记录一下，之后可以通过枚举圆心和这些有效点构成的直线，并通过叉乘来统计每次在这条直线左侧的点的数量来更新答案。代码：#include <stdio.

2016-08-27 23:33:13 1762

原创分治法求两点间最短距离->HDU5721

分治法求最近点对的距离：主要思想就是先把n个点按x坐标排序，然后求左边n/2个和右边n/2个的最近距离，最后合并。合并过程：首先，假设点是n个，编号为1到n。我们要分治求，则找一个中间的编号m，先求出1到m点的最近距离设为d1，还有m+1到n的最近距离设为d2。这里的点需要按x坐标的顺序排好，并且假设这些点中，没有2点在同一个位置。（若有，则直接最小距离为0了）。然后，令d为d1,

2016-08-27 00:25:44 4561

原创 POJ2653->判断线段相交

POJ2653->判断线段相交题意：有一些线段，按顺序给出，后给出的线段可能会覆盖住先给出的线段，求这些线段中最后没有被覆盖住的线段的编号。题解：一次输入所有线段后，枚举编号1-n,用跨立实验去验证每条线段有没有被后面的线段覆盖，一旦查询到有编号大于它的线段跨立它，则跳出当前循环。代码：#include <stdio.h>#include <iostream>#include <

2016-08-27 00:06:13 545

原创 POJ2318->叉积判断点在线段的左右

POJ2318->计算几何题意：已知n条线段把一个区域分成了n+1部分，给出一些点的坐标，求每个小区域中有多少个点。题解：利用叉积，线段两个端点为p1p2，记玩具坐标为p0，那么如果(p0p1 X p0p2) 叉积是小于0，那么就是在线段的左边，否则右边。枚举即可，也能用二分优化。代码：#include <stdio.h>#include <iostream>#inclu

2016-08-25 18:21:38 752

原创跨立实验判断线段是否相交->POJ3304

在二维坐标下介绍一些定义：点：A（x1，y1），B（x2，y2）向量：向量AB=（ x2 - x1 , y2 - y1 ）= ( x , y ); 向量的模 |AB| = sqrt ( x*x+y*y );向量的点积：向量叉积结果为 x1*x2 + y1*y2。点积的结果是一个数值。点积的集合意义：我们以向量 a 向向量 b 做垂线，则 | a | * cos（a,b）为 a

2016-08-25 00:05:22 656

原创 LCA在线算法ST&&DFS->POJ1330&&POJ1470

LCA在线算法ST&&DFS：在线算法DFS+ST描述(思想是：将树看成一个无向图，u和v的公共祖先一定在u与v之间的最短路径上)：（1）DFS：从树T的根开始，进行深度优先遍历（将树T看成一个无向图），并记录下每次到达的顶点。第一个的结点是root(T)，每经过一条边都记录它的端点。由于每条边恰好经过2次，因此一共记录了2n-1个结点，用E[1, … , 2n-1]来表示。（2）计算R：用R[i]

2016-08-23 16:06:11 528

原创 Nim博弈->HDU1907

Nim博弈->HDU1907Nim博弈介绍：1.有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3

2016-08-22 21:36:18 495

原创 UVALive6908->线性DP

POJ2096->概率DP题意：一个软件有s个子系统，会产生n种bug。某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。 PS：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，属于某种类型的概率是1/n。题解：

2016-08-22 14:21:26 344

原创威佐夫博弈->HDU1527

威佐夫博弈->HDU1527威佐夫博弈（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（

2016-08-21 12:59:49 332

原创 HDU1525->博弈论

HDU1525->博弈论题意：两个人玩游戏，给出两个数字，每个人只能用大的数字减去小的数字的任意正整数倍，先把一个数减到0的人获胜，问谁最后获胜。题解：记a > b, 如果输入中a和b中有一个是0，则先手直接获胜。否则：如果a%b == 0 , 则此时正在操作的人可以直接获胜；如果a/b>=2,则此时正在玩游戏的人可以通过自己的操作决定必胜和必败。

2016-08-20 17:07:01 529

原创 HDU5091->线段树维护区间覆盖次数&&扫描线

HDU5091->线段树维护区间覆盖次数&&扫描线题意：一个平面上有一些点，给出这些点的坐标，求用一个宽为w高为h的格子最多能包含到多少个点题解：用一根平行于y轴的扫描线维护沿x轴方向的宽度，而沿y轴方向的点的个数的计算则可以等价为求一个区间内线段覆盖的最多次数。由于已经给出高度h，所以每个点都可以看成是以这个点的y坐标为起始，长度为h的一条线段。这里扫描线的运用，就是

2016-08-20 12:14:45 958

原创 UVA10440->贪心||DP

UVA10440->贪心||DP题意：一些摆渡船运送汽车，给出往返需要的时间和每辆汽车到渡口的时间，每次最多能装几辆车，求所有汽车都到达对岸的最少次数和最短时间。题解：毋庸置疑，所有汽车都到达对岸的最少次数就是汽车总数除以船每次能装的汽车的最多数量，然后向上取整。时间的计算，每辆车可以是以自己的到达时间为起始时间来计算摆渡船这趟往返后到达渡口的时间；若是运输前一趟汽车后摆渡

2016-08-19 10:09:32 484

原创 HDU1024->线性DP

HDU1024->线性DP题意：求一个有n个元素的序列，划分出m个子序列，求这m个子序列的最大和。题解： dp[i][j]代表前j个数选i个子序列，能得到的最大和。决策为：第j个数，是在第包含在第i组里面，还是自己独立成组。状态转移方程： dp[i][j]=max(dp[i][j-1]+num[j],dp[i-1][k]+num[j]) ; 由于采用二维数组，

2016-08-18 12:44:22 311

原创 POJ2096->概率DP

POJ2096->概率DP题意：一个软件有s个子系统，会产生n种bug。某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。 PS：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，属于某种类型的概率是1/n。题解：

2016-08-18 00:10:48 440

原创 HYSBZ1206->数位DP

HYSBZ1206->数位DP题意：求一个区间中有多少个数其相邻两位之间的差值大于等于2，不含前导0，只有一位的数字也都算作符合规则。题解：典型的数位DP的题目。 dp[i][j]代表第i位为j时，符合要求的数字有多少个。先初始化，从第1位到第11位依次统计，状态转移方程为： dp[i][j] += dp[i-1][k] (k - j >= 2 || j - k >

2016-08-17 17:18:28 389

原创 HDU5094->BFS&&状态压缩

HDU5094->BFS&&状态压缩题意：有一个迷宫，每个格子有四个方向，但这四个方向可能是门，可能是墙，也可能是通路，有些格子里有钥匙，每种钥匙只能开对应品种的门，求从（1,1）到（n,m）所花费的最少时间题解：相比最基本的迷宫，这个题多了许多状态，因此我们在记录迷宫信息时不能再简单的只记录一张图，而是要记录每个格子的四个方向的状态以及每个格子有没有钥匙，有哪些钥匙。在记录钥

2016-08-17 15:40:47 613

LightFaceNet Model

Win32MFC计算器

空空如也