bzoj2003: [Hnoi2010]Matrix 矩阵 | jeffswt: the ac moments

Description

Input

第一行包含三个正整数 $n, m, p$ , 表示矩阵的行数列数以及每个数的范围, 接下来 $n$ 行每行包含 $m$ 个非负整数, 其中第 $i$ 行第 $j$ 个数表示以格子 $(i, j)$ 为右下角的 $2 \times 2$ 子矩阵中的数的和. 保证第一行与第一列的数均为 $0$ , 且每个和都不超过 $4(p-1)$ .

Output

包含 $n$ 行, 每行 $m$ 个整数, 描述你求出的矩阵, 相邻的整数用空格分开. (行末不要有多余空格)

Sample Input

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;
}