水。

水。

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

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

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

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

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

递归定义一个 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]

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

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

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

不会做。

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

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