[ZYOI Round1] Chessboard game/棋盘游戏

GitHub 跳转原题关系图返回列表

把 L 形棋盘按黑白染色后，任意一次操作都会同时改动一黑一白，因此带符号和不变，可直接解出缺失值。

OJ: luogu

题目 ID: P8050

难度:普及+/提高

标签:图论二分图思维

日期: 2026-06-18 21:58

题意

给出一个 L 形棋盘。初始时所有格子的值都等于 k。
每次操作可以选择两个相邻格子，把它们同时 +1 或同时 -1。

现在给出若干次操作后的棋盘，但其中恰好有一个位置被写成 999999。
题目要我们求出这个缺失格子的真实值。

思路

先看一个可以直接验证想法的朴素解：

因为题目保证最终每个格子的值都在 [-1000,1000]，所以可以直接枚举缺失值 x：

把 x 填回去；
计算整张棋盘的“黑格和减白格和”；
如果它和初始棋盘一致，那么这个 x 就是答案。

cpp

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
88
89
90
91
92// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 205;

int n1, m1, n2, m2, k;
int top_rows;
int total_rows;
int a[MAXN][MAXN];
int miss_x, miss_y;

int row_len(int row) {
    if (row <= top_rows) {
        return m1;
    }
    return m2;
}

int cell_sign(int row, int col) {
    if ((row + col) % 2 == 0) {
        return 1;
    }
    return -1;
}

void read_input() {
    cin >> n1 >> m1 >> n2 >> m2 >> k;
    if (n1 > 0 && m1 > 0) {
        top_rows = n1;
    } else {
        top_rows = 0;
    }
    total_rows = top_rows + n2;

    miss_x = miss_y = 0;
    for (int i = 1; i <= total_rows; i++) {
        int len = row_len(i);
        for (int j = 1; j <= len; j++) {
            cin >> a[i][j];
            if (a[i][j] == 999999) {
                miss_x = i;
                miss_y = j;
            }
        }
    }
}

// 直接枚举缺失值，检查黑白带符号和是否和初始棋盘一致。
bool check_value(int value) {
    ll sum = 0;
    for (int i = 1; i <= total_rows; i++) {
        int len = row_len(i);
        for (int j = 1; j <= len; j++) {
            int cur = a[i][j];
            if (i == miss_x && j == miss_y) {
                cur = value;
            }
            sum += 1LL * cell_sign(i, j) * cur;
        }
    }

    ll target = 0;
    for (int i = 1; i <= total_rows; i++) {
        int len = row_len(i);
        for (int j = 1; j <= len; j++) {
            target += 1LL * cell_sign(i, j) * k;
        }
    }
    return sum == target;
}

