ITeye博客

成长中的菜鸟

ren_hui · 共 21 篇文章

单调栈的一些应用

1、何为单调栈:顾名思义,栈中的元素是按照某种方式排列,但是必须是单调的,如果某元素破坏了栈的单调性,就弹出栈的元素,直到该元素满足栈的单调性为止。 2、用途:可以很方便的求出某元素左边或右边第一个比其大或者小的元素,且时间复杂度O(n); hm 与 zx系列故事题目链接 训练赛的时候没能够做出来,自己当时根本就不知到什么是单调栈,更别说应用了,平时应该多多的积累一些知识点,遇到不会的赶紧去学习,感觉知识单单钻一个方向不行。 #include<cstdio> #include<iostream> #include<stack> #define maxn 1000005 using names…

2013-12-01 22:09 · 数据结构 · 评论(0)

zoj 1655 Transport Goods (Dijkstra)

ZOJ Problem Set - 1655 Transport Goods 结题报告: 一开始用的是从首都向其他城市搜索,记录路径,然后向回搜索,但是出现了wa。 后来搜了一下结题报告,别人都是直接搜索,使费用率最大,试了一下,这样做还是wa 最后看了 小媛 的,才知道是可能同时出现费用率不同的同一条路,这是后我们当然要选择费用率较小的 感觉自己第一遍记录路径代码可以过!,但是细节没有注意 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 105 #define …

2013-11-17 22:26 · 图论 · zoj 1655 最短路 · 评论(0)

poj 1679 The Unique MST (最小生成树是否唯一 )

题目链接: poj 1679 The Unique MST 解题报告:最小生成树是否唯一判断方法 (1)图中每条边,扫描其他边,如果存在权值相同的边,则对其边标记 (2)用kruskal或prim算法求最小生成树的权值 (3)得到最小生成树,如果该最小生成树不包含标记的边,则最小生成树唯一,如果包含了标记的边,则 依次去掉 标记的边,再求最小生成树,如果求得的最小生成树与原最小生成树的权值相同,则最小生成树不唯一 code: #include<cstdio> #include<cstring> #include<algorithm> #define maxn 105 #define INF …

2013-11-10 20:27 · 图论 · 评论(0)

zoj 2048 / poj 1751 Highways prim算法 (无限wa注意)

题目链接 : http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1048 解题报告:在zoj上wa了多次还是过不了,感觉很郁闷,就去poj上提交,结果poj可以过。 代码其实很快就敲出来了,只是一直wa改了很久也没有发现错误,刚开始我还以为是已经完全联通的城市需要输出一个空行呢,结果只是两组数据之间夹一个空行,zoj上顺利通过,希望wa的可以借鉴一下。 代码: #include<cstdio> #include<cstring> #include<cmath> #define maxn 800 #define INF 0x7…

2013-11-07 21:17 · 图论 · 评论(0)

Problem - 105A - Codeforces A.(精度问题)

链接: http://codeforces.com/problemset/problem/105/A 解题思路:题目要求输出单词必须按字典序输出,用STL中的map容器会比较简单 map容器实质上是一个二叉查找树,它可以做插入、查找、查询等操作。时间复杂度log(n); n为map中元素的个数,再用迭代器去访问map中的元素就是按照字典序进行访问的 map<x1,x2>it1; x1为键,x2为值,键是用来索引的,值就是其存储的信息 此题应注意的是 精度问题 例如: 1 1 0.3 aaa 1000 b 输出为: aaa 299 b 0 说明double存储数据的时候可能不是300.000.…

2013-11-05 22:11 · Codeforces · 评论(0)

poj 2421 Constructing Roads (kruskal) runtime error

链接: http://poj.org/problem?id=2421 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define maxn 210 #define maxm (210*210) using namespace std; struct node { int u, v; int w; }edge[maxm]; int n, m,Q; int parent[maxn]; bool cmp(const node &a,const node &b) { return a.w < b.…

2013-10-30 21:51 · 图论 · 评论(0)

ZOJ 2193 Window Pains AOV网络

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1193 结题报告:本次代码写的比较乱,但是感觉收获还是不小的 第一次完全靠自己手写邻接表,虽然调了两天,但是最终还是搞出来了 首先4*4方格中每个方格可能出现的数字 1 1,2 2,3 3 1,4 1,2,4,5 2,3,5,6 3 ,6 4,7 4,5,7,8 5,6,8,9 6,9 7 7,8 8,9 9 输入的数字就是位于最上面的数字,然后与下面的数字都有关系,这种关系用邻接表存储 最后用拓扑排序,如果不存在环的话,就证明系统没有崩溃 代码: #inclu…

