ACM

51nod 1215 数组的宽度(单调栈+思维)

51nod 1215 数组的宽度(单调栈+思维)
题目:N个整数组成的数组,定义子数组a[i]..a[j]的宽度为:max(a[i]..a[j]) - min(a[i]..a[j]),求所有子数组的宽度和。题解:首先题目的意思可以转化为求所有的子数组最大值之和减去所有的子数组最小值之和。那么我们可以通过两次单调栈求得以每个a[i]作为最大以及最小的左右两端能到达的端点。然后求左右端点的时候要注意的一点是确定左边的重复计算或者右边的重复计算,因此通... 继续阅读 »
ACM

51nod 1737 配对(树的重心|贡献)

51nod 1737 配对(树的重心|贡献)
题目:给出一棵n个点的树,将这n个点两两配对,求所有可行的方案中配对两点间的距离的总和最大为多少。题解:解法一:一开始是想找出一个点,然后求出所有点到这个点的距离,这样配对的话就是每个点到这个点距离之和。但是这个点怎么求呢?其实这个点就是树的重心。于是先求一遍树的重心,然后从树的重心求一遍最短路之后求和就行。树的直径定义:删除某个点,使得这个点的所有子树中最大的子树的节点数最小。解法二:其实不需要... 继续阅读 »
ACM

51nod 1102 面积最大的矩形(单调栈)

51nod 1102 面积最大的矩形(单调栈)
题目:有一个正整数的数组,化为直方图,求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3,对应的直方图如下:面积最大的矩形为5,6组成的宽度为2的矩形,面积为10。题解:用单调栈存储从当前点开始往左右两边能到达的最远的坐标,遍历两遍即可获得。之后遍历一遍求最大值即可。代码:#include <iostream> #include <cstdio>... 继续阅读 »
ACM

51nod 1279 扔盘子(单调栈)

51nod 1279 扔盘子(单调栈)
有一口井,井的高度为N,每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘,如果圆盘的宽度大于井在某个高度的宽度,则圆盘被卡住(恰好等于的话会下去)。盘子有几种命运:1、掉到井底。2、被卡住。3、落到别的盘子上方。盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度,求最终落到井内的盘子数量。如图井和盘子信息如下:井:5 6 4 3 6 2 3盘子:2 3 5 2 4最终有4个盘子落在井内。题解:... 继续阅读 »
ACM

HDU 4300 Clairewd’s message(hash模板题)

HDU 4300 Clairewd’s message(hash模板题)
题目的意思是给你一串长度为26的密钥,意味着abcd...xyz各自被加密成了什么字符。现在给出你另外一段由密文和明文组成的字符串,密文在前面,明文在后面,但是明文有可能不完整。如果明文不完整请补充完明文。这个题看题目还是看的有点绕,看懂之后还是很容易的。假设把给出的文章串设为S1,那么我们可以把S1按照给出的密钥加密为S2,这样就把S1后面的明文加密了。然后判断加密后S2的后缀和未加密的S1前缀... 继续阅读 »