2017-C11-team8

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== D ===
可以用数论中常见的n^0.5^优化方法优化，即考虑每次取出的序列的长度，不同长度只有n^0.5^，将相同长度合并处理。O(n^0.5^)。
=== E ===
首先不考虑交换情况下贪心分段，选其中一段用交换来增加段数。假设某段长l，用1..l表示数字。该段中有k个符合要求的前缀，内部排序后分别是[a_k,l], [a_{k-1}, l], .., [1, l]。那么整段相当于被分为k个区间，内部排序后是[a_k, l], [a_{k-1}, a_k-1], .., [1, a_2-1]。贪心策略是选取一个前缀和一个后缀组成用于交换的两段，其余部分尽可能多分段。注意到如果中间的非交换部分包含不止一个区间，在最终方案里就只能合成为一段，只需考虑非交换部分只含一个区间的情形。所以要枚举的前后缀对只有k-2个，对中间的每个区间O(n)贪心。O(n)。
=== H ===
考虑对一个子矩阵中的一种数，用pair(x, y)最小的一个数用于统计。可以枚举一个数a[i][j]，然后枚举其所在子矩阵的上边沿k。子矩阵的左边界受到k..i行左侧同类数的约束，右边界受到k..i-1行右侧同类数的约束，下边沿则不受约束。可以按列j=1..m的顺序处理每个数，维护当前每种数在每行最右的出现位置，再预处理nex[i][j]表示右侧的同类数就可以快速更新约束。O(n^3^)。

D

可以用数论中常见的n^0.5优化方法优化，即考虑每次取出的序列的长度，不同长度只有n^0.5，将相同长度合并处理。O(n^0.5)。

E

首先不考虑交换情况下贪心分段，选其中一段用交换来增加段数。假设某段长l，用1..l表示数字。该段中有k个符合要求的前缀，内部排序后分别是[a_k,l], [a_{k-1}, l], .., [1, l]。那么整段相当于被分为k个区间，内部排序后是[a_k, l], [a_{k-1}, a_k-1], .., [1, a_2-1]。贪心策略是选取一个前缀和一个后缀组成用于交换的两段，其余部分尽可能多分段。注意到如果中间的非交换部分包含不止一个区间，在最终方案里就只能合成为一段，只需考虑非交换部分只含一个区间的情形。所以要枚举的前后缀对只有k-2个，对中间的每个区间O(n)贪心。O(n)。

H

考虑对一个子矩阵中的一种数，用pair(x, y)最小的一个数用于统计。可以枚举一个数a[i][j]，然后枚举其所在子矩阵的上边沿k。子矩阵的左边界受到k..i行左侧同类数的约束，右边界受到k..i-1行右侧同类数的约束，下边沿则不受约束。可以按列j=1..m的顺序处理每个数，维护当前每种数在每行最右的出现位置，再预处理nex[i][j]表示右侧的同类数就可以快速更新约束。O(n³)。