文章列表
1、何为单调栈：顾名思义，栈中的元素是按照某种方式排列，但是必须是单调的，如果某元素破坏了栈的单调性，就弹出栈的元素，直到该元素满足栈的单调性为止。
2、用途：可以很方便的求出某元素左边或右边第一个比其大或者小的元素，且时间复杂度O（n）;
hm 与 zx系列故事题目链接
训练赛的时候没能够做出来，自己当时根本就不知到什么是单调栈，更别说应用了，平时应该多多的积累一些知识点，遇到不会的赶紧去学习，感觉知识单单钻一个方向不行。
#include<cstdio>
#include<iostream>
#include<stack>
# ...
ZOJ Problem Set - 1655 Transport Goods
结题报告：
一开始用的是从首都向其他城市搜索，记录路径，然后向回搜索，但是出现了wa。
后来搜了一下结题报告，别人都是直接搜索，使费用率最大，试了一下，这样做还是wa
最后看了 小媛 的，才知道是可能同时出现费用率不同的同一条路，这是后我们当然要选择费用率较小的
感觉自己第一遍记录路径代码可以过！，但是细节没有注意
#include<cstdio>
#include<cstring>
#include<algorithm>
using names ...
题目链接：poj 1679 The Unique MST
解题报告：最小生成树是否唯一判断方法
（1）图中每条边，扫描其他边，如果存在权值相同的边，则对其边标记
（2）用kruskal或prim算法求最小生成树的权值
（3）得到最小生成树，如果该最小生成树不包含标记的边，则最小生成树唯一，如果包含了标记的边，则依次去掉标记的边，再求最小生成树，如果求得的最小生成树与原最小生成树的权值相同，则最小生成树不唯一
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
...
题目链接 ：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1048
解题报告：在zoj上wa了多次还是过不了，感觉很郁闷，就去poj上提交，结果poj可以过。
代码其实很快就敲出来了，只是一直wa改了很久也没有发现错误，刚开始我还以为是已经完全联通的城市需要输出一个空行呢，结果只是两组数据之间夹一个空行，zoj上顺利通过，希望wa的可以借鉴一下。
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#d ...
链接：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
说 ...
链接：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 cm ...
题目链接：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
输入的数字就是位于最上面的数字，然后与下面的数字都有关系，这种关系用邻接表存储
最后用拓扑 ...
题目链接：http://poj.org/problem?id=2935
解题报告：刷到bfs明显的感觉有些难，这道题应该卡的有3~4天了吧！
首先说明一下bfs如何记录路径：在结构体中，用一个值来记录上一个的位置，然后再“回溯”（并不是真的回溯）到第一个元素，然后递归输出即可；
第二点：交换两个数的位运算方法：a^=b^=a^=b,看上去显得代码更有技术含量
第三点：注意输入值的顺序，我就在这卡了n久
#include<cstdio>
#include<cstring>
#include<queue>
#define swap(a ...
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=91
结题报告：因该说10多天没有A题了，今天过了一道比较水的题目，也算是来纪念一下吧，最近在刷搜索的时候感觉bfs有些题目是比较难的，象蛇和梯子那道题整整卡了我一个星期但是现在仍然没有过，标记一下，有时间在回来看一下！
这道题注意两个地方，一个是下标的值，一个是vis数组标记！
#include<cstdio>
#include<cstring>
#include<queue>
using namespace ...
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. T ...
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 pip ...
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110
结题报告：搜索中的一个重要的剪枝，现在记录下来，作为一个积累；
起点到终点的距离即sx-ex+sy-ey如果是奇数， 则题目中所给定的时间一定是只有奇数才可能得到结果，如果题目中的起点到终点的距离如果是偶数，则题目中给的时间如果是偶数才可能得到想要的结果。如何优化题目代码已经标记：
#include<cstdio>
#include<cstring>
using namespace std;
co ...
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1457
解题报告：在zoj第一次提交的时候竟然是TLE,让我很是费解，然后把判断素数的方法变成直接打表的方法 ，以为这样可以节省很多的时间，结果还是TLE(hdu上此时就可以Ac),后来试了一下数字19，结果很久都没有跑出结果，感觉应该是这的问题，我就把奇数与偶数分开，结果AC。（感觉杭电的数据弱爆了）
#include<cstdio>
#include<cstring>
#include<cmath>
...
题目链接
解题报告：线段树的入门题目，这里只需要两种操作“建树”、“查询”。
线段树解题的关键是节点存放的信息
#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 in ...
题目链接
题意是求前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
...