这道题不难发现是一道搜索题 + 找规律题。
首先根据题意，可以发现若矩阵第一行与第一列被确定，那么整个矩阵中的元素也就能被一一确定。所以每个元素很可能可以根据第一行与第一列上的元素推导出来。需要注意的一点就是 $a[1][1]$ 这个元素，因为它是行与列的相交处。
继续进行推导，设 $s[i][j]$ 表示给定和中的每一项，$a[i][j]$ 表示所求的答案，$f[i][j]$ 表示一个值，即 $f[i][j] = s[i][j] - f[i - 1][j] - f[i][j - 1] - f[i - 1][j - 1]$。
则有：
因此，我们想要确定一个字典序最小的矩阵，只需要每一行的行首最小。记录的时候可以根据每一个位置的答案范围来记录 ($l-r$)。
完整代码就不给了，放个伪代码吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
int work (int x,int y,int value)
{
if (x % 2 == 1) value += s[1][y];
else value -= s[1][y];
if (y % 2 == 1) value += s[x][1];
else value -= s[x][1];
if ((x + y) % 2 == 1) value += s[1][1];
else value -= s[1][1];
}
bool dfs (int x)
{
for (int i = 0;i < p;++i)
{
s[1][x] = i;
bool ok = 1;
for (int j = 2;j <= n;++j)
{
int tmp = work (j,x,a[j][x]);
if (x % 2 == 1)
{
dx[x][j] = max (dx[x - 1][j],-tmp);
dy[x][j] = min (dy[x - 1][j],p - 1 - tmp);
}
else
{
dx[x][j] = max (dx[x - 1][j],tmp + 1 - p);
dy[x][j] = min (dy[x - 1][j],tmp);
}
if (dx[x][j] >= p || dx[x][j] > dy[x][j])
{
ok = 0;
break;
}
}
}
}
|
