Reflection

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

把关于水平和竖直中线对称的四个格子分成一组，单点翻转时只更新这一组的贡献。

OJ: usaco

题目 ID: 1491

难度:普及-

标签:模拟计数

日期: 2026-07-11 12:15

题意

有一张 $N \times N$ 的画布， $N$ 是偶数。

合法画布要求：它可以由某一个象限的图案，通过关于水平中线和竖直中线翻折得到。

换句话说，对于任意一个格子，它与上下、左右翻折后对应的格子必须最终全部相同。

现在给出一张被修改过的画布，并给出若干次单点翻转操作。需要在初始状态以及每次翻转后，输出让画布重新合法所需的最少修改次数。

思路

暴力想法

每个格子都属于一个关于水平中线、竖直中线对称的四元组。

对于代表元 (r,c)，这一组 4 个位置是：

(r,c),\;(n+1-r,c),\;(r,n+1-c),\;(n+1-r,n+1-c)

如果这一组里有 cnt 个 #，那么：

全部改成 .，需要改 cnt 个；
全部改成 #，需要改 4-cnt 个。

所以这一组的最小代价是 min(cnt, 4-cnt)。

每次更新后重新扫描所有四元组，就能得到一个朴素解：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:15
 * update_at: 2026-07-11 12:20
 */
// brute.cpp：小数据暴力解，每次更新后重新扫描所有对称四元组。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, q;
char a[MAXN][MAXN];

int calc_one(int r, int c) {
    int cnt = 0;
    if (a[r][c] == '#') cnt++;
    if (a[n + 1 - r][c] == '#') cnt++;
    if (a[r][n + 1 - c] == '#') cnt++;
    if (a[n + 1 - r][n + 1 - c] == '#') cnt++;
    return min(cnt, 4 - cnt);
}

int calc_answer() {
    int ans = 0;
    int h = n / 2;
    for (int r = 1; r <= h; r++) {
        for (int c = 1; c <= h; c++) {
            ans += calc_one(r, c);
        }
    }
    return ans;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            a[i][j] = s[j - 1];
        }
    }

    cout << calc_answer() << '\n';
    for (int i = 1; i <= q; i++) {
        int r, c;
        cin >> r >> c;
        a[r][c] = (a[r][c] == '#') ? '.' : '#';
        cout << calc_answer() << '\n';
    }

    return 0;
}

这个暴力每次更新都要扫描 $O(N^2)$ 个格子。数据范围里 $U$ 很大，所以需要利用“每次只翻转一个格子”这个条件。

增量维护

把格子 (r,c) 映射到它所在四元组的代表元：

gr = \min(r,\;n+1-r),\quad gc = \min(c,\;n+1-c)

维护 cnt[gr][gc]，表示这一组中有多少个 #。

全局答案就是所有组的代价之和：

ans = \sum \min(cnt[gr][gc],\;4-cnt[gr][gc])

一次翻转 (r,c) 只会影响它所在的这一组。更新时按照下面的顺序做：

text

1
2
3减去这一组旧代价
翻转 a[r][c]，更新 cnt[gr][gc]
加上这一组新代价

这样每次更新只做 $O(1)$ 次计算。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:15
 * update_at: 2026-07-11 12:20
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

int n, q;
char a[MAXN][MAXN];
int cnt[MAXN][MAXN]; // 每个对称四元组里的 '#' 数量
long long ans;

int group_row(int r) {
    // 映射到上下对称后的代表行。
    return min(r, n + 1 - r);
}

int group_col(int c) {
    // 映射到左右对称后的代表列。
    return min(c, n + 1 - c);
}

int cost(int x) {
    // 一个四元组里有 x 个 '#': 要么全部变 '#', 要么全部变 '.'。
    return min(x, 4 - x);
}

void add_cell(int r, int c) {
    if (a[r][c] == '#') {
        int gr = group_row(r);
        int gc = group_col(c);
        cnt[gr][gc]++;
    }
}

void read_input() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            a[i][j] = s[j - 1];
            add_cell(i, j);
        }
    }

    int h = n / 2;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= h; j++) {
            ans += cost(cnt[i][j]);
        }
    }
}

