CF1200D
题意
给你一个n,k,然后给出一个
n*n的矩阵,每个元素是’B’或’W’,你能选择k*k的范围,使范围内所有的’B’变成’W’,然后求一次染色后最多可以有多少条”白线”.白线是指全都为’W’的行和列的数量.
$1<=k,n,<=2000$
思路
题面很简单,就是模拟.
仅仅枚举染色范围的左上角,复杂度就是$O(n^2)$了,如果暴力计算范围内的线的个数,时间显然不够.
我们考虑优化对于每个矩阵,给出涂色区域的左上角,如何快速查询可增加的白线.
首先我们先预处理一下每个行和列.求出其第一个黑块和最后一个黑块的坐标(如果没有就要标记一下,然后记录数量,在之后的过程中忽略,在最后的结果加上)
然后我们不难发现,对于一个确定的染色左上角的坐标和一个确切的行/列的标号,我们可以O(1)直接确定此行/列能否成为白线了.
但是单纯做到这一步的话还是复杂度过高.所以我们考虑迭代计算每个矩形可以增加的白线.举个例子,对于(0,0)和(0,1)两个坐标,实际上只有第0列和第k列会影响他们的差值,所以迭代处理的话可以让复杂度均摊到$O(n^2)$
AC代码
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
#define maxn (int)2100
#define ll long long
#define endl '\n'
int n, k;
int mp[maxn][maxn];
#define pii pair<int, int>
#define fi first
#define se second
pii col[maxn], row[maxn];
bool mcol[maxn], mrow[maxn];
int fans[maxn][maxn];
int fans1[maxn][maxn];
bool checkrow(int x, int y, int id) {
if (mrow[id])
return 0;
if (x <= id && x + k - 1 >= id && y <= row[id].fi &&
y + k - 1 >= row[id].se)
return true;
return false;
}
bool checkcol(int x, int y, int id) {
if (mcol[id])
return 0;
if (y <= id && y + k - 1 >= id && x <= col[id].fi &&
x + k - 1 >= col[id].se)
return true;
return false;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char ch;
cin >> ch;
if (ch == 'B') {
mp[i][j] = 0;
} else {
mp[i][j] = 1;
}
}
}
int pre = 0;
for (int i = 0; i < n; ++i) {
pii tmp = make_pair(-1, -1);
for (int j = 0; j < n; ++j) {
if (mp[i][j] == 0) {
if (tmp.fi == -1) {
tmp.fi = j;
tmp.se = j;
} else {
tmp.se = j;
}
}
}
if (tmp.fi == -1 && tmp.se == -1) {
mrow[i] = 1;
++pre;
}
row[i] = tmp;
}
for (int j = 0; j < n; ++j) {
pii tmp = make_pair(-1, -1);
for (int i = 0; i < n; ++i) {
if (mp[i][j] == 0) {
if (tmp.fi == -1) {
tmp.fi = i;
tmp.se = i;
} else {
tmp.se = i;
}
}
}
if (tmp.fi == -1 && tmp.se == -1) {
mcol[j] = 1;
++pre;
}
col[j] = tmp;
}
for (int i = 0; i < n - k + 1; ++i) {
int ans = 0;
for (int j = 0; j < k; ++j) {
if (checkcol(i, 0, j)) {
++ans;
}
}
fans[i][0] = ans;
for (int j = k; j < n; ++j) {
if (checkcol(i, j - k, j - k)) {
--ans;
}
if (checkcol(i, j, j)) {
++ans;
}
fans[i][j - k + 1] = ans;
}
}
for (int i = 0; i < n - k + 1; ++i) {
int ans = 0;
for (int j = 0; j < k; ++j) {
if (checkrow(0, i, j)) {
++ans;
}
}
fans1[0][i] = ans;
for (int j = k; j < n; ++j) {
if (checkrow(j - k, i, j - k)) {
--ans;
}
if (checkrow(j, i, j)) {
++ans;
}
fans1[j - k + 1][i] = ans;
}
}
int maxans = 0;
for (int i = 0; i < n - k + 1; ++i) {
for (int j = 0; j < n - k + 1; ++j) {
maxans = max(maxans, fans[i][j] + fans1[i][j]);
}
}
cout << maxans + pre << endl;
return 0;
}
