目录
题目背景
问题描述
一、思路:
二、实现方法(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函数外部定义,因为其需要初始化。文章来源:https://www.toymoban.com/news/detail-431404.html
tree t[1000];
建议使用下面这种实现方法。文章来源地址https://www.toymoban.com/news/detail-431404.html
vector<tree> t(1001);
到了这里,关于CCF-202206-2-寻宝!大冒险!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!