「SOL」矩阵游戏 (2021省选A卷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」矩阵游戏 (2021省选A卷)

发表于 分类于 Valine：

考前感觉啥都复习了
考后感觉啥啥都不会

# 题面

> Link 洛谷 P7515

# 解析

最难处理的是 $a_{ij}$ 有 $[0,10^6]$ 的限制（因为有这个限制所以我 $n,m\le3$ 都不会做……）。

假如没有这个限制，显然我们可以随便构造出一组解 $\{a’_{ij}\}$，下面给出一种构造方法：

  • 固定最后一行和最后一列都是 $0$；
  • 从下到上从左到右依次确定 $a’_{ij}$（不需要满足范围限制，注意会爆 int）

然后考虑如何把 $\{a’_{ij}\}$ 修修补补使它满足范围限制。

这里的构造非常巧妙，我们可以将第 $i$ 行的偶数列加上 $p_i$，奇数列减去 $p_i$，这样操作后每一个 $2\times2$ 的矩形的和都不变；将第 $j$ 列的偶数行加上 $q_j$，奇数行减去 $q_j$ 同理。

于是我们要求：

差不多转化成了下面这种不等式

这个问题似乎也并不好求解，但是我们会用差分约束求解

怎么消除掉“两个变量之和”的不等式？考虑改变我们的构造方式，原本我们构造的方式是

我们发现，在 $i,j$ 奇偶性相同的位置，会出现变量之和的限制，于是我们稍作调整：

不难发现，这样构造仍然可以让 $2\times2$ 的矩形和不变。而这样构造的好处就在于，对应位置的正负性总相反。

然后就可以非常愉快地差分约束。

如果有负环就无解。有负权边，跑 SPFA？反正我会被卡常，看题解发现可以直接 bellman-ford，而且因为是完全二分图，可以用邻接矩阵存边。

跑得特别慢……

最后还有一点小问题。为什么这样是对的呢？我们感觉这个算法看起来就非常对…… 给出一个不是很严谨的证明。

证明

起初对这道题有一个非常暴力的想法：如果确定了 $\{a_{ij}\}$ 的最后一行和最后一列，那么可以唯一确定矩阵 $\{a_{ij}\}$（在忽略范围限制的前提下）。也就是说，我们可以用最后一行、最后一列代表一个矩阵。

假设存在合法解 $\{a_{ij}\}$，那么通过 $a_{im}\pm p_i$ 和 $a_{nj}\pm q_j$，可以得到任意一种 $a'_{im},a'_{nj}$，也即可以得到任意一种不符合范围限制的矩阵 $\{a'_{ij}\}$。

为什么会存在多解呢？因为实际上最后一行和最后一列只能提供 $n+m-1$ 个方程，而我们有 $n+m$ 个变量。

# 源代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*Lucky_Glass*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long llong;
const int N = 305, M = N * N, B = 1e6;
const llong INF = 0x3f3f3f3f3f3f3f3fll;
#define con(typ) const typ &
inline int rin(int &r) {
	int b = 1, c = getchar(); r = 0;
	while ( c < '0' || '9' < c ) b = c == '-' ? -1 : b, c = getchar();
	while ( '0' <= c && c <= '9' ) r = (r * 10) + (c ^ '0'), c = getchar();
	return r *= b;
}
void write(con(int) w) {
	if ( w < 0 ) putchar('-'), write(-w);
	else if ( w < 10 ) putchar('0' + w);
	else write(w / 10), putchar('0' + w % 10);
}

int n, m, nedg;
int mtb[N][N];
llong mta[N][N], edga[N][N], edgb[N][N];
llong dis[N << 1];

bool relax(con(int) u, con(llong) len, con(int) v) {
	if ( dis[v] > dis[u] + len ) {
		dis[v] = dis[u] + len;
		return true;
	}
	return false;
}
bool bellmanFord() {
	int cnt = 0; bool tag = false;
	for (int i = 1; i <= n + m; i++)
		dis[i] = 0;
	do {
		cnt++, tag = false;
		if ( cnt >= n + m ) return false;
		for (int u = 1; u <= n + m; u++)
			if ( u <= n )
				for (int v = 1; v <= m; v++)
					tag |= relax(u, edga[u][v], v + n);
			else
				for (int v = 1; v <= n; v++)
					tag |= relax(u, edgb[u - n][v], v);
	} while ( tag );
	return true;
}
void clean() {
	nedg = 0;
	fill(dis, dis + n + m + 1, INF);
}
int main() {
	int ncas; rin(ncas);
	while ( ncas-- ) {
		rin(n), rin(m);
		clean();
		for (int i = 1; i < n; i++)
			for (int j = 1; j < m; j++)
				rin(mtb[i][j]);
		for (int i = n; i; i--)
			for (int j = m; j; j--)
				if ( i == n || j == m ) mta[i][j] = 0;
				else mta[i][j] = mtb[i][j] - mta[i + 1][j + 1]
							   - mta[i + 1][j] - mta[i][j + 1];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if ( (i & 1) ^ (j & 1) )
					edga[i][j] = mta[i][j], edgb[j][i] = B - mta[i][j];
				else
					edgb[j][i] = mta[i][j], edga[i][j] = B - mta[i][j];
		if ( !bellmanFord() ) {printf("NO\n"); continue;}
		printf("YES\n");
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				llong now = mta[i][j];
				if ( (i & 1) ^ (j & 1) ) now += dis[i] - dis[j + n];
				else now += dis[j + n] - dis[i];
				write((int)now), putchar(j == m ? '\n' : ' ');
			}
	}
	return 0;
}

THE END

Thanks for reading!

你走吧 趁着天色未暗
你走吧 深知道阻且难
我献上明月一盏 照满河山

——《山遥路远（人声本家）》By ChiliChill

PS. 省选之后再听这首歌又有不一样的感动，似乎是我将此歌唱给谁人，又像是谁人唱予我。