官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-009 抢红包L2-010 排座位L2-011 玩转二叉树L2-012 关于堆的判断L2-009 抢红包题目大意给定N个人的发红包记录每条记录包含发红包个数、抢到者编号和对应金额。统计每个人的净收入抢到总金额 - 发出总金额按净收入从高到低排序输出收入并列则按抢到红包个数降序仍并列则按个人编号升序。输入金额以分为单位输出以元为单位保留两位小数。解题思路定义结构体存储每个人的编号、净收入、抢到红包的次数。遍历每条发红包记录对每个抢到红包的人累加其收入和抢包次数同时累计当前发红包者的总发出金额从其净收入中扣除。自定义三级排序规则优先按净收入降序其次按抢包次数降序最后按编号升序。排序后格式化输出完成分转元的单位换算。正解代码#includebits/stdc.husingnamespacestd;structpo{doubleq;intcnt,id;booloperator(constpo p)const{if(q!p.q)returnqp.q;if(cnt!p.cnt)returncntp.cnt;returnidp.id;}};intmain(){intn;cinn;vectorpop(n1);for(inti1;in;i){p[i].idi,p[i].q0,p[i].cnt0;}for(inti1;in;i){intk,sum0;cink;for(intj0;jk;j){intmoy,m;cinmmoy;summoy;p[m].cnt;p[m].qmoy*0.01;}p[i].q-sum*0.01;}vectorporesult;for(inti1;in;i){result.push_back(p[i]);}sort(result.begin(),result.end());for(inti0;in;i){printf(%d %.2f\n,result[i].id,result[i].q);}return0;}代码解析结构体po包含净收入q、抢包次数cnt、编号id重载运算符实现题目要求的排序优先级。外层循环遍历每个发红包的人内层循环处理每个红包接收者累加接收者收入最后统一扣除发红包者的总支出。将所有人存入结果数组后调用sort排序用printf控制两位小数输出。L2-010 排座位题目大意宾客间存在朋友和死对头两种关系朋友关系具有传递性敌对关系仅直接生效。对每组查询根据两人关系输出对应结果是朋友且不敌对输出No problem非朋友也不敌对输出OK敌对但有共同朋友输出OK but...仅敌对无共同朋友输出No way。解题思路朋友关系用并查集维护合并所有朋友对通过根节点判断两人是否属于同一个朋友圈子。敌对关系用二维布尔数组存储直接敌对关系仅记录直接的死对头。查询时分四种情况判断同根是朋友/有共同朋友且不敌对 → No problem不同根且不敌对 → OK同根且敌对 → OK but…不同根且敌对 → No way正解代码#includebits/stdc.husingnamespacestd;intn,m,k,p[110];intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}bools[110][110];intmain(){cinnmk;for(inti1;in;i)p[i]i;for(inti0;im;i){inta,b,c;cinabc;if(c-1)s[a][b]s[b][a]1;intaafind(a),bbfind(b);if(c1)p[aa]bb;}for(inti0;ik;i){inta,b;cinab;intaafind(a),bbfind(b);if(aabb!s[a][b])coutNo problem;elseif(aa!bb!s[a][b])coutOK;elseif(aabbs[a][b])coutOK but...;elseif(aa!bbs[a][b])coutNo way;else;cout\n;}return0;}代码解析并查集数组p维护朋友连通性find函数带路径压缩优化查询效率。二维数组s标记敌对关系双向赋值保证无向性。读取关系时朋友关系执行合并操作敌对关系标记数组对应位置。查询时先求两人的根节点结合敌对标记按四个分支输出对应结果。L2-011 玩转二叉树题目大意给定二叉树的中序遍历和前序遍历序列先对二叉树做镜面反转所有非叶节点的左右孩子互换再输出反转后的层序遍历序列。解题思路建树根据前序遍历确定根节点在中序遍历中定位根节点将序列划分为左子树和右子树递归构建整棵二叉树。镜面反转的层序遍历无需真正修改树结构在层序遍历时优先将右孩子入队再将左孩子入队输出顺序即为镜面反转后的层序结果。使用队列实现广度优先搜索完成层序遍历。正解代码#includebits/stdc.husingnamespacestd;constintN1e59;intn,m,t,k,x,y;intsuf[49],in[49];structnd{intval;nd*lefNULL;nd*rigNULL;};nd*build(intil,intir,intsl,intsr){if(ilir)returnNULL;introotsuf[sr];nd*pnewnd;p-valroot;if(ilir)returnp;intposil;while(in[pos]!root)pos;intlenpos-1-il1;p-lefbuild(il,pos-1,sl,sllen-1);p-rigbuild(pos1,ir,sllen,sr-1);returnp;}queuend*q;intmain(){cinn;for(inti0;in;i)cinsuf[i];for(inti0;in;i)cinin[i];introotsuf[n-1];nd*headnewnd;headbuild(0,n-1,0,n-1);q.push(head);while(q.size()){autontq.front();q.pop();if(nt-val!root)cout ;coutnt-val;if(NULL!nt-lef)q.push(nt-lef);if(NULL!nt-rig)q.push(nt-rig);}return0;}代码解析build函数接收前序、中序的左右边界递归构建二叉树前序首元素为根节点在中序中找到根位置计算左子树长度分别递归构建左右子树。层序遍历从根节点入队开始每次取出队首节点输出值先入队右孩子再入队左孩子等价于完成镜面反转。输出时控制空格保证行首行尾无多余空格。L2-012 关于堆的判断题目大意将给定数字按顺序插入初始为空的小顶堆随后判断多条命题包括根节点判断、兄弟节点判断、父子节点判断命题为真输出T否则输出F。解题思路建小顶堆数组模拟堆下标从1开始。逐个插入元素执行向上调整操作若当前节点值小于父节点则交换继续向上调整直到满足小顶堆性质。节点定位每次查询时遍历堆数组找到对应值的下标也可提前建立值到下标的映射。命题处理读取每行命题通过关键词判断命题类型提取节点值并转换为下标再根据堆的父子下标规则判断真假。正解代码#includebits/stdc.husingnamespacestd;constintN10010;intf[N],hs[N],n,s[N],p[N];//父节点 房子数 面积数 人数structfmy{intid,cntp,cnts,cnths;doubleperhs,pers;booloperator(fmy fam)const{if(pers!fam.pers)returnpersfam.pers;returnidfam.id;}};vectorfmyv;vectorintff[N];//先读入完再合并intfind(intx){if(f[x]!x)f[x]find(f[x]);returnf[x];}voidhebing(inta,intb){intaafind(a),bbfind(b);if(aabb)swap(aa,bb);if(aabb)return;f[bb]aa;//小的为家庭代表// 这里不合并财产等所有关系建立后再合并hs[aa]hs[bb];s[aa]s[bb];p[aa]p[bb];}intmain(){cinn;for(inti0;iN;i)f[i]i;//初始化intid,dad,mom,cnt;for(inti0;in;i){ciniddadmomcnt;intkid;// 标记存在的节点并初始化人数p[id]1;if(dad!-1){ff[id].push_back(dad);p[dad]1;}if(mom!-1){ff[id].push_back(mom);p[mom]1;}for(intj0;jcnt;j){cinkid;ff[id].push_back(kid);p[kid]1;}cinhs[id]s[id];}// 先建立所有关系for(inti0;i10000;i)for(intj0;jff[i].size();j)hebing(i,ff[i][j]);for(inti0;i10000;i)if(p[i]0ifind(i)){// 存在且是根节点v.push_back({i,p[i],s[i],hs[i],1.0*hs[i]/p[i],1.0*s[i]/p[i]});}sort(v.begin(),v.end());coutv.size()\n;for(inti0;iv.size();i)printf(%04d %d %.3f %.3f\n,v[i].id,v[i].cntp,v[i].perhs,v[i].pers);return0;}代码解析up函数实现向上调整递归比较当前节点与父节点不满足小顶堆则交换位置。使用string::find识别命题类型sscanf从字符串中提取数值简化字符串解析。兄弟节点判断两个节点的父节点下标相同i/2 j/2。父子节点判断子节点下标除以2等于父节点下标。根节点判断节点值等于堆数组第1位元素。