无论遍历全图,还是只遍历存在奶牛的位置都会 TLE,观察后发现新加入的奶牛只影响它的上下左右
记录所有舒适奶牛位置,对于每只新加入的牛,首先判断它自己是否舒适,再处理它的上下左右
不妨以上方为例
- 上方奶牛现在是舒适的,把它加入舒适列表
- 上方奶牛现在不舒适,但在新牛加入前舒适,就从舒适列表中去掉它
其它方向作相同处理
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1e3 + 3;
int n, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
bool g[N][N];
unordered_set<int> easy;
bool is_easy(int x0, int y0) {
int t = 0;
for (int j = 0; j < 4; j ++) {
int x = x0 + dx[j], y = y0 + dy[j];
if (x >= 0 && x < n && y >= 0 && y < n && g[x][y])
t ++;
}
return t == 3;
}
int find(int x0, int y0) {
if (is_easy(x0, y0)) easy.insert(x0 * n + y0);
g[x0][y0] = 1;
for (int j = 0; j < 4; j ++) {
int x = x0 + dx[j], y = y0 + dy[j], k = x * n + y;
if (x >= 0 && x < n && y >= 0 && y < n && g[x][y]) {
if (is_easy(x, y)) easy.insert(k);
else if (easy.count(k)) easy.erase(k);
}
}
return easy.size();
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
int x, y; cin >> x >> y;
cout << find(x, y) << '\n';
}
return 0;
}
进一步观察,新奶牛 $a$ 的所有影响只是使周围某只奶牛 $b$ 的周围奶牛数加一。我们只需关注被影响的牛,当 $b$ 周围增加到 $3$ 头牛时,答案加一。当 $b$ 周围增加到 $4$ 头牛时,答案减一。此外,为了不判断边界,我们使坐标向右下偏移
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int cnt, g[N][N], dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
void add(int x0, int y0) {
if ((g[x0][y0] += 10) == 13) cnt ++;
for (int i = 0; i < 4; i ++) {
int x = x0 + dx[i], y = y0 + dy[i];
int &other = g[x][y]; other ++;
if (other == 13) cnt ++;
else if (other == 14) cnt --;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
while (n --) {
int x, y; cin >> x >> y;
add(x + 1, y + 1);
cout << cnt << '\n';
}
return 0;
}