L2（第二阶段）真题参考代码 + 注释解释

本阶段真题参考代码解析在代码注释里面课程链接戳这 —您的支持是我最大的动力例题一L2-026 小字辈分数 25voiddfs(intu,intfa)// 搜树模板{d[u]d[fa]1;// 求树的深度for(autov:c[u]){if(v!fa){// 跳过父亲节点dfs(v,u);}}}voidsolve(){cinn;introot;for(inti1;in;i){intx;cinx;if(x-1)rooti;// 找根节点elsec[x].push_back(i);// 存树}d[root]1;// 根节点辈分为 1dfs(root,0);// 从根节点出发搜树vectorinte;// 存辈分最小的序列intmx0;for(inti1;in;i){if(mxd[i]){// 辈分还有更小e.clear();e.push_back(i);mxd[i];}elseif(mxd[i]){// 辈分最小直接存e.push_back(i);}}coutmx\n;for(inti0;ie.size();i){// 输出所有点coute[i];if(i!e.size()-1)cout ;}}例题二L2-031 深入虎穴分数 25voiddfs(intu,intfa)// 搜树模板{d[u]d[fa]1;// 求树的深度for(autov:c[u]){if(v!fa){// 跳过父亲节点dfs(v,u);}}}voidsolve(){cinn;for(inti1;in;i){intk;cink;for(intj1;jk;j){intx;cinx;c[i].push_back(x);// 存树p[x];// 统计入度}}introot;for(inti1;in;i)if(!p[i])rooti;// 找到根节点dfs(root,0);// 从根节点往下搜intx,mx0;for(inti1;in;i){// 找到最远的那个点if(mxd[i]){mxd[i];xi;}}coutx\n;}例题三L2-052 吉利矩阵分数 25voiddfs(intx,inty){if(xnyn){ans;// 统计答案return;}if(yn)x,y1;// 换行for(inti0;iL-row[x]iL-col[y];i){// 剪枝 1if(xnicol[y]!L)continue;// 剪枝 2if(ynirow[x]!L)continue;// 剪枝 3row[x]i;// 直接记录行和列的和优化判断col[y]i;dfs(x,y1);row[x]-i;// 回溯撤回标记col[y]-i;}}voidsolve(){cinLn;dfs(1,1);coutans\n;}例题四L2-048 寻宝图分数 25intdx[4]{0,0,1,-1};intdy[4]{1,-1,0,0};intT,n,m,k;voidsolve(){cinnm;vectorvectorcharg(n10,vectorchar(m10));// 二维n*m固定长度vectorvectorboolst(n10,vectorbool(m10));for(inti0;in;i)for(intj0;jm;j)st[i][j]0;for(inti0;in;i){for(intj0;jm;j){cing[i][j];}}intans0,cnt0;for(inti0;in;i){// 遍历整块大陆for(intj0;jm;j){if(!st[i][j]g[i][j]1){ans;// ans统计连通块岛屿个数queuePIIq;// bfs初始化q.push({i,j});st[i][j]true;boolflagfalse;if(g[i][j]1)flagtrue;while(q.size()){// 搜索连通块autotq.front();q.pop();for(intk0;k4;k){intxt.xdx[k];intyt.ydy[k];if(x0xny0ym!st[x][y]g[x][y]1){st[x][y]true;q.push({x,y});if(g[x][y]1)flagtrue;// 发现宝藏岛屿}}}cntflag;// cnt统计宝藏岛屿}}}coutans cnt\n;}例题五L3-037 夺宝大赛分数 30intdx[4]{0,0,1,-1};intdy[4]{1,-1,0,0};intg[N][N],d[N][N];boolst[N][N];intT,n,m,k;voidbfs(intx,inty)// 标准bfs求最短路{queuePIIq;// 初始化q.push({x,y});st[x][y]true;while(q.size()){intxq.front().x;// 取出当前点intyq.front().y;q.pop();for(inti0;i4;i){inttxxdx[i];inttyydy[i];if(!g[tx][ty])continue;// 跳过障碍if(tx1txnty1tym!st[tx][ty]g[tx][ty]1){d[tx][ty]d[x][y]1;// 距离1q.push({tx,ty});st[tx][ty]true;}}}}voidsolve(){cinnm;PII root;for(inti1;in;i){for(intj1;jm;j){cing[i][j];if(g[i][j]2)root{i,j};// 找到大本营}}bfs(root.x,root.y);// 从大本营出发进行bfs搜索最短路mapint,vectorintmp;cink;for(inti1;ik;i){intx,y;cinxy;swap(x,y);// 这里的横纵坐标反过来的需要交换一下if(d[x][y])mp[d[x][y]].push_back(i);// 记录第几支队伍}for(autot:mp){if(t.y.size()1){// 只有一支队伍就输出coutt.y[0] t.x\n;return;}}coutNo winner.;}例题六L2-050 懂蛇语分数 25mapstring,vectorstringmp;inta[N],b[N];intT,n,m,k;stringget(string s)// 获取每个单词首字母的集串{string str;for(inti0;is.size();i){if(s[i]as[i]z){strs[i];while(s[i]! is.size())i;}}returnstr;}voidsolve(){cinn;cin.ignore();for(inti1;in;i){string str;getline(cin,str);// 一整行读入mp[get(str)].push_back(str);// 根据首字母集串映射识别其他串}cinm;cin.ignore();for(inti1;im;i){string str;getline(cin,str);// 一整行读入string sget(str);// 获取关键串首字母映射if(!mp[s].size())coutstr\n;// 如果没找到就输出原串else{vectorstringcmp[s];sort(c.begin(),c.end());// 排序for(intj0;jc.size();j){coutc[j];if(j!c.size()-1)cout|;// 字符串之间用 | 隔开}cout\n;}}}