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 1279 扔盘子(单调栈)

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

2016HUAS_ACM暑假周测4 - A - 度熊哈希值问题

2016HUAS_ACM暑假周测4 - A - 度熊哈希值问题
哈希值问题。一看就应该知道用线段树可以AC。但是一开始想着用long long存应该没问题,就用一个数组存下了从1到这个数的乘积。用的时候用后面的位置除以前面位置-1的值就好了。但是竟然。。。Runtime Error(INTEGER_DIVIDE_BY_ZERO),怎么可能会有0作被除数的情况,这不科学啊?难道溢出了?诶。算了。还是线段树吧,然后就AC了。。。只不过这线段树不够优啊,happy_... 继续阅读 »
ACM

2016HUAS_ACM暑假周测1-D - Parentheses Balance

2016HUAS_ACM暑假周测1-D - Parentheses Balance
D - Parentheses Balance        这个题目和那个简单计算器类似,用了栈,如果后面的字符能和前面的字符配对(我没看懂题目意思,大概猜测了一下是这个意思吧~)那么删除前面的字符,当然,这个字符也不要了,如果最后都能配对,那么栈肯定为空,所以通过判断栈是否为空可以获得答案。Descrip... 继续阅读 »
ACM

2016HUAS_ACM暑假集训1-F - 简单计算器

2016HUAS_ACM暑假集训1-F - 简单计算器
F - 简单计算器        简单计算器这个题一开始我自己写了一个切割函数,把字符和数字切割开来,之后再判断进行计算,但是,很不幸,总是Wrong Answer,说好的简单计算器呢,简单在哪里呢?后来在网上看了别人的思路,为什么不在入栈时就进行计算呢,嗯,没错,好主意,说干就干,然后,发现真的很简单,但是... 继续阅读 »
ACM

2016HUAS_ACM暑假集训1-E - Rails

2016HUAS_ACM暑假集训1-E - Rails
E - Rails        Rails,火车问题,栈的典型应用,通过入栈来对比是否成立,《算法竞赛入门经典(第2版)》里面的例子,不多做解释。The local tradition is that every train arriving from the direction A continues i... 继续阅读 »