单调栈 单调栈下一个更大的元素 直接用单调递增的栈来求出每一个点最近大于该点的值 用k-y来存该点下一个更大的值，遍历询问就行。123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <unordered_map>#include <stac 2019-04-19 算法
兔子的兔子(字符串hash) 把我坑惨了（1个小时） 将cin换成scanf cout 换成printf就过了，思路：询问区间值就用前缀和来做，将字符串通过一个hash函数映射在几乎不会重复的集合内，能够快速判断是否子字符串是否重复出现过， 用unsigned long long存hash值相当于自动对$2^{64}$mod 把字符串看成P进制下的数，如S="abc" $h(S)=1p^2+2p^ 2019-04-19 算法
实数域上的二分(poj 2018) 设置精度epspoj 2018求平均数的最大值，那么平均数在一个区间内肯定具有一个点，满足该点右边都不成立，左边都成立但不是最大，所以可以在这个区间内进行二分 技巧：将a[i]转化为b[i]=a[i]-averge，那么只要b[i]的最大子段和>0该average成立，证明: $\Sigma^{n} _{i=1}a[i] = n * average$把$\Sigma$展开，ave移到左 2019-04-17 算法 二分
打家劫舍（+变形 dp） dp题目 题目给出n个，我们从1个开始分析1个房子 dp[1]=nums[1];2—- dp[2]=max(nums[1],nums[2]); 不能偷相邻的，所以2选13—- dp[3]=max(dp[3-2]+nums[3],dp[2]); 偷1,3号房子，否则偷2号房子即使d[2]=nums[1],也没关系，dp[3]取max后代表的还是偷1,3的值得到dp方程 $dp[i 2019-04-16 算法 dp
爬楼梯（leetcode_070 dp） 题目非常简单容易理解的线性dp，有n阶台阶，一次爬1或2个，爬到n阶有多少种方法，有1阶 dp[1]=1有2阶 dp[2]=2 (1+1 0+2)依次类推 dp[i]:代表到第i阶台阶的方法， 第i阶台阶可以分别由 i-2 走2步 和 i-1走1步到达 dp方程 dp[i]=dp[i-1]+dp[i-2] 最小花费爬楼梯在上一题原理上+每层台阶的花费 需要注意爬到最高层有2种情况 2019-04-15 算法 dp
最长上升子序列（dp leetcode_300） 最长上升子序列题目给定一个无序的整数数组，找到其中最长上升子序列的长度。样例输入： 123输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 思路用一个数组来维护上升的子序列，扫描原数组的数时，用二分在新数组中找到并且加入，但是要替换掉原来的，因为要按照原数组的顺序加入，如果新数组的数都小于该数，直接 2019-04-15 算法 dp
leetcode_53 最大自序和(类似LIS,dp) dp简单题题目 如何理解 当前子序碰到 a[i]<0 加不加到子序中 如果将a[i]加入到sum中，sum仍然>0,那么加入是有意义的，否则没有意义，即是加入a[i] a[i]<0使得sum减小，但我们已经记录上一个sum作为最大的自序和，并且加入a[i]后，a[i+1]更大，成为新的最大子序和。 因为求最大子序的和，当$sum[i-1]+a[i]<=a[i 2019-04-15 算法 dp
获取所有钥匙的最短路径（二进制状态压缩） description给定一个二维网格 grid。“.” 代表一个空房间， “#” 代表一堵墙， “@” 是起点，（”a”, “b”, …）代表钥匙，（”A”, “B”, …）代表锁。 我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。 假设 K 为钥匙/ 2019-04-14 算法 二进制状态压缩
费解的开关(二进制状态压缩) 费解的开关 你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯 自然想到从第一行开始点，但是点第1行第2个时候发现第1个又变了，只能枚举第1行的所有操作，（每点2个 2019-04-14 算法 状态压缩
供暖器（leetcode_475 二分） 题目 只要结果在一个单调区间内，且结果两边一边满足另一边不满足，用二分查找ans，当ans特殊时，考虑用倍增r=max(house[n-1],heater[m-1]) 此时半径一定能包含所有的housecheck时 以heater为点 看house满足范围就行了二分模板 12345678910111213141516171819202122232425262728293031323 2019-04-14 算法 二分