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，其它的类似）；