P11836 [USACO25FEB] Reflection B

题目描述

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

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

.#..
.#..
.##.
....

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

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

然而，当 FJ 熟睡时，Bessie 闯入了他的牛棚，偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格，同时添加了某些涂色的单元格！在 FJ 醒来之前，她将画布归还给了 FJ。

FJ 想要修改他的画布，使其再次满足翻转条件：即，它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源，他希望以尽可能少的操作来实现这一点，其中单次操作包括为一个方格涂色或移除一个方格的涂色。

给定 Bessie 破坏后的画布，以及一系列 $U$（$0\le U\le 10^5$）次对画布的更新，每次更新切换单个方格的状态，若它是 ‘#’ 则切换为 ‘.’，反之亦然。在所有更新之前，以及在每次更新之后，输出 FJ 为满足翻转条件所需要执行的最小操作数量 $x$。

输入格式

输入的第一行包含整数 $N$ 和 $U$。

以下 $N$ 行，每行包含 $N$ 个字符，表示 Bessie 破坏后的画布。每个字符均为 # 或 .。

以下 $U$ 行，每行包含整数 $r$ 和 $c$，其中 $1\le r,c\le N$，表示一次对画布从上到下第 $r$ 行，从左到右第 $c$ 列的方格的更新。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

4
3
2
1
0
1

说明/提示

样例 1 解释：

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

....
####
####
....

使用少于 4 次操作使原画布满足翻转条件是不可能的。

在更新 $(1,3)$ 之后，画布看起来是这样的：

....
##.#
####
..##

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

在更新 $(2,3)$ 之后，画布看起来是这样的：

....
####
####
..##

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

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

C++实现

#include<bits/stdc++.h>
using namespace std;
int n,u,x,y,t,ans;
char a[2005][2005];
int main(){
cin>>n>>u;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n/2;i++){
for(int j=1;j<=n/2;j++){
t=0;
if(a[i][j]‘#’)t++;
if(a[n+1-i][j]‘#’)t++;
if(a[i][n+1-j]‘#’)t++;
if(a[n+1-i][n+1-j]‘#’)t++;
ans+=min(t,4-t);
}
}
cout<<ans<<endl;
for(int i=1;i<=u;i++){
cin>>x>>y;
t=0;
if(a[x][y]‘#’)t++;
if(a[n+1-x][y]‘#’)t++;
if(a[x][n+1-y]‘#’)t++;
if(a[n+1-x][n+1-y]‘#’)t++;
ans-=min(t,4-t);
if(a[x][y]‘#’)a[x][y]=‘.’;
else a[x][y]=‘#’;
t=0;
if(a[x][y]‘#’)t++;
if(a[n+1-x][y]‘#’)t++;
if(a[x][n+1-y]‘#’)t++;
if(a[n+1-x][n+1-y]==‘#’)t++;
ans+=min(t,4-t);
cout<<ans<<endl;
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容