目录  P1396 营救 题目描述 “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动的热泪盈眶，开起了门…… 妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了t区，而自己在s区。 该市有m条大道连接n个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从s至t的路线，使得经过道路的拥挤度最大值最小。 输入格式 第一行四个数字n，m，s，t。 接下来m行，每行三个数字，分别表示两个区和拥挤度。 （有可能两个区之间有多条大道相连。) 输出格...

算法:单调栈和单调队列  一.单调栈和单调队列 二.单调栈例题  1.模板题入门 2.不懂不要急，看这道题  三.单调队列例题  1.入门 2.进阶    一.单调栈和单调队列 单调栈和单调队列与普通的栈，队列不同点就是要维护他们元素的单调性（单增或单减），来实现相应的效果。要注意的是单调栈和单调队列即可以用数组模拟，也可以直接使用STL（更方便易于理解），但是如果用STL的话，单调栈/队列要在开始放入元素之前设置边界，单调递增就在边界（栈顶/队首）赋值为负值（<=0），单调递减就在边界赋值为INF(极大值)。因为如果栈/队列内无元素，那么s.top()是不合法的，这样就无法继续进行插入...

存一下链接慢慢看 曼哈顿距离和切比雪夫距离 这个更清晰一些： 关于曼哈顿距离和切比雪夫距离 NN中常用的距离计算公式：欧式距离、曼哈顿距离、马氏距离、余弦、汉明距离

姊妹篇（DFS）   目录  一.入门级  P1747 好奇怪的游戏 TRDD got lost again  二.进阶  final的BFS Abbott's Revenge    一.入门级 P1747 好奇怪的游戏 P1747 好奇怪的游戏 题目描述 爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，...

目录  一.前缀和 二. 差分思想  1.静态数组的区间求和问题 2.静态维护区间加等差数列的求和问题  三.二维前缀和 二维前缀和例题P2280 [HNOI2003]激光炸弹 四.例题  例题一：差分+前缀和+贪心 例题二.差分+前缀和    一.前缀和 给定一个序列，定义pre[i]=pre[i-1]+a[i]; 可求区间[l,r]的和：pre[r]-pre[l-1]; 可求区间的[l,r]的异或和：（异或的逆运算是它本身）所以即为pre[r]^pre[l-1]; 若有n组操作，操作为将区间[l,r]中的数增加k，最后输出这个数组。 可以暴力跑，但如果数据较大就会超时，所以要用到下面的差分...

三维DP   1. P1006 传纸条 2.方格取数 3.Fillin的赚钱之路    1. P1006 传纸条 P1006 传纸条 题目描述 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给...

一.LCS最长公共子序列 最长公共子序列（LCS）问题算法详解+例题（转换成LIS，优化为O(nlogn)，看不懂你来打我） longest comment subsequence 模板题 longest comment subsequence A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, …, xm> another sequence Z = <z1, z2, ...

目录  一.模板题 二.树状数组求逆序对  一.离散化 二.逆序对 三.待解决 P1428 小鱼比可爱    算法详解 一.模板题 模板题 题目描述 如题，已知一个数列，你需要进行下面两种操作： 将某一个数加上 x求出某区间每一个数的和 输入格式 第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。 第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。 接下来 m 行每行包含 3 个整数，表示一个操作，具体如下： 1 x k 含义：将第 x 个数加上 k 2 x y 含义：输出区间 [x,y] 内每个数的和 输出格式 输出包含若干行整数，即为所有...

线性表——栈，队列，链表  目录  一.栈  １.函数实现栈 ２.宏定义实现栈 ３.STL实现栈 例题1:P1241 括号序列 例题2:P1449 后缀表达式  二.队列  实现队列 例题1.约瑟夫问题  三.双端队列 链表   一.栈 栈（stack）(last in first out);后进先出 １.函数实现栈 #include<cstdio> using namespace std; int s[10005]; int tot; void push(int x) { s[++tot]=x; } void pop() { tot--; } void print() { for...

目录  二叉排序树  1.二叉排序树(代码) P1087 FBI树 (建树) HDU 4707 Pet    二叉排序树  先序遍历：根->左->右 中序遍历：左->根->右 后序遍历：左->右->根  1.二叉排序树(代码) 输入 7 5 4 3 3 3 2 1 输出 1 2 3 3 3 4 5 //二叉排序树（左<根<右） #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e5+10; struct node{ ll val...

排序目录：  一.sort() 二.stable_sort() 三.merge()  1.merge函数的作用： 2.为什么引入归并排序merge()函数 3.代码 4.例题P1309 瑞士轮    一.sort() cppreference中的详细解释 二.stable_sort() stable_sort()遇见大小相同的值不会改变他们的位置 cppreference中的详细解释 三.merge() cppreference中的详细解释 1.merge函数的作用： 将两个有序的序列合并为一个有序的序列。函数参数：merge(first1,last1,first2,last2,result,...

在网上看到别人ACM学习的心得，转载过来，源地址不记得了，当时是百度的。内容如下： 网络上流传的答案有很多，估计提问者也曾经去网上搜过。所以根据自己微薄的经验提点看法。 我ACM初期是训练编码能力，以水题为主（就是没有任何算法，自己靠动脑筋能够实现的），这种题目特点是麻烦，但是不难，30-50道题目就可以了。 然后可以接触一下基础的算法，我感觉搜索方向的比较不错，可以解决很多问题，深搜，广搜，然后各种剪枝能力的锻炼。 搜索感觉不错了就可以去看看贪心，图论，和动态规划方向的了。图论有最短路径，最小生成树，网络流，拓扑排序等等很多，动态规划先去书上看经典例子，最长公共子序列等。各种变形的题目。 数...

按位与、或、非、异或总结 按位与(&)、按位或(|)、按位异或(^)、按位取反(~)、线性基 位运算简介及实用技巧（一）：基础篇

目录  一.位运算详解 二.位运算应用  1.快速幂 2.给定一个数组A, 长度为n，求下面这段程序的值 3.数数字 4.数数字 2 5.nim博弈问题： 6.树状数组 7.判断一个数x是不是2的某次方 神殿    一.位运算详解 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）。 各种...