[HNOI2010]MATRIX 矩阵

2018/03/13 19:25
阅读数 13

Description

Input

第一行包含三个正整数N M P表示矩阵的行数列数以及每个数的范围,接下来N行每行包含M个非负整数,其中第i行第j个数表示以格子(i,j)为右下角的2*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

HINT

1<=N,M<=200

1<P<=10

首先可以推出,一旦A的第一行与第一列已经确定,那么我们就可以按部就班地
算出A的所有元素的值了。这样一来需要决策的元素个数就从$200^{2}$变成了399
首先不看元素在0到P-1范围内的限制,设A(1,k)和A(k,1)都为0,并计算将A补全。
(此时A中可能有负数或者大于等于P的整数)
这样A中有些值不符合条件,调整A矩阵
当我们改变A(1,1)+=k时,
要把A调整成合法矩阵,事实上只需把i+j为偶数的A(i,j)
全部增加 k,i+j为奇数的 A(i,j)全部减去 k 即可
当我们把A(1,i)增加k时,要把A调整成合法,只需要把第i列奇数位加k,偶数位减k即可。
我们只需要搜索A的第一行,每当确定一个元素,就可以更新A(j,1)的取值范围。
根据公式,除了A(1,1)以外,A(i,1)的取值是互不影响的。
不断更新第一列每个元素的可以取值的范围,一旦出现有某个元素下界大于上界的情况就剪枝
显然这样搜索的字典序是最优的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 int l[301][301],r[301][301],a[301][301],s[301][301],c[301][301],n,m,p;
 8 int pd(int x)
 9 {
10   if (x&1) return -1;
11   return 1;
12 }
13 int get_num(int x,int y)
14 {
15   return c[x][y]-pd(x+y)*a[1][1]-pd(x)*a[1][y]-pd(y)*a[x][1];
16 }
17 bool dfs(int x)
18 {int k,i,j,ok;
19   if (x>m) return 1;
20   for (k=0;k<p;k++)
21     {
22       ok=1;
23       a[1][x]=k;
24       for (i=2;i<=n;i++)
25     {
26       int rl=(c[i][x]-pd(x+i)*a[1][1]-pd(i)*a[1][x])*(pd(x));
27       int rr=(c[i][x]-pd(x+i)*a[1][1]-pd(i)*a[1][x]-(p-1))*(pd(x));
28       if (rl>rr) swap(rl,rr);
29       l[i][x]=max(l[i][x-1],rl);
30       r[i][x]=min(r[i][x-1],rr);
31       if (l[i][x]>r[i][x])
32         {
33           ok=0;
34           break;
35         }
36     }
37     if (ok&&dfs(x+1)) return 1;
38     }
39   return 0; 
40 }
41 int main()
42 {int i,j,k;
43   cin>>n>>m>>p;
44   for (i=1;i<=n;i++)
45     {
46       for (j=1;j<=m;j++)
47     {
48       scanf("%d",&s[i][j]);
49       l[i][j]=0;r[i][j]=p-1;
50     }
51     }
52   for (i=2;i<=n;i++)
53     {
54       for (j=2;j<=m;j++)
55     {
56       c[i][j]=s[i][j]-c[i-1][j]-c[i][j-1]-c[i-1][j-1];
57     }
58     }
59   for (i=0;i<p;i++)
60     {
61       a[1][1]=i;
62       if (dfs(2))
63     {
64       for (j=2;j<=n;j++)
65         {
66           a[j][1]=l[j][m];
67         }
68       for (j=2;j<=n;j++)
69         {
70           for (k=2;k<=m;k++)
71         a[j][k]=get_num(j,k);
72         }
73       break;
74     }
75     }
76   for (i=1;i<=n;i++)
77     {
78       for (j=1;j<m;j++)
79     {
80       printf("%d ",a[i][j]);
81     }
82       printf("%d",a[i][m]);
83       printf("\n");
84     }
85 }

 

首先可以推出,一旦 A 的第一行与第一列已经确定,那么我们就可以按部就班地
算出 A 的所有元素的值了。这样一来需要决策的元素个数就从 200 2 变成了 399。
为了方便计算,我们试图建立 A i,j 与第一行或第一列之间的直接等式关系。
以下是一个较易理解的建立等量关系的方法:
首先不看元素在 0 到 P-1 范围内的限制,设 A 1,k 和 A k,1 都为 0,并计算将 A 补全。
(此时 A 中可能有负数或者大于等于 P 的整数)
S:
0 0 0
0 4 5
0 5 3A:
0 0 0
0 4 1
0 1 -3
当我们改变 A 1,1 +=k 时,
要把 A 调整成合法矩阵,事实上只需把 i+j 为偶数的 A i,j
全部增加 k,i+j 为奇数的 A i,j 全部减去 k 即可。
A’: A 1,1 +=1
1 -1 1
-1 5 0
1 0 -2
当我们把 A 1,i 增加 k 时,要把 A 调整成合法,只需要把第 i 列奇数位加 k,偶数位
减 k 即可。
A’: A 1,2 +=1
0 1 0
0 3 1
0 2 -3
修改 A i,1 类似。
设通过令第一行第一列都为 0 得到的矩阵为 C,
那么有公式:
A i,j = C i,j + (-1) i+j-2 A 1,1 + (-1) i-1 A 1,j + (-1) j-1 A i,1
(i>1,j>1)
接下来只需要考虑对第一行第一列进行决策即可。
前 30%的数据可以搜索解决。
另 30%实际上是一个 2-Sat.问题。参见 SGU 307 Cipher。
对于 100%的数据并没有很好的方法。
研究 30%的搜索方法,如果加入较强的剪枝,一般出解是很快的。
我们只需要搜索 A 的第一行,每当确定一个元素,就可以更新 A j,1 的取值范围。
根据公式,除了 A 1,1 以外,A i,1 的取值是互不影响的。
不断更新第一列每个元素的可以取值的范围,一旦出现有某个元素下界大于上界的
情况就剪枝。
显然这样搜索的字典序是最优的。
事实证明这个剪枝效率非常高。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部