惠阳住房和城乡建设局网站国际展览有限公司

当前位置： 首页 > news >正文

惠阳住房和城乡建设局网站,国际展览有限公司,个人站长做网站,四川网站排名目录 题目背景 问题描述 一、思路#xff1a; 二、实现方法#xff08;C#xff09; 2.1、方法一#xff08;int储存#xff09; 思路#xff1a; C实现如下#xff1a; 2.2、方法二#xff08;结构体储存#xff09; 思路#xff1a; 注意#xff1a;边界…目录 题目背景 问题描述 一、思路 二、实现方法C 2.1、方法一int储存 思路 C实现如下 2.2、方法二结构体储存 思路 注意边界判断 C实现如下 2.3、方法三map储存int为keymap为value 思路 C实现如下 2.4、方法四map储存pair为keyint为value 思路 C实现如下 三、遇到的问题 3.1、二维动态数组 3.2、vector作为value 3.3、结构体数组 题目背景 暑假要到了。可惜由于种种原因小 P 原本的出游计划取消。失望的小 P 只能留在西西艾弗岛上度过一个略显单调的假期……直到…… 某天小 P 获得了一张神秘的藏宝图。 问题描述 西西艾弗岛上种有 n 棵树这些树的具体位置记录在一张绿化图上。 简单地说西西艾弗岛绿化图可以视作一个大小为 (L1)×(L1) 的 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 棵树的具体位置。 传说大冒险家顿顿的宝藏就埋藏在某棵树下。 并且顿顿还从西西艾弗岛的绿化图上剪下了一小块制作成藏宝图指示其位置。 具体来说藏宝图可以看作一个大小为 (S1)×(S1) 的 01 矩阵 BS 远小于 L对应着 A 中的某一部分。 理论上绿化图 A 中存在着一处坐标 (x,y)0≤x,y≤L−S与藏宝图 B 左下角 (0,0) 相对应即满足 对 B 上任意一处坐标 (i,j)0≤i,j≤S都有 A[xi][yj]B[i][j]。 当上述条件满足时我们就认为藏宝图 B 对应着绿化图 A 中左下角为 (x,y)、右上角为 (xS,yS) 的区域。 实际上考虑到藏宝图仅描绘了很小的一个范围满足上述条件的坐标 (x,y) 很可能存在多个。 请结合西西艾弗岛绿化图中 n 棵树的位置以及小 P 手中的藏宝图判断绿化图中有多少处坐标满足条件。 特别地藏宝图左下角位置一定是一棵树即 A[x][y]B[0][0]1表示了宝藏埋藏的位置。 输入格式 从标准输入读入数据。 输入的第一行包含空格分隔的三个正整数 n、L 和 S分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。 由于绿化图尺寸过大输入数据中仅包含 n 棵树的坐标而非完整的地图即接下来 n 行每行包含空格分隔的两个整数 x 和 y表示一棵树的坐标满足 0≤x,y≤L 且同一坐标不会重复出现。 最后 (S1) 行输入小 P 手中完整的藏宝图其中第 i 行0≤i≤S包含空格分隔的 (S1) 个 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的容器里每次检查一棵树是否能作为有宝藏的地图时就检查藏宝图内所有树的坐标是否都能在以这棵树为左下角的S1*S1区域内找到如果可以便满足题目要求的条件。 当然为了节省运算时间和比对的次数我么可以在处理每棵树的时候就为其储存一个值存放其S1*S1区域内拥有的树木的总数量以及其S1*S1区域是否超过大地图的边界这样我们在判断时先比对这两个常量与藏宝图的关系就可以节省一部分匹配的时间。 由于开始写这个题的时候对C的stl容器还不是很了解在不断试错的过程中熟悉了很多容器的使用方法下面通过若干个实现例子分别解释。 注 写这个题目写了十几遍都不知道错在哪最后发现是自己没理解题目样例给的树的坐标都是从小到大的从左下角到右上角导致我以为测试数据都是这个规律以至于开始写了十几遍都没找到错误一直都是零分接下来的实现方法均是100写法同时可以帮助加深对C stl容器的理解和使用。 二、实现方法C 2.1、方法一int储存 思路 在输入每颗树的时候就判断其构成的小地图是否越界如果越界其必不可能用有宝藏故将A[i][3] 置为 -1表示其越界。 接着循环输入的每一棵树为其构造一个藏宝图大小的小地图同时储存其拥有的树的数量。 最后进行比较遇到满足条件的树会将num1。 C实现如下 #includeiostream using namespace std;int main() {int n,L,S;cinnLS; int A[1001][4]; int B[51][51]; int temp[1001][51][51]; int cnt;for(int i 0; in; i) {int x,y;cinxy;A[i][0] x;A[i][1] y;if(xSL||ySL) {A[i][3] -1;}}for(int i S; i0; –i) {for(int j 0; jS; j) {cinB[i][j];if(B[i][j]1) {cnt1;}}}for(int i 0; in; i) {int x,y;x A[i][0];y A[i][1];for(int j 0; jn; j) {//计算当前树为左下角的小地图内的树总数int xLen A[j][0] - x;int yLen A[j][1] - y;if(xLen0xLenSyLen0yLenS) {A[i][2]1;temp[i][xLen][yLen] 1;}}}int num 0;for(int i 0; in; i) {if(A[i][3]-1||A[i][2]!cnt) {continue;}bool flag true;for(int j 0; jS; j) {for(int k 0; kS; k) {if(B[j][k]1temp[i][j][k]!B[j][k]) {flag false;break;}}if(!flag) {break;}}if(flag) {num1;}}cout num;return 0; } 2.2、方法二结构体储存 思路 构造一个树的结构题其中储存以其为左下角构建的小地图他在大地图中的坐标以及它的地图是否越界小地图中含有的树的数目实现过程与方法一类似。 注意边界判断 //第一次写80分错在 x S L || y S L 多加了等于号 C实现如下 #includeiostream #includevector using namespace std; struct tree {int c[51][51];int view 0;int cnt 0;int x 0;int y 0;//int otherTree[1000]; }; vectortree 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) {giftCnt1;}}}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].cnt1;}}}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; in; 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; jS; j) { // for(int k 0; kS; k) { // cout t[i].c[j][k] ; // } // cout endl; // } // cout endl; // } // // cout 小明的藏宝图 endl; // for(int i 0; iS; i) { // for(int j 0; jS; j) { // coutgift[i][j] ; // // } // cout endl; // } // cout num;return 0; } 2.3、方法三map储存int为keymap为value 思路 将大地图中的树的坐标存到c的容器里每次检查一棵树是否能作为有宝藏的地图时就检查藏宝图内所有树的坐标是否都能在以这棵树为左下角的S1*S1区域内找到如果可以便满足题目要求的条件。最后判断输出即可是比较省时间省空间的做法。 同时由于map是红黑树实现的为有序的容器由于此题并未对顺序做要求所以可以使用由哈希表结构实现的unordered_map进一步提高检索的效率。 unordered_map的头文件为#includeunordered_map C实现如下 #includeiostream #includemap #includevector #includeunordered_map using namespace std; // 使用的是mapint,mapint,int BigMp;int main() {int n,L,S;cinnLS;int x,y;unordered_mapint,int[4] mp;unordered_mapint,int[2] gift; // mapint,vectorint mp; // mapint,vectorint gift; // vectorint v[L];unordered_mapint,mapint,int BigMp; for(int i 0; in; i) {cin x y;mp[i][0] x;mp[i][1] y;//储存当前树的横纵坐标在大地图中BigMp[x][y] 1;if(xSL||ySL) {//表示以该树为左下角的地图越界mp[i][3] -1;}}int giftNum 0;for(int i S; i0; –i) {for(int j 0; jS; j) {int now 0;cinnow;if(now1) {gift[giftNum][0] i;gift[giftNum][1] j;giftNum1;}}}for(int i 0; in; i) {x mp[i][0];y mp[i][1];for(int j 0; jn; 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; in; 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; jgiftNum; j) {int gX gift[j][0];int gY gift[j][1];if( BigMp[xgX][ygY]!1) {flag false;break;}}if(flag) {num1;}}cout num ;return 0; } 2.4、方法四map储存pair为keyint为value 思路 与上一方法相同只是容器的使用存在小小的区别 C实现如下 #includeiostream #includemap #includevector using namespace std; // 使用的是mappairint,int ,int BigMp;//可行 ,放里外都对 int main() {int n,L,S;cinnLS;int x,y;mapint,int[4] mp;mapint,int[2] gift;mappairint,int ,int BigMp;//可行 ,放里外都对 for(int i 0; in; i) {cin x y;mp[i][0] x;mp[i][1] y;//储存当前树的横纵坐标在大地图中BigMp[make_pair(x,y)] 1;if(xSL||ySL) {//表示以该树为左下角的地图越界mp[i][3] -1;}}int giftNum 0;for(int i S; i0; –i) {for(int j 0; jS; j) {int now 0;cinnow;if(now1) {gift[giftNum][0] i;gift[giftNum][1] j;giftNum1;}}}for(int i 0; in; i) {x mp[i][0];y mp[i][1];for(int j 0; jn; 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; in; 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; jgiftNum; j) {int gX gift[j][0];int gY gift[j][1];if( BigMp[make_pair(xgX,ygY)]!1) {flag false;break;}}if(flag) {num1;}}cout num ;return 0; } 三、遇到的问题 3.1、二维动态数组 使用该行代码 程序直接崩溃 vectorvectorint BigMp(1000000000,vectorint (1000000000,0));这段代码定义了一个名为 BigMp 的二维 vector其中包含 10^18 个整数类型的元素每个元素初始化为0。这里使用了 C11 中引入的双大于号语法来表示嵌套的向量。 这段代码存在的问题是。它试图分配巨大的内存空间超出了大部分机器的物理内存大小。由于每个 int 类型的变量通常占用4字节因此将使用至少4000GB的内存即使有处理这样多数据的计算机也很可能会导致其他程序的崩溃或系统的不稳定。 所以不推荐在实际应用中使用这种方式来定义向量。如果需要创建一个大型二维数组请考虑使用动态分配内存例如使用 new或将数据存储在磁盘上的文件中以避免消耗过多的内存资源。 3.2、vector作为value 这种写法是很不推荐的浪费空间 。 mapint,vectorint BigMp;//直接崩溃 3.3、结构体数组 这种结构体的写法只能在main函数外部定义因为其需要初始化。 tree t[1000]; 建议使用下面这种实现方法。 vectortree t(1001);