十一七天终于结束了... 成果是AK了3场CF，做了2场TC的div1 250与500。还算效率可以吧....
代码见：
http://codeforces.com/contest/226/my
A 汉诺塔，不用多说...
B
有N(N<100,000)堆石子，任何一堆石子i可以放到任何一堆石子j上，代价是i的石子数量。
合并以后，这堆石子数量是两堆石子的和，标号是j。
现在询问，每堆石子被+不能超过k的最小代价。
算法分析：
一开始以为是Huffman Tree，其实毛关系没有，如果k没有限制那么答案应该是所有石子加和减去最大的那个...
如果有限制k，那么我们想，最后的情形一定是k堆石子加到了某石子i上，那么石子i一定是最大的那个（因为i不用加了）...
那么这k堆的石子标号一定是次大的k个，k堆石子一定是k*k堆石子累加的... 于是这样类推.... 一开始排个序就好了...
C
在[l,r]中，选k个数，让他们的最大公约数最大, l,r<1,000,000,000,000
算法分析：
巨坑的一题，答案的分布不是单调的，无法枚举结果。只能改变思路...
假设答案是ans， 那么一定有
r/ans - (l-1)/ans >= k
a/b下取整最多有2*sqrt(a)个，怎么求自己想吧 ＝＝ , 于是枚举ans就可以了....
D 不会证明
E
给一颗大小100,000的树，100,000次操作。每次操作要么给一个节点赋一个值，要么求一个路径上的比 x大的点数。
算法分析：
树链剖分转为线形结构，然后问题就是如何就一个区间里比k大的数的个数，而且支持修改。
线段树树套按权值建的线段树搞之...
posted on 2012-10-07 16:10
西月弦 阅读(539)
评论(10) 编辑 收藏 引用 所属分类:
解题报告 、
codeforces