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

本阶段真题参考代码（解析在代码注释里面）

课程链接：戳这 <—（您的支持是我最大的动力！）

例题一：L2-026 小字辈分数 25

voiddfs(intu,intfa)// 搜树模板{d[u]=d[fa]+1;// 求树的深度for(autov:c[u]){if(v!=fa){// 跳过父亲节点dfs(v,u);}}}voidsolve(){cin>>n;introot;for(inti=1;i<=n;i++){intx;cin>>x;if(x==-1)root=i;// 找根节点elsec[x].push_back(i);// 存树}d[root]=1;// 根节点辈分为 1dfs(root,0);// 从根节点出发搜树vector<int>e;// 存辈分最小的序列intmx=0;for(inti=1;i<=n;i++){if(mx<d[i]){// 辈分还有更小e.clear();e.push_back(i);mx=d[i];}elseif(mx==d[i]){// 辈分最小直接存e.push_back(i);}}cout<<mx<<'\n';for(inti=0;i<e.size();i++){// 输出所有点cout<<e[i];if(i!=e.size()-1)cout<<' ';}}

例题二：L2-031 深入虎穴分数 25

voiddfs(intu,intfa)// 搜树模板{d[u]=d[fa]+1;// 求树的深度for(autov:c[u]){if(v!=fa){// 跳过父亲节点dfs(v,u);}}}voidsolve(){cin>>n;for(inti=1;i<=n;i++){intk;cin>>k;for(intj=1;j<=k;j++){intx;cin>>x;c[i].push_back(x);// 存树p[x]++;// 统计入度}}introot;for(inti=1;i<=n;i++)if(!p[i])root=i;// 找到根节点dfs(root,0);// 从根节点往下搜intx,mx=0;for(inti=1;i<=n;i++){// 找到最远的那个点if(mx<d[i]){mx=d[i];x=i;}}cout<<x<<'\n';}

例题三：L2-052 吉利矩阵分数 25

voiddfs(intx,inty){if(x==n&&y>n){ans++;// 统计答案return;}if(y>n)x++,y=1;// 换行for(inti=0;i<=L-row[x]&&i<=L-col[y];i++){// 剪枝 1if(x==n&&i+col[y]!=L)continue;// 剪枝 2if(y==n&&i+row[x]!=L)continue;// 剪枝 3row[x]+=i;// 直接记录行和列的和优化判断col[y]+=i;dfs(x,y+1);row[x]-=i;// 回溯撤回标记col[y]-=i;}}voidsolve(){cin>>L>>n;dfs(1,1);cout<<ans<<'\n';}

例题四：L2-048 寻宝图分数 25

intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};intT,n,m,k;voidsolve(){cin>>n>>m;vector<vector<char>>g(n+10,vector<char>(m+10));// 二维n*m固定长度vector<vector<bool>>st(n+10,vector<bool>(m+10));for(inti=0;i<n;i++)for(intj=0;j<m;j++)st[i][j]=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>g[i][j];}}intans=0,cnt=0;for(inti=0;i<n;i++){// 遍历整块大陆for(intj=0;j<m;j++){if(!st[i][j]&&g[i][j]>='1'){ans++;// ans统计连通块（岛屿）个数queue<PII>q;// bfs初始化q.push({i,j});st[i][j]=true;boolflag=false;if(g[i][j]>'1')flag=true;while(q.size()){// 搜索连通块autot=q.front();q.pop();for(intk=0;k<4;k++){intx=t.x+dx[k];inty=t.y+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&!st[x][y]&&g[x][y]>='1'){st[x][y]=true;q.push({x,y});if(g[x][y]>'1')flag=true;// 发现宝藏岛屿}}}cnt+=flag;// cnt统计宝藏岛屿}}}cout<<ans<<' '<<cnt<<'\n';}

例题五：L3-037 夺宝大赛分数 30

intdx[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求最短路{queue<PII>q;// 初始化q.push({x,y});st[x][y]=true;while(q.size()){intx=q.front().x;// 取出当前点inty=q.front().y;q.pop();for(inti=0;i<4;i++){inttx=x+dx[i];intty=y+dy[i];if(!g[tx][ty])continue;// 跳过障碍if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!st[tx][ty]&&g[tx][ty]==1){d[tx][ty]=d[x][y]+1;// 距离+1q.push({tx,ty});st[tx][ty]=true;}}}}voidsolve(){cin>>n>>m;PII root;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>g[i][j];if(g[i][j]==2)root={i,j};// 找到大本营}}bfs(root.x,root.y);// 从大本营出发进行bfs搜索最短路map<int,vector<int>>mp;cin>>k;for(inti=1;i<=k;i++){intx,y;cin>>x>>y;swap(x,y);// 这里的横纵坐标反过来的，需要交换一下if(d[x][y])mp[d[x][y]].push_back(i);// 记录第几支队伍}for(autot:mp){if(t.y.size()==1){// 只有一支队伍就输出cout<<t.y[0]<<' '<<t.x<<'\n';return;}}cout<<"No winner.";}

例题六：L2-050 懂蛇语分数 25

map<string,vector<string>>mp;inta[N],b[N];intT,n,m,k;stringget(string s)// 获取每个单词首字母的集串{string str="";for(inti=0;i<s.size();i++){if(s[i]>='a'&&s[i]<='z'){str+=s[i];while(s[i]!=' '&&i<s.size())i++;}}returnstr;}voidsolve(){cin>>n;cin.ignore();for(inti=1;i<=n;i++){string str;getline(cin,str);// 一整行读入mp[get(str)].push_back(str);// 根据首字母集串映射识别其他串}cin>>m;cin.ignore();for(inti=1;i<=m;i++){string str;getline(cin,str);// 一整行读入string s=get(str);// 获取关键串（首字母映射）if(!mp[s].size())cout<<str<<'\n';// 如果没找到就输出原串else{vector<string>c=mp[s];sort(c.begin(),c.end());// 排序for(intj=0;j<c.size();j++){cout<<c[j];if(j!=c.size()-1)cout<<"|";// 字符串之间用 | 隔开}cout<<'\n';}}}