CCF-202206-2-寻宝！大冒险！

目录

题目背景

问题描述

一、思路：

二、实现方法（C++）

2.1、方法一（int储存）

思路：

C++实现如下：

2.2、方法二（结构体储存）

思路：

注意：边界判断

C++实现如下：

2.3、方法三（map储存，int为key，map为value）

思路：

C++实现如下：

2.4、方法四（map储存，pair为key，int为value）

思路：

C++实现如下：

三、遇到的问题

3.1、二维动态数组

3.2、vector作为value

3.3、结构体数组

---

 

题目背景

暑假要到了。可惜由于种种原因，小 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≤x,y≤L−S）与藏宝图 B 左下角 (0,0) 相对应，即满足：
对 B 上任意一处坐标 (i,j)（0≤i,j≤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≤i≤S）包含空格分隔的 (S+1) 个 0 和 1，表示 B[S−i][0]⋯B[S−i][S]。
需要注意，最先输入的是 B[S][0]⋯B[S][S] 一行，B[0][0]⋯B[0][S] 一行最后输入。

输出格式

输出到标准输出。

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

样例 1 输入

5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0

样例 1 输出

3

样例 1 解释

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

样例 2 输入

5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0

样例 2 输出

0

样例 2 解释

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

子任务

40% 的测试数据满足：L≤50；

70% 的测试数据满足：L≤2000；

全部的测试数据满足：n≤1000、L≤109 且 S≤50。

提示

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

---

一、思路：

毕竟是CCF第二题，所以一上来就知道不能构造一张很大的地图，一定是从很小的藏宝图来入手。所以想到了将每棵树作为一个小地图（大小为藏宝图的小地图）的左下角的位置，为每棵树维护一个小地图，最后将每棵树维护的小地图与藏宝图进行比对即可。

还有一个思路就是，不维护那么多的小地图，只需要将大地图中的树的坐标存到c++的容器里，每次检查一棵树是否能作为有宝藏的地图时，就检查藏宝图内所有树的坐标是否都能在以这棵树为左下角的（S+1）*（S+1）区域内找到，如果可以便满足题目要求的条件。

当然，为了节省运算时间和比对的次数，我么可以在处理每棵树的时候就为其储存一个值存放其（S+1）*（S+1）区域内拥有的树木的总数量，以及其（S+1）*（S+1）区域是否超过大地图的边界，这样我们在判断时先比对这两个常量与藏宝图的关系，就可以节省一部分匹配的时间。

由于开始写这个题的时候对C++的stl容器还不是很了解，在不断试错的过程中，熟悉了很多容器的使用方法，下面通过若干个实现例子分别解释。

注： 写这个题目写了十几遍都不知道错在哪，最后发现是自己没理解题目，样例给的树的坐标都是从小到大的（从左下角到右上角）导致我以为测试数据都是这个规律，以至于开始写了十几遍都没找到错误，一直都是零分，接下来的实现方法均是100写法，同时可以帮助加深对C++ stl容器的理解和使用。

---

二、实现方法（C++）

2.1、方法一（int储存）

思路：

在输入每颗树的时候就判断其构成的小地图是否越界，如果越界其必不可能用有宝藏，故将A[i][3] 置为 -1，表示其越界。

接着循环输入的每一棵树，为其构造一个藏宝图大小的小地图，同时储存其拥有的树的数量。

最后进行比较，遇到满足条件的树会将num+1。

C++实现如下：

