Description
![](/blog/bzoj2003/bzoj2003.png)
Input
第一行包含三个正整数 \(n, m, p\), 表示矩阵的行数列数以及每个数的范围, 接下来 \(n\) 行每行包含 \(m\) 个非负整数, 其中第 \(i\) 行第 \(j\) 个数表示以格子 \((i, j)\) 为右下角的 \(2 \times 2\) 子矩阵中的数的和. 保证第一行与第一列的数均为 \(0\), 且每个和都不超过 \(4(p-1)\).
Output
包含 \(n\) 行, 每行 \(m\) 个整数, 描述你求出的矩阵, 相邻的整数用空格分开. (行末不要有多余空格)
Sample Input
3 3 3
0 0 0
0 4 5
0 5 3
Sample Output
0 0 2
2 2 1
1 0 0
Data Range
对于所有数据, 满足:\(1 \leq n, m \leq 200, 1 \lt p \leq 10\)
Explanation
不停地出矩阵瞎搞而且连标题都没有变是要怎样......
而且行尾不要输出多余空格!! !
然而这道题并不会做, 看上去以为是一道瞎搞搜索, 结果一看题解果然是神搜索. 然而那种 奇怪的推断函数并没有弄明白, 所以就直接贴题解 (然而最后的复杂度分析我也是醉了):
原文链接:http://www.cnblogs.com/yangjiyuan/p/5321082.html
首先可以知道, 如果已知第一行和第一列的数, 那么可以很容易的计算出其余的数. 进一步的, 如果笔算将每个数的表达式写出可以得出如下结论:
第 \(i\) 行的第 \(j\) 个数 (\(i \gt 1, j \gt 1\)) 只与 \((1, 1), (i, 1), (1, j)\) 有关
更数学化地说, 设输入矩阵为 \(S\), 定义 \(C\) 如下:
\[C_{i,j} = \begin{cases} 0 & i = 1\ \text{or}\ j = 1\\ S_{i,j} - C_{i,j-1} - C_{i-1,j} - C_{i-1,j-1} & \text{else} \end{cases}\]
则原矩阵 \(A\) 的第 \(i\) 行的第 \(j\) 个数可按下式确定:
\[A_{i,j} = f(i) \cdot A_{i,1} + f(j) \cdot A_{1,j} - f(i) \cdot f(j) \cdot A_{1,1} + C_{i,j} (i \gt 1\ \text{and}\ j \gt 1)\]
\[f(x) = \begin{cases} 1 & (x \bmod 2 = 1)\\ -1 & (x \bmod 2 = -1) \end{cases}\]
算法一:
直接利用该结论, 枚举第一行和第一列的每个数, 从而求出剩下所有数, 并判断是否符合要求. 时间复杂度 \(O(n \cdot m \cdot p^{n+m-1})\), 较好的实现可以通过 30% 的数据.
算法二:
考虑 \(p=2\) 的情况, 每个格子只有两种取值 0/1. 首先枚举 \((1,1)\), 那么第一行某个格子 \((1,j)\) 与第一列某个格子 \((i,1)\) 唯一确定了格子 \((i,j)\), 若 \((1,j)=x\) 且 \((i,1)=y\) 时 \((i,j)\) 的取值不合法, 则 \((1,j)\) 取 \(x\) 和 \((i,1)\) 取 \(y\) 不能同时发生.
这是经典的 2-SAT 模型, 虽然使用拓扑排序可以在 \(O(n \cdot m)\) 的时间内求出一个可行解, 但无法求出字典序最小解. 这里应使用枚举算法, 按字典序的优先级判断每一个点, 若该点的取值未确定, 先尝试放 \(0\), 看是否产生矛盾, 无矛盾则确定为 \(0\) 否则改为 \(1\). 该算法的时间复杂度为 \(O((n+m) \cdot n \cdot m)\), 较好的实现可以通过 30% 的数据.
算法三:
结合算法一与算法二可以通过 60% 的数据.
算法四:
对于一般的情况, 2-SAT 模型并不适用, 但可以尝试将算法二稍做修改. 即每次从 \(0\) 到 \(p-1\) 枚举取值, 找到最小的且不与前面产生矛盾的确定为该格的值. 遗憾的是, 该算法是 错误的, 很多时候这样做甚至会丢失可行解! 为了避免这种情况, 可以使用 DFS 算法.
具体来说, 依次枚举第一行每个格子的取值, 每次枚举后判断第一列每个格子是否均有可行的取值, 若没有则退出, 否则继续枚举下一个格子. 若第一行的格子均已确定, 则第一列的每个格子直接取可行取值中最小的即可.
由于数据保证有解, 对于矩阵较大的情况, 解很多, 限制很多, 搜索树的宽度很小, 而矩阵较小时搜索树深度很小, 均可以较快的得出答案. 更进一步的, 在矩阵较大时, 基本上不会有回溯的情况, 即时间复杂度约等于 \(O(n \cdot m \cdot p^2)\), 可以通过所有测试数据.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long lli;
const int maxn = 210;
int even(int in) {
return (in & 1) ? -1 : 1; }
int odd(int in) {
return (in & 1) ? 1 : -1; }
int n, m, p;
int arr[maxn][maxn], // Initial array, read-only
comp[maxn][maxn], // Values need to be added to this location
vmn[maxn][maxn], // Minimum allowed value at location
vmx[maxn][maxn], // Maximum allowed value at location
res[maxn][maxn]; // Final result
bool dfs(int j)
{
// Construction complete.
if (j > m)
return true;
// Leftmost value in this row.
for (int k = 0; k < p; k++) {
bool satisfy = true;
res[1][j] = k;
// Checking for satisfaction at this row.
for (int i = 2; i <= n; i++) {
int tmp_1 = (comp[i][j] + res[1][1] * even(i+j+1) + res[1][j] *
odd(i)) * even(j),
tmp_2 = (comp[i][j] + res[1][1] * even(i+j+1) + res[1][j] *
odd(i) - p + 1) * even(j);
if (tmp_1 > tmp_2)
swap(tmp_1, tmp_2);
vmn[i][j] = max(vmn[i][j-1], tmp_1);
vmx[i][j] = min(vmx[i][j-1], tmp_2);
if (vmn[i][j] > vmx[i][j]) {
satisfy = false;
break;
}
}
if (satisfy && dfs(j+1))
return true;
}
return false;
}
int main(int argc, char** argv)
{
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &arr[i][j]);
vmx[i][j] = p - 1;
}
for (int i = 2; i <= n; i++)
for (int j = 2; j <= m; j++)
comp[i][j] = arr[i][j] - (comp[i-1][j-1] + comp[i-1][j] + comp[i][j-1]);
// Attempting to create first level, by searching
// and iterate the rest with searching, no cuts
for (int init_val = 0; init_val < p; init_val++) {
res[1][1] = init_val;
// Given the case that search completes, save the results
if (dfs(2)) {
for (int i = 2; i <= n; i++)
res[i][1] = vmn[i][m];
for (int i = 2; i <= n; i++)
for (int j = 2; j <= m; j++)
res[i][j] = comp[i][j] + odd(j) * res[i][1] + odd(i) *
res[1][j] + even(i+j+1) * res[1][1];
break;
}
}
// Output result, and such a result is guranteed
// And the format is really devastating
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
printf("%d%s", res[i][j], j == m ? "\n" : " ");
return 0;
}