「OOI 2016 Day 1」表格压缩 题解

问题分析

我们需要将原表格中的数值重新映射到新的正整数，使得：

• 同一行内相对大小关系保持不变
• 同一列内相对大小关系保持不变
• 映射后的最大值尽可能小

关键观察：

• 如果两个单元格 $a_{i,j}$ 和 $a_{k,l}$ 不在同一行或同一列，它们可以映射到相同的值
• 如果 $a_{i,j} < a_{i,k}$，则 $b_{i,j} < b_{i,k}$
• 如果 $a_{i,j} = a_{i,k}$，则 $b_{i,j} = b_{i,k}$

算法思路

核心思想：图论建模

将每个单元格 $(i,j)$ 看作图中的一个节点，建立偏序关系：

1. 行约束：对于任意 $i \in [1,n]$, $j,k \in [1,m]$：

   • 如果 $a_{i,j} < a_{i,k}$，建立有向边 $(i,j) \rightarrow (i,k)$
   • 如果 $a_{i,j} = a_{i,k}$，合并节点 $(i,j)$ 和 $(i,k)$

2. 列约束：对于任意 $j \in [1,m]$, $i,k \in [1,n]$：

   • 如果 $a_{i,j} < a_{k,j}$，建立有向边 $(i,j) \rightarrow (k,j)$
   • 如果 $a_{i,j} = a_{k,j}$，合并节点 $(i,j)$ 和 $(k,j)$

3. 等价类合并：使用并查集处理相等关系，将必须相等的单元格合并为同一个节点

4. 拓扑排序赋值：在得到的 DAG 上进行拓扑排序，每个节点的值 $dp[u] = \max(1, \max\{dp[v] + 1 \mid v \to u\})$

具体步骤

1. 预处理

• 将 $n \times m$ 表格展平为一维数组，索引函数：$id(i,j) = i \times m + j$
• 初始化并查集，每个单元格独立为一个集合

2. 等价类合并

• 按行处理：对每行 $i$，将值 $a_{i,j}$ 相同的所有单元格 $(i,j)$ 合并到同一等价类
• 按列处理：对每列 $j$，将值 $a_{i,j}$ 相同的所有单元格 $(i,j)$ 合并到同一等价类
• 最终得到等价类集合 $\mathcal{C} = \{C_1, C_2, \ldots, C_k\}$

3. 建立约束图

• 行约束边：对每行排序，在相邻的不同值对应的等价类间建立有向边 $C_p \to C_q$
• 列约束边：对每列排序，在相邻的不同值对应的等价类间建立有向边 $C_p \to C_q$
• 计算每个等价类的入度 $deg[C]$

4. 拓扑排序与动态规划

• 初始化队列 $Q$ 包含所有入度为 $0$ 的等价类，设 $dp[C] = 1$
• 当 $Q$ 非空时：
  • 取出队首 $C$，遍历所有出边 $C \to C'$
  • 更新 $dp[C'] = \max(dp[C'], dp[C] + 1)$
  • $deg[C']$ 减 $1$，若为 $0$ 则入队

5. 输出结果

对于每个单元格 $(i,j)$，输出其所属等价类 $C$ 的 $dp[C]$ 值

复杂度分析

时间复杂度

• 排序：$O(nm \log(\max(n,m)))$
• 并查集：$O(nm \alpha(nm))$
• 建图与拓扑排序：$O(nm)$
• 总复杂度：$O(nm \log(nm))$

空间复杂度

• 存储图结构：$O(nm)$
• 并查集与DP数组：$O(nm)$
• 总空间：$O(nm)$