寻宝！大冒险！

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

枚举树作为左下角，检查平移后的藏宝图 1 集合与窗口内树集合完全相同。

OJ: shumeng

题目 ID: CSP202206B

难度:普及-

标签:模拟集合网格

日期: 2026-07-31 16:21

形式化题目

有一张大小为 $(L+1)\times(L+1)$ 的稀疏 01 网格，只给出其中 $n$ 个值为 1 的位置（树）。另有一张大小为 $(S+1)\times(S+1)$ 的完整 01 藏宝图 $B$ ，且 $B_{0,0}=1$ 。

问有多少个左下角 $(x,y)$ ，满足把 $B$ 平移到 $[x,x+S]\times[y,y+S]$ 后，与绿化图的对应区域完全相同。

思路

藏宝图很小（ $S\le 50$ ），绿化图很大（ $L\le 10^9$ ）但只有 $n\le 1000$ 棵树。直接对每个候选左下角展开整个窗口逐格比较，是理解题意最直接的朴素做法：

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，枚举每个候选左下角并逐格比较完整藏宝图。
#include <bits/stdc++.h>
using namespace std;

int n;
long long limit;
int s;
vector<pair<long long, long long> > tree;
set<pair<long long, long long> > exists; // 用集合记录每棵树的位置
vector<vector<int> > map_value;
int answer;

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

    cin >> n >> limit >> s;
    tree.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> tree[i].first >> tree[i].second;
        exists.insert(tree[i]);
    }
    map_value.assign(s + 1, vector<int>(s + 1, 0));
    for (int row = s; row >= 0; row--) {
        for (int col = 0; col <= s; col++) {
            cin >> map_value[row][col];
        }
    }

    // 对每个树作为左下角，展开整个 (S+1)*(S+1) 窗口逐格比较
    for (int i = 0; i < n; i++) {
        long long x = tree[i].first, y = tree[i].second;
        if (x + s > limit || y + s > limit) continue;
        bool valid = true;
        for (int dx = 0; dx <= s && valid; dx++) {
            for (int dy = 0; dy <= s; dy++) {
                bool has_tree = exists.count({x + dx, y + dy}) != 0;
                if (has_tree != (map_value[dx][dy] != 0)) {
                    valid = false;
                    break;
                }
            }
        }
        if (valid) answer++;
    }

    cout << answer << '\n';
    return 0;
}

这个做法逐格比较需要 $O(nS^2)$ 次集合查询，已经可以通过。下面再给出一个只用树集合、不展开窗口的写法。

关键观察

藏宝图左下角一定是树，所以候选左下角只可能是 $n$ 棵树之一。
对候选 $(x,y)$ ，窗口内实际存在的树必须是藏宝图中为 1 的位置。
反之，藏宝图中为 1 的位置也必须在窗口内有树。

第二个方向只需检查数量：窗口内的树总数等于藏宝图中 1 的总数，即可保证 1 的位置都有树。

算法步骤

读入 $n$ 棵树的位置。
读入藏宝图，注意输入按从上到下给出，实际存储时把行号倒置，让 map[dx][dy] 与坐标偏移 $(x+dx,y+dy)$ 对应；同时统计藏宝图中 1 的个数 tree_count。
枚举每棵树作为候选左下角，先排除窗口越界的候选。
遍历所有树，统计落在窗口内的树，并检查每棵窗口内的树对应藏宝图位置是否为 1。
若窗口内树数等于 tree_count，则该候选匹配，答案加一。

代码

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;          // 树的数量
long long limit; // 绿化图大小 L
int s;       // 藏宝图大小 S
pair<long long, long long> tree[MAXN]; // 每棵树的坐标 (x, y)
bool map_value[55][55]; // 藏宝图：map[dx][dy] 表示相对左下角的偏移位置是否有树
int tree_count;  // 藏宝图中 1 的总数
int answer;      // 匹配的左下角候选个数

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

    cin >> n >> limit >> s;
    for (int i = 0; i < n; i++) {
        cin >> tree[i].first >> tree[i].second;
    }

    // 藏宝图按从下往上逐行读入，所以先读最上面一行，再填到 map[0..s][0..s]
    // 这里把输入的第 s 行放到 map 的第 s 行，保证 map[dx][dy] 与坐标偏移一致
    for (int row = s; row >= 0; row--) {
        for (int col = 0; col <= s; col++) {
            cin >> map_value[row][col];
            if (map_value[row][col]) tree_count++;
        }
    }

    // 枚举每个树作为藏宝图左下角，检查该窗口内的树是否与藏宝图一致
    for (int i = 0; i < n; i++) {
        long long x = tree[i].first, y = tree[i].second;
        if (x + s > limit || y + s > limit) continue; // 窗口越出绿化图边界

        bool valid = true;
        int inside = 0; // 落在窗口内的树的数量
        for (int j = 0; j < n; j++) {
            long long tx = tree[j].first, ty = tree[j].second;
            if (tx < x || tx > x + s || ty < y || ty > y + s) continue;
            inside++;
            if (!map_value[tx - x][ty - y]) { // 窗口内有树但藏宝图对应位置为 0
                valid = false;
                break;
            }
        }
        // 窗口内树的数量必须恰好等于藏宝图中 1 的数量，
        // 这样藏宝图为 1 的位置也都一定有树。
        if (valid && inside == tree_count) answer++;
    }

    cout << answer << '\n';
    return 0;
}

