十一七天終于結(jié)束了... 成果是AK了3場CF，做了2場TC的div1 250與500。還算效率可以吧....
代碼見：
http://codeforces.com/contest/226/my
A 漢諾塔，不用多說...
B
有N(N<100,000)堆石子，任何一堆石子i可以放到任何一堆石子j上，代價是i的石子數(shù)量。
合并以后，這堆石子數(shù)量是兩堆石子的和，標號是j。
現(xiàn)在詢問，每堆石子被+不能超過k的最小代價。
算法分析：
一開始以為是Huffman Tree，其實毛關(guān)系沒有，如果k沒有限制那么答案應(yīng)該是所有石子加和減去最大的那個...
如果有限制k，那么我們想，最后的情形一定是k堆石子加到了某石子i上，那么石子i一定是最大的那個（因為i不用加了）...
那么這k堆的石子標號一定是次大的k個，k堆石子一定是k*k堆石子累加的... 于是這樣類推.... 一開始排個序就好了...
C
在[l,r]中，選k個數(shù)，讓他們的最大公約數(shù)最大, l,r<1,000,000,000,000
算法分析：
巨坑的一題，答案的分布不是單調(diào)的，無法枚舉結(jié)果。只能改變思路...
假設(shè)答案是ans， 那么一定有
r/ans - (l-1)/ans >= k
a/b下取整最多有2*sqrt(a)個，怎么求自己想吧 ＝＝ , 于是枚舉ans就可以了....
D 不會證明
E
給一顆大小100,000的樹，100,000次操作。每次操作要么給一個節(jié)點賦一個值，要么求一個路徑上的比 x大的點數(shù)。
算法分析：
樹鏈剖分轉(zhuǎn)為線形結(jié)構(gòu)，然后問題就是如何就一個區(qū)間里比k大的數(shù)的個數(shù)，而且支持修改。
線段樹樹套按權(quán)值建的線段樹搞之...
posted on 2012-10-07 16:10
西月弦 閱讀(595)
評論(10) 編輯 收藏 引用 所屬分類:
解題報告 、
codeforces