2013-10-15 19:43 · 数据结构 · 图论 · 评论(0)

poj 2935 (bfs+路径)

题目链接: http://poj.org/problem?id=2935 解题报告:刷到bfs明显的感觉有些难,这道题应该卡的有3~4天了吧! 首先说明一下bfs如何记录路径:在结构体中,用一个值来记录上一个的位置,然后再“回溯”(并不是真的回溯)到第一个元素,然后递归输出即可; 第二点:交换两个数的位运算方法:a^=b^=a^=b,看上去显得代码更有技术含量 第三点:注意输入值的顺序,我就在这卡了n久 #include<cstdio> #include<cstring> #include<queue> #define swap(a,b) a^=b^=a^=b using namespace…

2013-10-08 21:55 · dfs · 图论 · 评论(0)

zoj 1091 (bfs搜索)

链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=91 结题报告:因该说10多天没有A题了,今天过了一道比较水的题目,也算是来纪念一下吧,最近在刷搜索的时候感觉bfs有些题目是比较难的,象蛇和梯子那道题整整卡了我一个星期但是现在仍然没有过,标记一下,有时间在回来看一下! 这道题注意两个地方,一个是下标的值,一个是vis数组标记! #include<cstdio> #include<cstring> #include<queue> using namespace std; const int dir[8][2] = {…

2013-09-28 21:25 · 图论,搜索 · 评论(0)

ZOJ Problem Set - 1649 Rescue (bfs搜所)

ZOJ Problem Set - 1649 Rescue Time Limit: 2 Seconds Memory Limit: 65536 KB Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. Angel's friends want to save Angel. Their task is: …

2013-09-15 20:17 · dfs · 图论 · 评论(0)

Farm Irrigation zoj 2412(dfs)

Farm Irrigation Time Limit: 2 Seconds Memory Limit: 65536 KB Benny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has a different type of pipe. There are 11 types of pipes, whi…

2013-09-12 19:30 · dfs · 图论 · 评论(0)

zoj 2110 Tempter of the Bone (dfs搜索)

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110 结题报告:搜索中的一个重要的剪枝,现在记录下来,作为一个积累; 起点到终点的距离即sx-ex+sy-ey如果是奇数, 则题目中所给定的时间一定是只有奇数才可能得到结果,如果题目中的起点到终点的距离如果是偶数,则题目中给的时间如果是偶数才可能得到想要的结果。如何优化题目代码已经标记: #include<cstdio> #include<cstring> using namespace std; const int maxn = 10; int n,m,t,…

2013-09-06 21:40 · dfs · 图论 · 评论(0)

hdu 1016 && zoj 1457 Prime Ring Problem (dfs)

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1457 解题报告:在zoj第一次提交的时候竟然是TLE,让我很是费解,然后把判断素数的方法变成直接打表的方法 ,以为这样可以节省很多的时间,结果还是TLE(hdu上此时就可以Ac),后来试了一下数字19,结果很久都没有跑出结果,感觉应该是这的问题,我就把奇数与偶数分开,结果AC。(感觉杭电的数据弱爆了) #include<cstdio> #include<cstring> #include<cmath> using namespace std; const …

2013-09-01 21:52 · dfs · 图论 · 评论(0)

poj 3264 Balanced Lineup (线段树)

题目链接 解题报告:线段树的入门题目,这里只需要两种操作“建树”、“查询”。 线段树解题的关键是节点存放的信息 #include <cstdio> #include<cstring> #include<algorithm> #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b #define mid(a,b) (a+b)>>1 #define L(a) a<<1 #define R(a) a<<1|1 const int MAX = 200000+10; const int INF = 0x3fffffff; int h[MAX],mini,ma…

2013-08-20 09:44 · 数据结构 · 评论(0)

hdu 1358 Period ((KMP算法)求循环节的个数)

题目链接 题意是求前n个数的循环节的个数: 例如:aabaabaabaab中 , 前2个字符aa,循环节为a, 所以为2 2; 前6 个 字符循环节为aab, 所以为6 2; 前9个 字符循环节为aab, 所以为9 3; 前12 个 字符循环节为aab,所以为12 4; 关键是如何求循环节,首先还要熟悉next数组的意思,next[j]=k,表示j前面k个元素与开头的前k个元素相同,但是中间可能有循环的元素,如何去除重复的元素 i 0 1 2 3 4 5 6 7 8 9 10 11 12 a[i] a a b a a b a a b a a b next[i] -1 0 1 0 1 2 3 …

2013-08-18 11:46 · 数据结构 · 评论(0)