c++&oi

培訓作業-第一周(樹狀數組)

樹狀數組題目列表

POJ 3378  Crazy Thairs      (WA)        
POJ 2481 Cows                AC
POJ 2352 Stars                AC
POJ 3321 Apple Tree        AC
POJ 3067 Japan               AC
POJ 1195 Mobile phones  AC
POJ 2155  Matrix             AC
POJ 1990  MooFest          AC

第一周寫作業就沒寫完。。。對不起大家。
留下了三道題目繼續思考。那個培訓題3就當做下一周的線段樹吧。

poj2352（3次AC）
根據題意用樹狀數組模擬。
這道題我竟想了好久，寫完之后數組上向下溢出。。。
（可能是英語水平退步的緣故，讀完題各種條件印象不深）

poj1195（2次AC）
二維樹狀數組
一開始沒有注意循環的處理，由于樣例不過，檢查出來了。
改后提交WA，
原來是不小心打錯了y1->y2。。。
（沒有檢查！）

poj3067（AC）
排序+樹狀數組
貌似是以前做過的。。。但還是花了不少時間。（還研究了一下sort和qsort）
這里排序是雙關鍵字，用了cstdlib的快排。
關于cstdlib的快排用法的文章已經轉到了我的cppblog
數據比較大，要用long long
【固定思維是：升序排序+樹狀數組倒著用。何必呢?樹樁數組才是主題，降序排序不就行了嗎。。。】

poj3378 (WA)
簡單DP
實現時用樹狀數組+離散化
數據規模大得驚人！！
寫了高精度后莫名地掛掉。

poj2155(AC)
模式二的水題，而且還可以化簡為 ^ 運算。。。
快速地學習了一下模式二就AC了

poj2481（5次AC）
看似只是簡單的sort+樹狀數組。
其實細節比較多，sort是雙關鍵字。
然后由
Given two cows: cowi and cowj, their favourite clover range is [Si, Ei] and [Sj, Ej].
 If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cowi is stronger than cowj.
知邊界可以相同，又不能完全相同。
加上poj.org和我家的時間不一致，導致我以為沒有提交成功。。。提交了幾次錯誤的代碼。。。。。

poj3321（2次AC）
利用樹的歐拉序列，記錄每個節點的起始時間和它的子樹的結束時間。
化點為線，且a是b的子節點<==>區間a屬于區間b
怎么WA的一次忘記了。。

poj1990（AC）
這題是最難最難的。
按V排序，利用樹狀數組計算
sigma|xj-xi|=xi*sigma(1)[xj<xi]-sigma(xj)[xj<xi]
             +sigma(xj)[xj>xi]-xi*sigma(1)[xj>xi]

posted on 2012-02-26 12:47 zyn.cpp 閱讀(302) 評論(0)  編輯 收藏 引用