bzoj 1303: [CQOI2009]中位数图 dp 乘法原理

我们从d的点往左扫,然后我们用一个变量维护大于小于d点值的数量,即大于d点就++,小于d点就–。然后我们每次记录一下不同的这个变量的数量。然后我们同理处理右侧。我们考虑如果左侧有变量维护为1,意味着我们缺少一个小于d的量。那我们去右侧找-1,然后相乘即可。记得算上这个变量为0的情况。和d本身是一个[……]

Read more

POJ1113 Wall 凸包 Andrew算法

算法讲解:

我们把所有点按照x排序,若x相容则按照y排序。然后我们准备一个栈,每次如果栈内元素>=2我们就看待加入元素与栈顶元素的连线和栈顶元素和栈第二个元素的连线的位置关系。如果在左面,就加入。否则,就删除最近加入的点。直到在左面。然后我们这样子就求出了下凸包。然后我们只要再反着求一遍[……]

Read more

codeforces 402div2 D – String Game 二分

二分一下可以拆到什么位置就好了。快被自己蠢哭了。二分l,r写反了,然后就变枚举了。然后就tle了。

codeforces 402div2 C. Dishonest Sellers 贪心

尽可能的拿相对而言优惠的就可以了。

codeforces 402div2 B. Weird Rounding 贪心

就从后尽可能的多的删就行了。如果发现最后也没删成就删成0。

codeforces 402div2 A. Pupils Redistribution 简单思维题

如果有一种等级的人为奇数,则不可行。否则答案为一个班级所要进入的人的总数。这样子正确性非常显然。

codeforces 401div2 e Hanoi Factory 排序,栈

先按照外径排序,从大到小,外径相同按照内径排序。然后我们每次发现如果当前元素不能放入栈顶,就不断删除栈内元素直到可以删除。然后更新答案。我们可以证明,若果当前元素放不进去,那么根据排序得出的后面的元素也是放不进去的。所以这么做是没有问题的。
[crayon-5bcf4ae1dbd104123599[……]

Read more

codeforces 401 div2 d Cloud of Hashtags 贪心

从下往上,不行就尽可能少的删除字符让他满足。还是坑爹数据,逼人用vector搞字符串。

codeforces 401div2 c Alyona and Spreadsheet

大概题意,给你一个矩阵。每次询问l-r行是否有一列为单调不递减的。我们只要n^2dp一下就好了。记录一下包含i,j这个元素所在的最长的纵向的在i,j元素上面的不递减序列的长度,然后每行算出一个max即可。这题感觉最坑的是数据范围。逼着你开vector..
[crayon-5bcf4ae1dc294[……]

Read more