void solve() {
    for (int value = -1000; value <= 1000; value++) {
        if (check_value(value)) {
            cout << value << '\n';
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

关键在于，为什么只检查这个带符号和就够了？

先把棋盘像普通国际象棋一样黑白染色。对样例来说，可以给每个格子赋这样的符号：

行\列	1	2	3	4
1	`+`	`-`	`×`	`×`
2	`-`	`+`	`×`	`×`
3	`+`	`-`	`+`	`-`
4	`-`	`+`	`-`	`+`
5	`+`	`-`	`+`	`-`

这里 × 表示这一格不存在。
由于每次操作总是作用在两个相邻格子上，而相邻格子的符号一定一正一负，所以一次操作对

S = 所有格子的符号 × 数值之和

的影响永远是 0。

这就说明 S 是不变量。
初始时所有格子都等于 k，所以初始不变量 S0 可以直接算出来。

设缺失位置的符号是 sgn，其他已知格子的带符号和是 sum_known，那么最后状态必须满足：

sum_known + sgn × x = S0

于是直接解得：

x = sgn × (S0 - sum_known)

正式代码就是按这个式子一步算出答案。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 205;

int n1, m1, n2, m2, k;
int top_rows;
int total_rows;
int a[MAXN][MAXN];
int miss_x, miss_y;

int row_len(int row) {
    if (row <= top_rows) {
        return m1;
    }
    return m2;
}

int cell_sign(int row, int col) {
    if ((row + col) % 2 == 0) {
        return 1;
    }
    return -1;
}

void read_input() {
    cin >> n1 >> m1 >> n2 >> m2 >> k;

    // 上面的小矩形只在 n1,m1 都大于 0 时才真正存在。
    if (n1 > 0 && m1 > 0) {
        top_rows = n1;
    } else {
        top_rows = 0;
    }
    total_rows = top_rows + n2;

    miss_x = miss_y = 0;
    for (int i = 1; i <= total_rows; i++) {
        int len = row_len(i);
        for (int j = 1; j <= len; j++) {
            cin >> a[i][j];
            if (a[i][j] == 999999) {
                miss_x = i;
                miss_y = j;
            }
        }
    }
}

void solve() {
    ll target = 0;     // 初始棋盘的黑白带符号和
    ll known_sum = 0;  // 除缺失值外，当前棋盘的带符号和

    for (int i = 1; i <= total_rows; i++) {
        int len = row_len(i);
        for (int j = 1; j <= len; j++) {
            int sgn = cell_sign(i, j);
            target += 1LL * sgn * k;
            if (i == miss_x && j == miss_y) {
                continue;
            }
            known_sum += 1LL * sgn * a[i][j];
        }
    }

    int sgn = cell_sign(miss_x, miss_y);
    ll ans = 1LL * sgn * (target - known_sum);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

设棋盘总格子数为 N，正式做法只扫描一遍棋盘，所以时间复杂度是 $O(N)$ ，空间复杂度是 $O(N)$ 。

总结

这题不是去还原操作过程，而是去找“操作不改变什么”。

一旦看出棋盘相邻关系是二分图，黑白染色后的带符号和就是天然不变量，缺失值也就能直接列式算出来了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8050 [ZYOI Round1] Chessboard game/棋盘游戏

题目背景

子衿有一个游戏棋盘，此时准备拿出来玩玩。

题目描述

她的棋盘是 L 字形的，由上面一个 $n_1 \times m_1$ 的小长方形和下面一个 $n_2 \times m_2$ 的大长方形组成。棋盘初始状态所有格子上的数都为 $k$ 。

比如，当 $n_1 = 2$ ， $m_1 = 2$ ， $n_2 = 3$ ， $m_2 = 4$ ， $k = 0$ 时，棋盘初始是这样的：

text

现在她要进行若干次操作：将相邻的两个格子中的数同时加 $1$ 或减 $1$ 。操作完成后她会记住这些格子上的数。

可是她有一次不小心，经过若干次操作后忘掉了其中某一个数是多少了，于是在上面打了一个 $999999$ 。请你通过编程求出被打上 $999999$ 的数应该是多少。保证有且仅有一个格子被打上了 $999999$ 。

输入格式

第一行输入五个整数 $n_1,m_1,n_2,m_2,k$ ，分别表示组成 L 字形棋盘小长方形的行数和列数，大长方形的行数和列数，以及初始格子上的数。

接下来 $n_1$ 行，每行输入 $m_1$ 个整数，表示操作后的棋盘小长方形中每个格子中的数。

接下来 $n_2$ 行，每行输入 $m_2$ 个整数，表示操作后的棋盘大长方形中每个格子中的数。

未知的数以 $999999$ 代替。

输出格式

一行，一个整数，表示被打上 $999999$ 的数原本的值。

数据保证有解。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
62 2 3 4 0
0 0
1 0
2 1 1 0
0 1 999999 0
0 0 0 0

输出 #1

text

说明/提示

对于 $40\%$ 的数据， $n_1 = m_1 = 0$ 。

对于 $100\%$ 的数据， $m_1 < m_2$ ， $0 \le n_1,m_1,k \le 100$ ， $1 \le n_2,m_2 \le 100$ ，每个格子中的数 $\ge -1000$ 且 $\le 1000$ ，除前 $40\%$ 的数据外剩下的 $60\%$ 的数据保证 $n_1,m_1 > 0$ 。

【样例说明】

一开始棋盘是这样的：

text

下面给出一种可行的操作方案：

先将第 $2$ 行第 $1$ 个数与第 $3$ 行第 $1$ 个数同时加 $1$ ：

text

再将第 $3$ 行第 $1$ 个数与第 $3$ 行第 $2$ 个数同时加 $1$ ：

text

再将第 $3$ 行第 $3$ 个数与第 $4$ 行第 $3$ 个数同时加 $1$ ：

text

最后将第 $4$ 行第 $2$ 个数与第 $4$ 行第 $3$ 个数同时加 $1$ ：

text

可以得出被打上 $999999$ 的数（第 $4$ 行第 $3$ 个数）为 $2$ 。

操作方案可能不唯一，但可以证明答案是唯一的。

[ZYOI Round1] Chessboard game/棋盘游戏

目录

题意

思路

代码

复杂度

总结

一图流解析