【溫故知新】BZOJ複習計劃

前言：

在BZOJ上也做了不少題了，但是有些題當時在做的時候了解不夠深刻，或是時間久了忘記了，都是形同虛設的。那麼，有空就多看看自己以前做的題目吧……

==============分割線==============

1805: [Ioi2007]Sail 船帆：

好題。首先我們要得到貪心的政策，從後往前放旗子，每次選目前行最少旗子的放，若相同則從上往下放，正确性顯然。但有了這個還不夠，我們還需要維護每次的操作。注意到如果将杆按高度從小到大排序，貪心政策依然可行，而且每次都是某一段+1，那麼我們就可以差分，維護delta，用線段樹實作即可。

3210: 花神的澆花集會 3170: [Tjoi 2013]松鼠聚會：

切比雪夫距離轉曼哈頓距離。切比雪夫距離為 max(|x1−x2|,|y1−y2|) m a x ( | x 1 − x 2 | , | y 1 − y 2 | ) ，令新點的坐标為 X=x+y,Y=x−y X = x + y , Y = x − y ，那麼切比雪夫距離為曼哈頓距離的一半。

2324: [ZJOI2011]營救皮卡丘：

挺強的費用流，當時做這道題目的時候不太了解floyd的限制條件，現在再看就突然明白了，對于每一個i，前面的狀态都是保證1~i-1是走過的，是以即使中轉點k的編号是比i要小的，也隻是重複走了一次而已。

1007: [HNOI2008]水準可見直線：

将直線按照k排序後用一個棧維護，最後在棧中的就為可見直線，類似維護凸包。

2006: [NOI2010]超級鋼琴：重新看隻想到了堆+主席樹的做法……其實還可以直接RMQ，每次把區間分裂成兩個即可實作删除操作。

1228: [SDOI2009]E&D：今天初二的來問我們這道題，發現SG已經忘得一幹二淨了，連定義都忘了……今天重新回憶了一下，基本的定義大概是這樣的：

1、先手必敗态的SG值為0

2、其它狀态的SG值為所有它能到達的狀态的SG值的mex

3、把各個子狀态的SG值異或起來，為0則先手必敗，否則必勝

對于這道題，還要把SG值的表打出來，找規律才行……