模拟赛题讲解[32]

来自 yukuai26 2023-08-04 noi.ac #3271

题目描述：

给定一个 $H$ 行 $W$ 列的矩阵，矩阵中的点一开始均为白色，然后将指定的 $N$ 个点染成黑色，询问有多少个 $3 \times 3$的区域中有恰好 $i$个黑色点 $0 \le i \le 9$。

输入格式：

输入共 $N+1$行，第一行三个整数，分别是 $H,W,N$，含义如题目所示。

接下来 $N$行，每行两个整数 $x,y$，表示将坐标为 $x,y$ 的点染成黑色。

输出格式：

输出共 $10$ 行，每行一个数，第 $i$行代表有多少个 $3 \times 3$的区域中恰好有 $i-1$个黑色点。

输入样例：

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

输出样例：

0
0
0
2
4
0
0
0
0
0

数据范围：

保证没有任何一个点被重复染色。

$3 \le H, W \le 10^9,~0 \le N \le \min(10^5, H \times W),~1 \le x_i,y_i \le H,W$。

题解：

这个破题居然折腾了我好久，真服了。

我的做法是枚举每个点周围的 $8$ 个点，如果不存在就加一个虚点。

然后枚举所有的点，计算以其为中心的矩形的答案（虚点不算进贡献里）

时间复杂度 $\mathcal{O}(9N)$

代码：（最失败的一份代码，留下作为教训）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define np(x,y) (make_pair(a[i].Fi + x, a[i].Se + y))
#define Fi first
#define Se second

int n,m,W,H,ans[15]; pii a[9 * N]; map<pii, char> mp;
bool check(pii x) { return *lower_bound(a + 1, a + 1 + n, x) == x; }
// int pos(pii x) { return lower_bound(a + 1, a + 1 + n, x) - a; }
bool safe(pii x) { return x.Fi >= 1 && x.Fi <= W && x.Se >= 1 && x.Se <= H; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> W >> H >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].Fi >> a[i].Se;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
    {
        for(int c = -1; c <= 1; c++)
            for(int d = -1; d <= 1; d++) {
                pii tmp = np(c,d);
                if(safe(tmp) && !check(tmp) && !mp[tmp])
                    a[n + (++m)] = tmp, mp[tmp] = 1;
            }
    }
    for(int i = 1; i <= n + m; i++)
    {
        if(safe(np(1,1)) && safe(np(-1,-1)))
        {
            int cnt = 0;
            for(int c = -1; c <= 1; c++)
                for(int d = -1; d <= 1; d++)
                    if(check(np(c,d))) ++cnt;
            ++ans[cnt];
        }
    }
    ans[0] = (W - 2) * (H - 2);
    for(int i = 1; i <= 9; i++) ans[0] -= ans[i];
    for(int i = 0; i <= 9; i++) cout << ans[i] << '\n';
    return 0;
}