ACM

CODE FESTIVAL 2017 qual B D - 101 to 010(线性dp)

CODE FESTIVAL 2017 qual B D - 101 to 010(线性dp)
题目:给你一串由0或1组成的串,每次可以将101转换成010,求最大的可转换次数。题解:假设只有一个101那么只操作一次,但是会出现这种情况,比如1101、1011,像这些情况,第一个101转换成010之后会对接下来的字符串提供一个贡献。设一个长度为n的字符串由k个连续的1接一个0再接1个1(或者是一个1接一个0再接k个1),那么这种情况下这个串的可操作次数是k。但是对于11110111111这种... 继续阅读 »
ACM

51nod 1682 中位数计数(差分统计)

51nod 1682 中位数计数(差分统计)
题目:中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。题解:一个数作为中位数,那么区间内大于他的数的数目以及小于他的数的数目必然相等。所有区间情况也就是三种:[_____i],[____i____],[i____]。其中第一种和第三种是一样的,而且也比较好计算... 继续阅读 »
ACM

51nod 1109 01组成的N的倍数(BFS+剪枝)

51nod 1109 01组成的N的倍数(BFS+剪枝)
题目:给定一个自然数N,找出一个M,使得M > 0且M是N的倍数,并且M的10进制表示只包含0或1。求最小的M。例如:N = 4,M = 100。题解:因为答案必须为十进制只包含01的数,所以我们只需要不断把当前数*10,和当前数*10+1放入队列即可。因为最终得到的结果可能会超出long long型,所以我们可以用字符串来存储,然后按照大数取模来计算余数即可。为什么要计算余数呢?... 继续阅读 »
ACM

51nod 1105 第K大的数(二分答案+二分查找)

51nod 1105 第K大的数(二分答案+二分查找)
题目:数组A和数组B,里面都有n个整数。数组C共有n^2个整数,分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1](数组A同数组B的组合)。求数组C中第K大的数。例如:A:1 2 3,B:2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。题解:二分好题,最重要... 继续阅读 »
ACM

tenka1-2017-IntegerotS(位运算+贪心)

tenka1-2017-IntegerotS(位运算+贪心)
题意:给出n组数据,ai,bi,意味着编号为ai的物品价值为bi,求选择一些ai,他们或运算之后小于或等于k的最大价值。题解:贪心法,因为当前选择的ai或运算之后有可能会大于k,考虑到或运算的性质,假设当前选择的数或运算之后必须小于或者等于k,那么我们必须要选择这样的一个a[i],a[i]&k==a[i]。即k的二进制位上有1的地方,a[i]才能有1。然后,循环将k二进制位上有1的位减一(... 继续阅读 »
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前缀... 继续阅读 »