十一七天終于結束了... 成果是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
西月弦 閱讀(552)
評論(10) 編輯 收藏 引用 所屬分類:
解題報告 、
codeforces