====== Codeforces Round #656 (Div. 3) ======

====== [A] Three Pairwise Maximums ======

===== 题意 =====

水。

===== 解法 =====

水。

====== [B] Restore the Permutation by Merger ======

===== 题意 =====

同样的两个 1-n 排列随意穿插在一起，让你还原

===== 解法 =====

这个直接记录每个元素的第一次出现 ...

====== [C] Make It Good ======

===== 题意 =====

求一个序列的最长好后缀。

把后缀序列看成一个 deque，如果能从按值小到大 pop 那么是好的。

===== 解法 =====

从后往前看，直接记录上升下降后的第一次上升在哪，在这里断开。

====== [D] a-Good String ======

===== 题意 =====

递归定义一个 a-好 串，只需满足以下情况之一：

  * 长为 1，全为 a
  * 长 > 1，前一半全为 a，后一半是 a+1-好 串
  * 长 > 1，后一半全为 a，前一半是 a+1-好 串

问最少修改多少个元素可使得给出的串成为一个 'a'-好串

===== 做法 =====

像线段树那样区间 DP 即可。

记 dp[i][j] 为标号为 i 的区间成为 j-好串 的代价

记 DP[i][j] 为标号为 j 的区间全改成 j 的代价

则：

  * dp[u][i] = min(DP[u * 2][i] + dp[u * 2 + 1][i + 1], dp[u * 2][i + 1] + DP[u * 2 + 1][i])

  * DP[u][i] = DP[u * 2][i] + DP[u * 2 + 1][i]

====== [E] Directing Edges ======

===== 题意 =====

给一个图，有些边无向，有些边有向。问能否为所有无向边确定方向，使得确定完后的图是 DAG。有解输出方案。

===== 解法 =====

直接无视无向边，仅根据有向边进行拓扑排序，然后直接按照拓扑序确定无向边的方向。

====== [F] Removing Leaves ======

===== 题意 =====

给一棵树，每次可选同父亲的 k 个叶结点将其删除，问最多可进行多少次。

===== 解法 =====

不会做。

====== [G] Columns Swaps ======

===== 题意 =====

给一个 2*n 的矩阵，你每次操作可以翻转一列的元素（上下交换），问最少多少次使得上下两侧均为 1-n 的排列。

===== 解法 =====

直接跑个 2-SAT 就能过了吧。