void toggle_cell(int r, int c) {
    // 单点翻转只会改变它所在的一个对称四元组。
    int gr = group_row(r);
    int gc = group_col(c);

    ans -= cost(cnt[gr][gc]);
    if (a[r][c] == '#') {
        a[r][c] = '.';
        cnt[gr][gc]--;
    } else {
        a[r][c] = '#';
        cnt[gr][gc]++;
    }
    ans += cost(cnt[gr][gc]);
}

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

    read_input();

    cout << ans << '\n';
    for (int i = 1; i <= q; i++) {
        int r, c;
        cin >> r >> c;
        toggle_cell(r, c);
        cout << ans << '\n';
    }

    return 0;
}

复杂度

初始化需要扫描整张图，时间复杂度 $O(N^2)$ 。

每次更新只处理一个四元组，时间复杂度 $O(1)$ 。

总时间复杂度 $O(N^2+U)$ ，空间复杂度 $O(N^2)$ 。

总结

这题的关键是不要把整张画布当成一个整体处理，而是拆成互不影响的对称四元组。

每组只有 4 个格子，最优修改次数就是 min(cnt,4-cnt)。单点翻转只影响一组，所以维护每组 # 数量后，就可以快速更新全局答案。

1491 Reflection

赛事信息

USACO 2025 February Contest, Bronze

题目描述

Farmer John 有一块正方形画布，由一个 $N$ 行 $N$ 列的方阵表示（ $2 \leq N \leq 2000$ ， $N$ 为偶数）。他按照以下步骤来绘制画布：

首先，他将画布分成四个等大的象限，由通过画布中心的水平和垂直直线分隔。
其次，他在画布的右上象限中绘制了一幅美丽的画作。右上象限的每个方格或者被涂色（以 ‘#’ 表示），或者未被涂色（以 ‘.’ 表示）。
最后，由于他对自己的画作感到非常自豪，他将其沿此前提到的水平和垂直直线翻转到画布的其他象限中。例如，假设 $N=8$ ，且 FJ 在步骤 2 中于右上象限绘制了以下画作：

text

1
2
3
4
5
.#..
.#..
.##.
....

在步骤 3 中沿水平和垂直直线翻转过后，画布将如下所示：

text

1
2
3
4
5
6
7
8
9
..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

然而，当 FJ 熟睡时，Bessie 闯入了他的牛棚，偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格，同时添加了某些涂色的单元格！在 FJ 醒来之前，她将画布归还给了 FJ。 FJ 想要修改他的画布，使其再次满足翻转条件：即，它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源，他希望以尽可能少的操作来实现这一点，其中单次操作包括为一个方格涂色或移除一个方格的涂色。给定 Bessie 破坏后的画布，以及一系列 $U$ （ $0\le U \leq 10^5$ ）次对画布的更新，每次更新切换单个方格的状态，若它是 ‘#’ 则切换为 ‘.’，反之亦然。在所有更新之前，以及在每次更新之后，输出 FJ 为满足翻转条件所需要执行的最小操作数量 $x$ 。

输入格式

输入的第一行包含整数 $N$ 和 $U$ 。以下 $N$ 行，每行包含 $N$ 个字符，表示 Bessie 破坏后的画布。每个字符均为 ‘#’ 或 ‘.’。以下 $U$ 行，每行包含整数 $r$ 和 $c$ ，其中 $1 \leq r, c \leq N$ ，表示一次对画布从上到下第 $r$ 行，从左到右第 $c$ 列的方格的更新。

输出格式

输出 $U+1$ 行，为在所有更新之前以及在每次更新之后的 $x$ 。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
104 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

输出 #1

text

样例说明

以下画布满足翻转条件，并且可由原画布经过 4 次操作得到：

text

1
2
3
4
5
....
####
####
....

使用少于 4 次操作使原画布满足翻转条件是不可能的。在更新 $(1, 3)$ 之后，画布看起来是这样的：

text

1
2
3
4
5
....
##.#
####
..##

现在需要 3 次操作使画布满足翻转条件。在更新 $(2, 3)$ 之后，画布看起来是这样的：

text

1
2
3
4
5
....
####
####
..##

现在需要 2 次操作使画布满足翻转条件。

测试点性质

测试点 2-3： $N \le 4$ 。
测试点 4-6： $U \le 10$ 。
测试点 7-16：没有额外限制。

Reflection

目录

题意

思路

暴力想法

增量维护

代码

复杂度

总结