复杂度

枚举 $n$ 个候选，每个候选扫描全部 $n$ 棵树，时间复杂度为 $O(n^2)$ ；空间复杂度为 $O(n+S^2)$ ，用于存树和藏宝图。

总结

稀疏地图不需要展开到 $L^2$ 的大小，候选左下角枚举和窗口内树计数分别保证了藏宝图 0、1 两种格子都被检查；这也是用树集合维护稀疏信息的典型思路。

题目来自第 26 次 CSP 认证 T2，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 0.5 秒

空间限制： 512 MB

题目背景

暑假要到了。可惜由于种种原因，小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到……

某天，小 P 获得了一张神秘的藏宝图。

题目描述

西西艾弗岛上种有 $n$ 棵树，这些树的具体位置记录在一张绿化图上。简单地说，西西艾弗岛绿化图可以视作一个大小为 $(L+1)×(L+1)$ 的 $01$ 矩阵 $A$ ，地图左下角（坐标 $(0,0)$ ）和右上角（坐标 $(L,L)$ ）分别对应 $A_{0,0}$ 和 $A_{L,L}$ 。其中 $A_{i,j}=1$ 表示坐标 $(i,j)$ 处种有一棵树， $A_{i,j}=0$ 则表示坐标 $(i,j)$ 处没有树。换言之，矩阵 $A$ 中有且仅有的 $n$ 个 $1$ 展示了西西艾弗岛上 $n$ 棵树的具体位置。

传说，大冒险家顿顿的宝藏就埋藏在某棵树下。并且，顿顿还从西西艾弗岛的绿化图上剪下了一小块，制作成藏宝图指示其位置。具体来说，藏宝图可以看作一个大小为 $(S+1)×(S+1)$ 的 $01$ 矩阵 $B$ （ $S$ 远小于 $L$ ），对应着 $A$ 中的某一部分。理论上，绿化图 $A$ 中存在着一处坐标 $(x,y)~(0\le x,y\le L-S)$ 与藏宝图 $B$ 左下角 $(0,0)$ 相对应，即满足：对 $B$ 上任意一处坐标 $(i,j)~(0\le i,j\le S)$ ，都有 $A_{x+i,y+j}=B_{i,j}$ 。当上述条件满足时，我们就认为藏宝图 $B$ 对应着绿化图 $A$ 中左下角为 $(x,y)$ 、右上角为 $(x+S,y+S)$ 的区域。

实际上，考虑到藏宝图仅描绘了很小的一个范围，满足上述条件的坐标 $(x,y)$ 很可能存在多个。请结合西西艾弗岛绿化图中 $n$ 棵树的位置，以及小 P 手中的藏宝图，判断绿化图中有多少处坐标满足条件。

特别地，藏宝图左下角位置一定是一棵树，即 $A_{x,y}=B_{0,0}=1$ ，表示了宝藏埋藏的位置。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的三个正整数 $n,L,S$ ，分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。

由于绿化图尺寸过大，输入数据中仅包含 $n$ 棵树的坐标而非完整的地图；即接下来 $n$ 行每行包含空格分隔的两个整数 $x$ 和 $y$ ，表示一棵树的坐标，满足 $0≤x,y≤L$ 且同一坐标不会重复出现。

最后 $(S+1)$ 行输入小 P 手中完整的藏宝图，其中第 $i$ 行 $(0\le i\le S)$ 包含空格分隔的 $(S+1)$ 个 $0$ 和 $1$ ，表示 $B_{S-i,0},\cdots,B_{S-i,S}$ 。需要注意，最先输入的是 $B_{S,0},\cdots,B_{S,S}$ 一行， $B_{0,0},\cdots,B_{0,S}$ 一行最后输入。

输出格式

输出到标准输出。

输出一个整数，表示绿化图中有多少处坐标可以与藏宝图左下角对应，即可能埋藏着顿顿的宝藏。

input1

output1

样例 1 解释

绿化图上 $(0,0),(1,1),(2,2)$ 三处均可能埋有宝藏。

input2

output2

样例 2 解释

如果将藏宝图左下角与绿化图 $(3,3)$ 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

子任务

$40\%$ 的测试数据满足： $L\le 50$ ；

$70\%$ 的测试数据满足： $L\le 2000$ ；

全部的测试数据满足： $n\le 1000,L\le 10^9,S\le 50$ 。

提示

实际测试数据中不包括答案为 $0$ 的用例。