#include<iostream>
using namespace std;int main() {int n,L,S;cin>>n>>L>>S;
int A[1001][4];
int B[51][51];
int temp[1001][51][51];
int cnt;for(int i = 0; i<n; ++i) {int x,y;cin>>x>>y;A[i][0] = x;A[i][1] = y;if(x+S>L||y+S>L) {A[i][3] = -1;}}for(int i = S; i>=0; --i) {for(int j = 0; j<=S; ++j) {cin>>B[i][j];if(B[i][j]==1) {cnt+=1;}}}for(int i = 0; i<n; ++i) {int x,y;x= A[i][0];y = A[i][1];for(int j = 0; j<n; ++j) {//计算当前树为左下角的小地图内的树总数int xLen = A[j][0] - x;int yLen = A[j][1] - y;if(xLen>=0&&xLen<=S&&yLen>=0&&yLen<=S) {A[i][2]+=1;temp[i][xLen][yLen] = 1;}}}int num = 0;for(int i = 0; i<n; ++i) {if(A[i][3]==-1||A[i][2]!=cnt) {continue;}bool flag = true;for(int j = 0; j<=S; ++j) {for(int k = 0; k<=S; ++k) {if(B[j][k]==1&&temp[i][j][k]!=B[j][k]) {flag = false;break;}}if(!flag) {break;}}if(flag) {num+=1;}}cout << num;return 0;
}

2.2、方法二（结构体储存）

思路：

构造一个树的结构题，其中储存以其为左下角构建的小地图，他在大地图中的坐标，以及它的地图是否越界，小地图中含有的树的数目，实现过程与方法一类似。

注意：边界判断

//第一次写80分，错在 x + S > L || y + S > L 多加了等于号

C++实现如下：

#include<iostream>
#include<vector>
using namespace std;
struct tree {int c[51][51];int view = 0;int cnt = 0;int x = 0;int y = 0;//int otherTree[1000];
};
vector<tree> t(1001);
//	tree t[1000];int main() {int n, L, S;int giftCnt = 0;int gift[51][51];cin >> n >> L >> S;for (int i = 0; i < n; ++i) {int x, y;cin >> x >> y;t[i].x = x;t[i].y = y;//如果当前树为左下角的藏宝图越界，将其标记为-1//第一次写80分，错在 x + S > L || y + S > L 多加了等于号 if (x + S > L || y + S > L ) {t[i].view = -1;}}for (int i = S; i >= 0; --i) {for (int j = 0; j <= S; ++j) {cin >> gift[i][j];if(gift[i][j]==1) {giftCnt+=1;}}}for (int i = 0; i < n; ++i) {int x, y;x = t[i].x;y = t[i].y;for (int j = 0; j < n; ++j) {int xLen = t[j].x - x;int yLen = t[j].y - y;if (xLen >= 0 && xLen <= S && yLen >= 0 && yLen <= S) {t[i].c[xLen][yLen] = 1;t[i].cnt+=1;}}}int num = 0;for (int i = 0; i < n; ++i) {bool flag = false;if(t[i].view==-1||t[i].cnt!=giftCnt) {continue;}for (int j = 0; j <= S; ++j) {for (int k = 0; k <= S; ++k) {if (t[i].c[j][k] != gift[j][k]) {flag = true;break;}}if (flag) {break;}}if (!flag) {if (t[i].view != -1)num++;}}//	for(int i = 0; i<n; ++i) {
//		cout << "第" << i << "个藏宝图" << endl;
//		cout << "该藏宝图拥有 " << t[i].cnt << " 棵树" << endl;
//		if(t[i].view==-1) {
//			cout << "他越界了 " << t[i].view << endl;
//		} else {
//			cout << "他没越界 " << t[i].view << endl;
//		}
//		for(int j = 0; j<=S; ++j) {
//			for(int k = 0; k<=S; ++k) {
//				cout << t[i].c[j][k] << ' ';
//			}
//			cout << endl;
//		}
//		cout << endl;
//	}
//	
//	cout << "小明的藏宝图" << endl;
//	for(int i = 0; i<=S; ++i) {
//		for(int j = 0; j<=S; ++j) {
//			cout<<gift[i][j] <<' ';
//
//		}
//		cout << endl;
//	}
//	cout << num;return 0;
}

2.3、方法三（map储存，int为key，map为value）

思路：

将大地图中的树的坐标存到c++的容器里，每次检查一棵树是否能作为有宝藏的地图时，就检查藏宝图内所有树的坐标是否都能在以这棵树为左下角的（S+1）*（S+1）区域内找到，如果可以便满足题目要求的条件。最后判断输出即可，是比较省时间省空间的做法。

同时，由于map是红黑树实现的，为有序的容器，由于此题并未对顺序做要求，所以可以使用由哈希表结构实现的unordered_map，进一步提高检索的效率。

unordered_map的头文件为#include<unordered_map>

C++实现如下：

#include<iostream>
#include<map>
#include<vector>
#include<unordered_map>
using namespace std;
//	使用的是map<int,map<int,int> > BigMp;int main() {int n,L,S;cin>>n>>L>>S;int x,y;unordered_map<int,int[4]> mp;unordered_map<int,int[2]> gift;
//	map<int,vector<int> > mp;
//	map<int,vector<int> > gift;
//	vector<int> v[L];unordered_map<int,map<int,int> > BigMp;	for(int i = 0; i<n; ++i) {cin >> x >> y;mp[i][0] = x;mp[i][1] = y;//储存当前树的横纵坐标在大地图中BigMp[x][y] = 1;if(x+S>L||y+S>L) {//表示以该树为左下角的地图越界mp[i][3] = -1;}}int giftNum = 0;for(int i = S; i>=0; --i) {for(int j = 0; j<=S; ++j) {int now = 0;cin>>now;if(now==1) {gift[giftNum][0] = i;gift[giftNum][1] = j;giftNum+=1;}}}for(int i = 0; i<n; ++i) {x = mp[i][0];y = mp[i][1];for(int j = 0; j<n; ++j) {int xLen = mp[j][0] - x;int yLen = mp[j][1] - y;if (xLen >= 0 && xLen <= S && yLen >= 0 && yLen <= S) {mp[i][2]+=1;}}}int num = 0;//遍历每一棵树for(int i = 0; i<n; ++i) {x = mp[i][0];y = mp[i][1];if(mp[i][3]==-1||mp[i][2]!=giftNum) {//当前树构成的小地图越界，或者小地图内含有的树的数量与藏宝图内的不符continue;}int flag = true;//遍历藏宝图中的每一棵树for(int j = 0; j<giftNum; ++j) {int gX = gift[j][0];int gY = gift[j][1];if( BigMp[x+gX][y+gY]!=1) {flag = false;break;}}if(flag) {num+=1;}}cout << num ;return 0;
}

