# [HNOI2010]MATRIX 矩阵

2018/03/13 19:25

3 3 3
0 0 0
0 4 5
0 5 3

0 0 2
2 2 1
1 0 0

## HINT

1<=N,M<=200

1<P<=10

(此时A中可能有负数或者大于等于P的整数)

`````` 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 中可能有负数或者大于等于 P 的整数)
S:
0 0 0
0 4 5
0 5 3A:
0 0 0
0 4 1
0 1 -3

A’: A 1,1 +=1
1 -1 1
-1 5 0
1 0 -2

A’: A 1,2 +=1
0 1 0
0 3 1
0 2 -3

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)

0
0 收藏

0 评论
0 收藏
0