算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
十一七天终于结束了... 成果是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 西月弦 阅读(484) 评论(10)  编辑 收藏 引用 所属分类: 解题报告codeforces

FeedBack:
# re: codeforces #140
2012-10-07 21:08 | cgangee
不懂C题,怎么枚举ans?  回复  更多评论
  
# re: codeforces #140
2012-10-08 11:09 | 西月弦
@cgangee
a/b的值只可能是 a/1 a/2 a/3 a/4 .... a/ sqrt(a) 和 1 .. 2.. 3.. sqrt(a)  回复  更多评论
  
# re: codeforces #140
2012-10-25 13:50 | snowfox
大神 C题不懂 能说的详细点吗?  回复  更多评论
  
# re: codeforces #140
2012-10-28 11:33 | 西月弦
@snowfox
根据gcd(F(i),F(j)) = F(gcd(i,j)) 我们可以得出,该问题等价于求在[l,r]中选出k个数让他们的gcd最大。

假设这个gcd是ans
那么就相当于求 r/ans - (l-1)/ans >= k (我这个沙茶写错了,对不起。。)

a/b下取整可能的取值是有O(sqrt(a))个,见我上一个回复。
这样一词枚举就可以了。。。 哪里不明白我还可以详细解释  回复  更多评论
  
# re: codeforces #140
2012-10-28 14:07 | snowfox
@西月弦
谢谢神牛~  回复  更多评论
  
# re: codeforces #140
2012-10-28 14:55 | snowfox
@西月弦
懂了 懂了~  回复  更多评论
  
# re: codeforces #140
2012-10-28 17:22 | snowfox
@snowfox
神牛 如果是10 4 8 2 这组数据的话 ans应该等于4 但是根据 r/ans - (l-1)/ans >= k 8/4-3/4>=2 不成立啊……  回复  更多评论
  
# re: codeforces #140
2012-10-28 17:23 | snowfox
神牛 如果是10 4 8 2 这组数据的话 ans应该等于4 但是根据 r/ans - (l-1)/ans >= k 8/4-3/4>=2 不成立啊……   回复  更多评论
  
# re: codeforces #140
2012-10-29 17:44 | 西月弦
@snowfox
8/4 - 3/4 = 2 >= 2 哪里不对了><  回复  更多评论
  
# re: codeforces #140
2012-10-29 18:08 | snowfox
@西月弦
额……我错了……我错了……我忘了是取整了……擦……我SB了……  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理