ural 1126 题意：n个数，求从第k个元素开始，求每k个元素的最大值（一共求n-k+1次） 思路：单调队列。 单调队列学习链接 其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333 说下我的理解： 单调队列的尾端（就是后进入元素的那一端）其实和单调栈类似。 首端加了个元素期限的概念，不断删除“过期”的元素。 所谓过期的元素，对于这道题来说，当我往前移动到第k+1个元素的时候，第1个元素就是过期了的元素，堆答案不会再有贡献。 理论上单调队列中的元素是<元素的期限，元素>的二元组。 而一般元素的"期限"是由下标的位置决定的，而得到下标就可以知道元素。 所以我们实际操 …

hdu 1559 题意：给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。 思路：二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。 /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 21时08分18秒 File Name :code/hdu/1559.cpp ************************************************ */ #include <cstdio> #include <cstring> …

poj 3494 题意：给出一个n*m个0-1图，求最大的全部由1组成的矩阵。 思路：同poj 1964,一共做n+2×m次单调栈。。。数组开小re一发。。某处stk忘记清空re 1发。。。智力-2.。。3A /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 19时33分14秒 File Name :code/poj/3494.cpp ************************************************ */ #include <cstdio> …

poj 2796 题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。 现在求value的最大值，并且输出得到这个最大值的区间。 思路：单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标，两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。 然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 19时14分42 …

poj 2082 题目链接 题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。 思路：单调栈。 之前的最大矩形面积的宽度都是1.。这次不是1.。做个宽度的前缀和就好。。。1A /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 18时54分40秒 File Name :code/poj/2082.cpp …

poj 1964 题意：n*m的maze,由'R'和‘F’组成，现在要求找到面积最大的矩形，使得矩形中所有格子都是'F'。 思路：单调栈...一开始神tm tle....复杂度没问题啊。。。 结果看到有人说这题由于数据量比较大。。。scanf会超时。。。所以要用输入挂。。。。。getchar什么的。。。 poj竟然也卡读入。。。人性呢。。。。 改了输出以后再交wa了。 发现想错了，我是写了从(i,j)到两个方向能到的最大距离。。但是这样写有些点上的情况是没有考虑到的。。比如如果(i+1,j+1)上的点是'R'，实际上是不可以构成l*r的矩形的(l>=2&r>=2)。。。但是我这样做无法体现。 改了下，变成： 仍然 …

poj 3250 题意： n头牛排成一列，第n只牛在最前面，第1只牛在最后面。第i只牛能看到的牛的个数是，它前面的且没有被其他牛遮挡的牛的个数，遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。 思路：单调栈。具体见代码。1A. /* *********************************************** Author :111qqz Created Time :2016年08月03日 星期三 05时12分47秒 File Name :code/poj/3250.cpp ************************************************ */ #include …

poj 2559 题意：给定从左到右多个矩形，已知这此矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，求该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。 思路：单调栈。。。好久没写了，感觉之前一直也没有完全掌握单调栈的技巧。这回一定要掌握。 对于这道题，我们对于每个位置i，用两个单调栈维护出最左边和最右边最远能到达的位置。然后扫一遍更新最大值。 单调栈部分我用了stl 的stack 细节见注释 /* *********************************************** Author :111qqz Created Time :2016 …

题目链接 题意：定义一个函数F．． For exampe: _F_(_babbabbababbab_, _babb_) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12) Its continuous sequences are: * (1, 4) * (4, 7) * (9, 12) * (1, 4), (4, 7) * (4, 7), (9, 12) * (1, 4), (4, 7), (9, 12) erfen ． erfen 题目描述得很烂．．看例子把．．大概就是：如果字符串y在字符串x中出现n次，那 …

poj 2406 题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值 思路:论文题. 转载论文中的题解: 做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n) …