Mato is No.1

歷經千辛萬苦總算搞定了COCI 2011 OPEN的所有題……真WS啊囧……
（不過除了sort的滿分算法稍微看了一下題解之外，其它的題目都是自己想出來的……這說明本沙茶想算法的能力并不差……只是所用的時間有點……）

sort：很容易想到該置換的循環分解，然后對每個長度大于1的循環進行一次操作就成了，總操作次數是長度大于1的循環個數。但是，這并不是最優解（在官方數據中，這個算法能過4個點，加上剩下6個點的一半分總共是70分，所以現場結果中多數人都是70分……）。最優解是先通過一次操作把各個長度大于1的循環攪亂，使得整個置換只有一個循環，然后再來一次操作就行了，也就是任何置換都最多只要兩次操作就行……至于攪亂的方法，只要在原來的各個循環（當然是長度大于1的）中各抽出一個元素，再對這些抽出的元素執行一次題目中的操作即可（證明是很容易的）。不過要注意只需0次或1次操作的情況：當原置換長度大于1的循環總數為0或1時；
至于具體的操作構造方法隨便亂搞一下就行了囧……

telka：應該算是最水的一題……樹狀數組的裸模型“改段求段”（具體見這里），唯一值得注意的就是在改段求段模型中的一個注意點：當l=1的時候，不能執行opr(l-1, c)，因為凡是下標遞增的數組都不能以0作為初始下標；

rijeka：這題比較坑人啊囧……如果任意時刻最多只能載一個人，可以把每個人的要求（也就是每條有向線段）都拆成若干個元線段，然后統計正反元線段的個數，亂搞一下就成了……不過這題目里面是可以載任意多的人……那么最優策略是：先把所有反方向線段覆蓋的總區間求出來，比如有4->2、6->3、9->8三條反方向線段，則覆蓋的區間就是[2, 6]和[8, 9]，然后在送人的時候，每送到一個區間的右端就回頭去把這個區間內的要走反方向的人全送到，然后再回頭往正方向開（比如上例中先從0到6，回到2，再從2到9，回到8，再回頭往前一直開到終點），這樣開到終點時，所有的人就都送到了，因此，總時間就是(M+反方向線段覆蓋的總長度)，用線段樹來搞。此外，由于M太大，需要離散化。

后面兩題就是猥瑣題了。

kamion：很明顯是個遞推……但是按照常規方法根本無法劃分狀態。不過，要發現本題和括號序列類的動態規劃神似，因此就可以用括號序列的來搞。關鍵是，對于那些第3種邊（既不含左括號也不含右括號的）比較難搞，另外本題還允許到終點的時候有左括號（就是大寫字母）剩余，這就明顯加大了難度。
狀態設計應是這樣的：F[i][j][k][s0][s1]，表示從i到j走正好k步，且滿足單多段限制（s0）和多余左括號限制（s1）的合法路徑總數，s0、s1為bool，s0表示是單段還是多段的規則括號序列，0：單段，1：單段或多段；s1表示是否可以有多余左括號，0：不能有；1：可以有（當然也可以木有，也就是s0和s1都是0包含在1之中的）。
遞推式：
F[i][j][k][0][0]=ΣF[t1][t2][k-2][1][0]（其中<i, t1>邊有一左括號，<t2, j>邊有一右括號，且兩括號匹配）；
F[i][j][k][1][0]=ΣF[t1][t2][k-2][1][0] + Σ(F[i][t][k'][0][0] * F[t][j][k-k'][0][1]) （注意0<k'<k，其它的類似）；