官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录一、L2-048 寻宝图正解代码二、L2-047锦标赛能力值还原正解代码三、L2-046 天梯赛的赛场安排正解代码四、L2-045 堆宝塔正解代码一、L2-048 寻宝图题目大意给定一张N × M N \times MN×M的网格地图0代表水域1代表普通陆地2~9代表埋藏宝藏的陆地四连通上下左右相邻的陆地构成一座岛屿要求输出两个整数岛屿总数量、包含至少一个宝藏的岛屿数量。数据范围N × M ≤ 10 5 N \times M \le 10^5N×M≤105核心思路这是一道经典的洪水填充Flood Fill问题用 BFS 或 DFS 均可解决遍历网格中每一个格子遇到未访问过的非水域格子就启动一次连通块遍历岛屿总数 1遍历连通块的过程中只要发现任意一个格子数值 1即有宝藏就标记该岛屿为“有宝藏”单次连通块遍历结束后若标记为有宝藏则宝藏岛屿数 1。算法步骤读入地图用二维数组存储注意输入是字符型直接存字符即可建立访问标记避免重复统计同一个岛屿双重循环遍历每个格子若当前格子不是水域且未访问启动 BFSBFS 中向四个方向扩展标记已访问同时检查是否存在宝藏遍历结束后输出总岛屿数与宝藏岛屿数。正解代码#includebits/stdc.husingnamespacestd;constintdx[]{-1,1,0,0};constintdy[]{0,0,-1,1};intn,m,cnt0,ans0;vectorvectorcharg;mappairint,int,boolmp;// 访问标记也可以用二维数组优化voidbfs(intsx,intsy){boolhasTreasurefalse;queuepairint,intq;q.push({sx,sy});mp[{sx,sy}]true;if(g[sx][sy]!1)hasTreasuretrue;// 起点就是宝藏while(!q.empty()){auto[x,y]q.front();q.pop();// 枚举四个方向for(inti0;i4;i){intnxxdx[i],nyydy[i];// 越界判断if(nx1||ny1||nxn||nym)continue;// 是水域或已访问跳过if(g[nx][ny]0||mp[{nx,ny}])continue;mp[{nx,ny}]true;if(g[nx][ny]!1)hasTreasuretrue;q.push({nx,ny});}}if(hasTreasure)ans;// 该岛屿有宝藏}intmain(){cinnm;g.resize(n1,vectorchar(m1));for(inti1;in;i)for(intj1;jm;j)cing[i][j];for(inti1;in;i)for(intj1;jm;j)if(g[i][j]!0!mp[{i,j}]){bfs(i,j);cnt;// 每启动一次BFS对应一个新岛屿}coutcnt ans;return0;}二、L2-047锦标赛能力值还原题目大意有2 k 2^k2k名选手参加单败淘汰赛赛制为满二叉树结构第i ii轮共有2 k − i 2^{k-i}2k−i场比赛每场比赛的两名选手分别来自上一轮两场比赛的胜者能力值高的选手一定获胜能力值相同时任意一方获胜已知每场比赛败者的能力值以及最终冠军的能力值w ww要求还原初始所有选手的能力值无解则输出No Solution。数据范围1 ≤ k ≤ 18 1 \le k \le 181≤k≤18核心思路递归 满二叉树构造从根节点决赛向下逐层推导每场比赛对应满二叉树的一个节点节点存储本场比赛的「胜者能力值」和「败者能力值」根节点决赛的胜者是最终冠军w ww败者是输入给出的决赛败者值核心性质每场比赛的胜者能力值≥败者能力值当前节点的胜者和败者恰好是它两个子节点的胜者子节点的胜者打比赛赢的成为当前节点胜者输的成为当前节点败者。因此有两种分配方式左子节点胜者 当前胜者右子节点胜者 当前败者左子节点胜者 当前败者右子节点胜者 当前胜者。递归尝试两种分配方式只要有一种能让所有叶子节点都满足胜者≥败者就为合法解。算法步骤用数组模拟满二叉树每个节点存胜者win和败者lose按轮次输入所有比赛的败者值填入对应节点根节点的胜者赋值为w ww开始 DFS 递归若当前节点胜者 败者直接返回不合法若已经递归到选手层超出比赛节点范围返回合法尝试两种分配方式递归左右子节点任意一种成功则返回合法递归成功则输出叶子比赛层的所有胜者、败者即初始选手顺序失败则输出No Solution。正解代码#includebits/stdc.husingnamespacestd;constintN119;// k最大18节点数2^18-1开足够空间structNode{intwin,lose;}tre[N];intk;booldfs(intnow){// 递归边界超出比赛节点范围到达选手层合法if(now(1k))returntrue;// 胜者必须 败者否则不合法if(tre[now].wintre[now].lose)returnfalse;// 尝试第一种分配左子胜者当前胜者右子胜者当前败者tre[now*2].wintre[now].win;tre[now*21].wintre[now].lose;if(dfs(now*2)dfs(now*21))returntrue;// 尝试第二种分配左右交换tre[now*2].wintre[now].lose;tre[now*21].wintre[now].win;if(dfs(now*2)dfs(now*21))returntrue;returnfalse;}intmain(){cink;// 第i轮对应节点区间 [2^{k-i}, 2^{k-i1})for(inti1;ik;i){for(intj1(k-i);j1(k-i1);j){cintre[j].lose;}}cintre[1].win;// 根节点胜者是最终冠军if(dfs(1)){// 叶子比赛层第1轮的winlose就是初始选手顺序for(intj1(k-1);j(1k);j){couttre[j].win tre[j].lose;if(j!(1k)-1)cout ;}}else{coutNo Solution;}return0;}三、L2-046 天梯赛的赛场安排题目大意有N NN所学校参赛每个赛场容量为C CC安排规则如下按未安排人数从大到小的顺序处理学校若当前学校剩余人数≥ C \ge C≥C新开一个赛场放入C CC人剩余人数继续排队若剩余人数 C CC找编号最小的、剩余空位 ≥ 该人数的非空赛场安排进去找不到则新开一个赛场。要求输出每所学校需要联系的监考数量即该校分布在多少个赛场以及总赛场数。数据范围0 N ≤ 5000 0 N \le 50000N≤500010 ≤ C ≤ 50 10 \le C \le 5010≤C≤50每校人数 ≤ 500核心思路贪心模拟 优先队列分两部分处理整赛场部分每所学校的人数除以C CC得到的整数部分必然是独立的满赛场直接计入该校监考数和总赛场数余数部分存入大顶堆等待后续合并安排。余数部分用大顶堆维护所有学校的剩余人数每次取出人数最多的余数按规则遍历现有非满赛场找到第一个能放下的就安排找不到就新开赛场。算法步骤输入所有学校信息保存名称与编号对每所学校计算整赛场数num / C计入该校监考数与总赛场数余数 0 则加入大顶堆按人数降序用vector维护所有非满赛场的已用人数按开赛场顺序排列保证编号从小到大循环处理优先队列取出人数最多的余数遍历非满赛场列表找到第一个剩余空位足够的赛场找到则安排进去该校监考数 1更新赛场已用人数没找到则新开赛场总赛场数 1该校监考数 1加入非满赛场列表。按输入顺序输出每校名称与监考数最后输出总赛场数。正解代码#includebits/stdc.h#definepiipairint,intusingnamespacestd;constintN5009;structSchool{string name;intid;}s[N];intcnt[N];// 每所学校的监考数vectorintrooms;// 非满赛场的已用人数下标对应赛场编号顺序intmain(){intn,c;cinnc;inttotal0;// 总赛场数priority_queuepiiq;// 大顶堆(剩余人数, 学校id)for(inti0;in;i){intnum;cins[i].namenum;s[i].idi;intfullnum/c;cnt[i]full;totalfull;intremnum%c;if(rem0)q.push({rem,i});}while(!q.empty()){auto[x,id]q.top();q.pop();boolfoundfalse;// 按编号从小到大找第一个能放下的赛场for(inti0;irooms.size();i){if(c-rooms[i]x){rooms[i]x;cnt[id];foundtrue;break;}}// 找不到就新开赛场if(!found){total;cnt[id];rooms.push_back(x);}}// 按输入顺序输出for(inti0;in;i){couts[i].name cnt[i]\n;}couttotal;return0;}四、L2-045 堆宝塔题目大意有 A、B 两根柱子按顺序处理直径不同的彩虹圈规则如下第一个彩虹圈直接放在 A 柱作为第一座宝塔的基座取下一个彩虹圈 C若 C 小于 A 柱顶部圈直接放到 A 柱上否则比较 C 与 B 柱顶部圈B 柱为空 或 C 大于 B 柱顶部放到 B 柱上否则将 A 柱当前宝塔作为成品入库清空 A再把 B 柱上所有比 C 大的圈逐个移到 A 柱最后把 C 放到 A 柱。所有圈处理完后A 柱剩余的算一个成品B 柱剩余的逐个取下堆成另一个成品。求成品宝塔的总数量以及最高宝塔的层数。数据范围N ≤ 10 3 N \le 10^3N≤103核心思路双栈模拟用两个vector模拟 A、B 两根柱子back()对应栈顶严格按照题目描述的规则逐步骤模拟即可。算法步骤读入第一个彩虹圈放入 A 柱遍历剩余每个彩虹圈 C若 C A 栈顶 → 入 A 栈否则若 B 空 或 C B 栈顶 → 入 B 栈否则A 栈成品数 1更新最大高度清空 A 栈循环将 B 栈中所有比 C 大的元素弹出压入 A 栈将 C 压入 A 栈。处理剩余柱子A 非空则成品数 1更新最大高度B 非空则成品数 1更新最大高度。输出总成品数与最大高度。正解代码#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorintA,B;intans0,mx0,x;cinx;A.push_back(x);// 第一个圈直接放Afor(inti1;in;i){cinx;if(xA.back()){A.push_back(x);}elseif(B.empty()||B.back()x){B.push_back(x);}else{// A柱成品入库ans;mxmax(mx,(int)A.size());A.clear();// B中比x大的移到Awhile(!B.empty()B.back()x){A.push_back(B.back());B.pop_back();}A.push_back(x);}}// 处理剩余的A和Bif(!A.empty()){ans;mxmax(mx,(int)A.size());}if(!B.empty()){ans;mxmax(mx,(int)B.size());}coutans mx;return0;}