2.4、方法四（map储存，pair为key，int为value）

思路：

与上一方法相同，只是容器的使用存在小小的区别

C++实现如下：

#include<iostream>
#include<map>
#include<vector>
using namespace std;
//	使用的是map<pair<int,int> ,int> BigMp;//可行 ,放里外都对 int main() {int n,L,S;cin>>n>>L>>S;int x,y;map<int,int[4]> mp;map<int,int[2]> gift;map<pair<int,int> ,int> BigMp;//可行 ,放里外都对 for(int i = 0; i<n; ++i) {cin >> x >> y;mp[i][0] = x;mp[i][1] = y;//储存当前树的横纵坐标在大地图中BigMp[make_pair(x,y)] = 1;if(x+S>L||y+S>L) {//表示以该树为左下角的地图越界mp[i][3] = -1;}}int giftNum = 0;for(int i = S; i>=0; --i) {for(int j = 0; j<=S; ++j) {int now = 0;cin>>now;if(now==1) {gift[giftNum][0] = i;gift[giftNum][1] = j;giftNum+=1;}}}for(int i = 0; i<n; ++i) {x = mp[i][0];y = mp[i][1];for(int j = 0; j<n; ++j) {int xLen = mp[j][0] - x;int yLen = mp[j][1] - y;if (xLen >= 0 && xLen <= S && yLen >= 0 && yLen <= S) {mp[i][2]+=1;}}}int num = 0;//遍历每一棵树for(int i = 0; i<n; ++i) {x = mp[i][0];y = mp[i][1];if(mp[i][3]==-1||mp[i][2]!=giftNum) {//当前树构成的小地图越界，或者小地图内含有的树的数量与藏宝图内的不符continue;}int flag = true;//遍历藏宝图中的每一棵树for(int j = 0; j<giftNum; ++j) {int gX = gift[j][0];int gY = gift[j][1];if( BigMp[make_pair(x+gX,y+gY)]!=1) {flag = false;break;}}if(flag) {num+=1;}}cout << num ;return 0;
}

三、遇到的问题

3.1、二维动态数组

使用该行代码 ，程序直接崩溃

vector<vector<int> > BigMp(1000000000,vector<int> (1000000000,0));

这段代码定义了一个名为 BigMp 的二维 vector，其中包含 10^18 个整数类型的元素，每个元素初始化为0。这里使用了 C++11 中引入的双大于号语法来表示嵌套的向量。
这段代码存在的问题是。它试图分配巨大的内存空间，超出了大部分机器的物理内存大小。由于每个 int 类型的变量通常占用4字节，因此将使用至少4000GB的内存，即使有处理这样多数据的计算机，也很可能会导致其他程序的崩溃或系统的不稳定。
所以不推荐在实际应用中使用这种方式来定义向量。如果需要创建一个大型二维数组，请考虑使用动态分配内存（例如使用 new）或将数据存储在磁盘上的文件中，以避免消耗过多的内存资源。

3.2、vector作为value

这种写法是很不推荐的，浪费空间 。

map<int,vector<int> > BigMp;//直接崩溃

3.3、结构体数组

这种结构体的写法，只能在main函数外部定义，因为其需要初始化。

tree t[1000];

建议使用下面这种实现方法。

vector<tree> t(1001);