- 博客(224)
- 资源 (2)
- 问答 (10)
- 收藏
- 关注
RSS订阅原创 POJ 3295 - 位运算 + 模拟 +递归
1.Question:本题是用枚举的思路来判断一个规定的逻辑表达式是不是永真式首先题目意思是最多不会有超过5个逻辑变量，有五种运算Definitions of K, A, N, C, and E w x Kwx Awx Nw Cwx Ewx 1 1 1 1
2016-12-04 16:47:49
970
1
原创 NYOJ 118 次小生成树
1.Question:描述南将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，南将军准备修路。现在已经知道哪些城市之间可以修路，如果修路，花费是多少。现在，军师小工已经找到了一种修路的方案，能够使各个城市都联通起来，而且花费最少。但是，南将军说，这个修路方案所拼成的图案很不吉利，想让小工计算一下是否存在另外一种方案
2016-12-03 14:38:23
824
原创 胜者树 败者树 K-路最佳归并树 高效外部排序
外部排序 外部排序和内部排序还是有非常的的不同的,我们的外部排序主要针对的优化目标也是不同的,这里我先从外部排序的物理基础开始进行讲解1.外存:外部存储设备,相对于我们的内部存储设备而言具有一些特点1.优点:永久存储能力,便携性,存储空间大2.缺点:访问速度相对于内存的访问速度来说极其低下(相差约5~6个数量级)因此对于外存来说,我们要遵守的基本操作原则就是:尽
2016-12-02 16:33:21
9136
1
原创 POJ 1062 - 昂贵的聘礼 - 经典题
1.Question:中文题不说什么了2.Solution:本题的难点有两个1.建图2.限制建图：首先，我们需要明确本图G是一个有向图，我们的顶点代表庙我们的物品的编号，图采用邻接矩阵存储，我们的图中的邻接矩阵中存储我们的便宜价格这样的话，我们每个点只要在限制条件下都可以找到1点，那么我们就取到达1点的最小值当作我们的答案限制：本体的限制说的很明
2016-11-30 17:57:26
915
原创 POJ 1860 - SPFA - 正权回路
1.Question:我们的城市有几个货币兑换点。让我们假设每一个点都只能兑换专门的两种货币。可以有几个点，专门从事相同货币兑换。每个点都有自己的汇率，外汇汇率的A到B是B的数量你1A。同时各交换点有一些佣金，你要为你的交换操作的总和。在来源货币中总是收取佣金。例如，如果你想换100美元到俄罗斯卢布兑换点，那里的汇率是29.75，而佣金是0.39，你会得到（100 - 0.39
2016-11-29 17:58:26
762
原创 POJ 2240 - SPFA - 正权环（最大路）
1.Question:输入n代表有n个国家之后的n行代表n个国家的名称输入m代表有向边的个数之后的代表我们国家货币之间的汇率现在求，是否存在一条回路是的我们的交换货币之后原本的货币量增多2.Solution:本题是标准的判断回路的问题，我们需要将最短路的标准思路转变一下，首先，本题我们需要找到的是正权回路不是负权回路，我们只需要改变一下松弛策略就好，我们只要将松
2016-11-29 09:22:01
959
原创 关于快速排序算法本质的重要说明 - 考试考了不会就不要怪我
说明，本文章的针对已经大致的理解了快速排序的同学双向扫描 VS 单向扫描我们都知道，快速排序算法存在两种实现机制，一种是单向扫描法，一种是优化后的双向扫描法单向扫描：首先，我们需要知道，单向扫描是最正规的《算法导论》上给出的基本实现的过程伪代码如下data - array wait to sortn - the count of the arrayi - head po
2016-11-28 21:47:26
1514
1
原创 Shell-Sort 增量排序算法 总结
1.Shell - Sort希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。我们都知道直接插入排序算法是相对来说比较低效的算法，但是正是插入排序算法的特性决定了我们在数据量小的时候，数据基本有序的时候的排序效果往往比一些高级排序算法构架行之有效，更加快速在我们开始了解Shell-Sor
2016-11-27 23:49:19
3009
原创 NYOJ 99 - 欧拉图 单词拼接
1.Question:描述给你一些单词，请你判断能否把它们首尾串起来串成一串。前一个单词的结尾应该与下一个单词的道字母相同。如alohadogarachnidgophertigerrat 可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
2016-11-26 16:35:51
651
原创 POJ 3259 - SPFA负权回路 < Floyed
1.Question:POJ 3259农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发
2016-11-26 11:54:15
618
原创 POJ 1847 - Shortest Path Dijstra>SPFA
1.Question：又一个火车网络系统输入第一行:n,a,b分别代表网络中 节点的个数，初始节点，终止节点接下来n行分别代表第i个节点的有向边的终点每一行第一个代表的是有向边的个数，之后的第一个有向边的权值是0，之后的权值都是1现在请给出从a到b的最短的路径权值和2.Solution：本题是标准的最短路径的问题并且数据量比较水，所以说，我们的很多的最短路径
2016-11-24 14:42:00
503
原创 NYOJ - 42 - 并查集+半欧拉图
1.Question:描述 zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。规定，所有的边都只能画一次，不能重复画。 输入第一行只有一个正整数N(N每组测试数据的第一行有两个正整数P,Q(P随后的Q行，每行有两个正整数A,B(0输出如果存在符合条件的连线，则输出"Yes",如果不存在符合条件的连线，输
2016-11-23 23:15:51
403
原创 POJ 3268 - Shortest Path Dijstra+ SPFA
1.Question：题意：输入第一行n,m,t三个数代表的含义分别是图中的n个点，m条有向边，t为初始定点之后的m行代表我们图中的m条有向边在题目要求从t初始点到所有的点点额单源最短路径和将所有的有向边反向之后，我们再求一次单源最短路径求两次的最短路径之和的最大值2.Solution：单元最短路径问题本题因为牵扯到有向边的反向问题，所以我们最好选用矩阵的数据结构来
2016-11-23 19:54:04
408
原创 AVL - 自平衡二叉树 - 详解
1.AVL说到AVL，我们就必须先要了解一下BSTLantian的BST总结在了解了有关BST的性质之后，我们现在就明白了因为在我们的插入的节点有序的情况下，我们的BST会出现偏树的情况，这会导致我们的ASL（平均查找长度）大大增加从而降低我们的查找效率因此，我们就需要一种BST的优化版本取克服这种输入造成的弊端（现在证明，在平均情况下，出现偏树的概率大致在45.6%），所以说，我
2016-11-23 16:26:18
1578
原创 POJ 2253 - 最短路变形 SPFA+Dijstra
1.Question:题意:题意：给出青蛙A,B和若干石头的坐标，现青蛙A想到青蛙B那，A可通过任意石头到达B, 问从A到B多条路径中的 最长边 中的 最短距离2.Solution:分析：这题是最短路的变形，以前求的是路径总长的最小值，而此题是通路中最长边的最小值，每条边的权值可以通过坐标算出，因为是单源起点，直接用SPFA算法或dijkstra算法就
2016-11-22 19:50:11
512
原创 POJ 1502 - Shortest Path - SPFA+Dijstra
1.Question:题意：MPI微处理器求解1号MPI到其他的所有的MPI的最短的路径中的最长的一条Shortest Path版题2.Solution:本题我用了两种思路去求解SPFA+Dijstra在同为邻接表的情况下，运行的时间效率相当但是，我通过左本题发现，我对SPFA的算法的本质理解存在有很大的漏洞3.Code:SPFA/*Problem:
2016-11-21 10:47:02
553
原创 Euler Graph - 欧拉图 详解
1.从哥尼斯堡七桥问题到欧拉图哥尼斯堡七桥问题：18世纪中叶在欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的和河中有两个小岛，现在四块陆地有七座桥连接，引入问题，如何规划线路才能保证我们可以走过所有的边但是却保证不会重复呢这就是著名的哥尼斯堡七桥问题，现在通过图论证明哥尼斯堡问题是不存在解的，第一个发表论文证明了这个事实的人就是欧拉，该论文也是目前为止发现的最早的关于图论的论文，当然，这种问
2016-11-19 19:18:34
19314
2
原创 POJ 1287 MST Prim+Krustral
1.Code:Prim：/*Problem: 1287 User: lantianheyeqiMemory: 4132K Time: 63MSLanguage: C++ Result: Accepted*/#include"iostream"#include"cstdio"#include"cstring"#include"cstdlib"#define N 100
2016-11-17 16:23:03
493
原创 POJ 2349 MST Prim
1.Question:抽象概括题意：现在给你一个些点的坐标，每个坐标都是正整数，现在每个点之间都有一个连边（稠密图）现在求最小生成树MST的第n-s/n-1条边的长度，具体选哪个，我们根据s代销来判断，在程序中我已经写明了2.Solution:标准的稠密图，我们最好用Prim，如果用Krustral的话，最坏的情况500*500的边，很容易超时3.Code:#inclu
2016-11-16 20:00:25
462
2
原创 DAG - AOV - AOE - CPM - Topological-Sort 详解
1.DAG(Directed acycline graph)DAG图，又称有向无环图，简称为DAG，DAG是相对更像是有向树一样的数据结构，用处十分的广泛1.表达式树：DAG可以模拟表达式树，按照数据结构老师的话来说，在操作系统方面的用处更加的广泛2.检查图的环路：我们都知道检查一个无向图是否存在回路是非常的简单的，我们只需要DFS遍历一遍就能判断出来但是我们检查一个有向图
2016-11-16 12:17:38
2022
原创 POJ 1251 MST Krustral
1.Question:题意:题目中说明了是边数不会超过75，可见是稀疏图，我们直接Krustral 0MS水过来测模板了2.Solution:本题唯一的难点在于理解题意，和图的构建没什么难的3.Code:#include"iostream"#include"cstdio"#include"cstring"#include"algorithm"using n
2016-11-15 08:46:10
453
原创 POJ 3625 - MST
1.Question:题意：输入：n,mn代表已经点个数，m表示有多少条边已经连接成功本题是一个稠密图，每两个点之间都有边相连之后的输入的代表两个点之间有连边输出：最小的需求，本题是一个稠密图2.Solution:因为是稠密图，本题的Krustral没有Prim快本题是一个Prim的版题，但是不知道为什么，可能是精度的问题，导致的已知在WA之后莫
2016-11-14 11:18:34
303
原创 POJ 1861 - MST - Krustral
1.Question:输入：第一行两个数字，第一个n代表是点数，第二个m代表边数之后的m行代表有m个边，前两个代表两个点，第三个数字代表权重输出：MST中最大的边边的个数（n-1）将边集列出来2.Solution:标准的套模板，1861的题目的标准样例有一些问题，但是不应向我们做题，毕竟是Special Judge3.Code:#include"iost
2016-11-12 21:41:33
411
原创 正则表达式 详解
1.作用：搜索和替换——正则表达式的作用2.匹配单个字符：正则表达式可以包含纯文本当然，这样用正则表达式也是一种浪费正则表达式字母大小写敏感匹配任意字符：.元字符可以匹配任意的 一个 字符我们有时候在文本中还需要去匹配字符.这时候我们的正则表达式中的元字符.已经有了实际的含义，我们就必须对模式中的.进行转义这时候我们利用元字符\堆元字符.进行转义，这时候的正
2016-11-12 19:06:45
701
原创 POJ 2531 - DFS - 经典
1.Question:题意：有一个无向图，现在，我们需要将无向图进行划分，是的，每两个点之间都有连边，并且两边集合的点之间边有权值，集合内的点之间没有权值，现在求最大的情况是多少2.Solution:真的是一道非常新颖的DFS的思路，我们需要做的就是穷尽所有的可能情况1.我们首先假设，所有的点都在0集合2.我们穷举的情况是，所有的点在0,1之间的分布3.在DFS中，我们
2016-11-11 09:28:29
397
原创 Leetcode 3 - 最大不重复子串
1.Question:题意：有一个字符串，现在让我们求出最大的不重复的连续的子串的长度Examples:Given "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given
2016-11-10 15:02:44
5275
原创 POJ 3087 - STL(map)+滚动数组
1.Question:目的：通过本题熟悉C++，STL标准模板库中的map强大容器的基本操作题意：Shuffle游戏输入：第一次输入的t代表数据的测试用例个数之后的c代表我们玩的牌的每组牌的牌数(0之后两行代表我们的两座拍的顺序，顺序输入时从底向上的（从左到右）最后一行输入代表我们要活的的最终的状态，现在问我们进过多少次操作可以获得我们的最终状态，如果我们可以获得最
2016-11-10 13:24:01
361
原创 POJ 3414 - Easy BFS - 六入口倒水问题
1.Question:题目描述：有两个杯子，a，b，我们现在给定一个数据c现在有这么三种操作：FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;DROP(i) empty the pot i to the drain;POUR(i,j) pour from pot i to pot j; after
2016-11-09 12:07:19
378
原创 LeetCode 1 - 哈希
1.Question:给你一个字符串序列，再给你一个指定的数字的大小，现在询问你有没有尽可能快的思路去找到两个数的和满足这个目标的数本题的原型大致是这样的，我们给你一个有序的数列，现在要你在有序的序列中去找两个数之和满足一个条件在一个有序的数列中，找到这样的要求的两个数是十分的简单的我们大致的思路就是头指针，尾指针，然后不断的向中间移动，比预计的数字大的话，我们就西安移动右指针缩小
2016-11-08 17:35:24
453
原创 Leetcode 2 - Add Two Numbers
1.Question:2. Add Two Numbers QuestionEditorial Solution My SubmissionsTotal Accepted: 206533Total Submissions: 804547Difficulty: MediumContributors: AdminY
2016-11-08 17:25:04
517
原创 POJ 3083 - 变向DFS + BFS
1.Question:本题是一道非常好的搜索题，号不是好在本题混合了深搜和广搜，而是好在了本题的新的思路首先，题意：有一个迷宫，我们现在要求出在各种限制下的从S走到E的步数首先题目限制了一定有解存在1.我们现在定义初始方向，题目中明确说明了（我没有看到，半天没有理解题意），我们定义S的状态只有这么几种情况S不会出现在地图的中间，S不会出现在地图的四个角落,S只会在地
2016-11-08 13:46:23
417
原创 POJ 3126 - 筛素数+BFS
1.Question:输入：1.n代表测试用例的个数2.之后的n行，每行有两个数字，都是四位素数，现在让我输出最少的操作次数是的从第一个素数变换成第二个素数操作定义：我们每次允许改变四位数的的一个位的数字，不能不改变，并且改变数字后的新的四位数也必须是素数，这里的前卫上的数字不允许改变成02.Solution:标准的BFS枚举思路，但是这里我们对于素数的判定，可
2016-11-07 08:38:49
401
原创 GCD Extends_GCD 欧几里得算法+扩展欧几里得算法详解
1.欧几里得算法：我们从小学开始老师都会让我们求解一一种问题，叫做最大公约数，这里的最大公约数就叫做GCD当然求解最大公约数的算法也是非常的重要，我们在这里就引入欧几里得的算法，也就是著名的辗转相除法首先给出定义：GCD(a,b)=GCD(b,a%b)在这里有的人会问a，b到底哪个大才能使对的，其实在这里我们的a，b是没有大小之分的，要是硬说影响的话，是有那么一点影响，但是无关
2016-11-05 21:00:55
1080
原创 Miller-Rabin概率素数测试算法
本文首先鸣谢以下资料文章： 资料1 资料2 资料3 下面我们开始正文，从源头开始真正的梳理一下素数测试1.素数我们都知道，素数在当今的数论中占有非常重要的地位，主要原因就是素数最根本的性质——除了1，和自身以外，不会被任何一个数整除 并且，素数现在在我们的日常生活中伴有非常重要的地位，这一点的其一主要原因就是素数已经是密码学中最重要的一点，我们当今的密码学常常要涉及到利用超大素数作为我们的
2016-11-05 16:37:23
12047
原创 快速幂取模算法详解
1.大数模幂运算的缺陷：快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的，在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的，在整个计算过程中最麻烦的就是我们的5^1003这个过程缺点1：在我们在之后计算指数的过程中，计算的数字不都拿得增大，非常的占用我们的计算资源（主要是时间，还有空间）缺点2：我们计算的中间过程数字大的恐怖，我们现有的计算机
2016-11-05 10:40:41
43984
14
原创 POJ 1840 - Hash
1.Question:题意：本题中有一个五元三次方程，现在让我们求解出系数都在-50-50，未知元的范围是-50-50的所有的解的个数，不计含0的解PS：首先，我们首先要知道，为了简化我们的操作，题目已经限定了系数和解得的取值范围，并且解是 整数 2.Solution:首先，对于我们的朴素的算法的话，我们需要对所有的情况都进行枚举，中国需要我们枚举50^5,很显然，这种算法的思
2016-11-04 17:07:33
460
原创 NYOJ - 138 节约内存 哈希
1.Question:在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，还有一个空箱子，现在有两种动作：一种是"ADD"，表示向空箱子里放m(0<m<=100)个球，另一种是"QUERY”，表示说出M(0<M<=100)个随机整数ki(0<=ki<=100000100),分别判断编号为ki 的球是否在这个空箱子中
2016-11-04 12:46:29
483
原创 POJ 3274 - 数组 + 哈希
1.Question:2.Solution:首先我们通过范例来了解一下题意是什么：7 31 1 11 1 00 1 00 0 11 0 00 1 0如代码所示，我们k代表的是二进制的位数，n代表的是奶牛个数注意这种排列是题目要求的唯一的，我们不能改动最后，我们开始转化问题首先，我们想要快速的求出差值最好的方法就是就是对数组从头到尾进行累加（这种方法也
2016-11-03 16:08:11
331
原创 快排光芒下被忽视的Partition函数
1.前言:看到这篇标题，没有学过快排的人自然是不知道Partition函数的意思和作用，这里附上学习的连接Lantian的快排总结我们现在都是被快排蒙蔽了双眼，没有意识到快最核心的划分函数Partition,当然Partition函数也就不止于快排这里，本文就从多方面来为展示Partition函数的本质和扩展作用2.快排中的Partition及其优化：在算法导论中我们对Partit
2016-11-02 19:33:53
3722
原创 Leetcode - 75. Sort Colors - Dutch national flag problem - Partition
1.Question:Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will
2016-11-02 18:43:29
745
从零开始学SBT
2016-08-18
关于python迭代器的问题
2017-02-10
关于python迭代器的问题
2017-02-10
关于floyed算法实现的问题
2016-11-26
关于RSA的一些问题，急求解答
2016-11-06
关于POJ 2503 ELFhash WA的问题
2016-10-30
求解5050问题的解法为什么递归返回不去了
2016-08-25
关于java swing的一点问题
2016-07-11
关于c++文件读写的一个问题
2016-06-03
C++的成员函数友元的问题
2016-05-31
链表和指针的疑惑问题
2016-05-25
TA创建的收藏夹 TA关注的收藏夹
TA关注的人