官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7文章目录L2-029 特立独行的幸福L2-030 冰岛人L2-031 深入虎穴L2-032 彩虹瓶L2-029 特立独行的幸福题目大意对一个数的各位数字做平方和称为一次迭代能通过若干次迭代得到1的数称为幸福数迭代路径上的所有数都依附于初始数。在给定区间内不依附于区间内其他任何数字的幸福数称为特立独行的幸福数其独立性为依附于它的幸福数的总个数若该数本身是素数独立性翻倍。要求按升序输出区间内所有特立独行的幸福数及其独立性不存在则输出SAD。核心思路幸福数判定对每个数反复计算各位平方和若最终得到1则是幸福数若出现重复数字则说明进入死循环不是幸福数。依附关系标记用全局数组vis标记所有迭代过程中出现的中间数字——这些数字都依附于某个初始数最终区间内未被标记的幸福数就是特立独行的。独立性计算记录从初始数迭代到1的路径长度包含初始数自身若该数是素数则结果乘以2。素数判定试除法判断一个数是否为素数用于独立性加倍。关键细节判定单个数字是否幸福时需要局部标记数组st检测自身循环避免死循环。全局vis数组只标记迭代的中间结果不标记初始数本身这样初始数是否被标记取决于它是否出现在其他数的迭代路径中。独立性计数为路径上数字总数即中间数个数1初始数自身。正解代码#includebits/stdc.h//#define int long longusingnamespacestd;constintN1e49;intt,x,q,k,n,a,b;boolck(intx){if(x2)return0;for(inti2;ix/i;i)if(x%i0)return0;return1;}intf(intx){intnum0;while(x){inta1x%10;numa1*a1;x/10;}returnnum;}vectorboolvis(N,0);vectorpairint,intp;signedmain(){cinab;boolfg0;for(intia;ib;i){intnumi;boolfd0;vectorintv;vectorboolst(N,0);while(1){numf(num);vis[num]1;if(st[num])break;if(num!1){//coutnum ;v.push_back(num);st[num]1;continue;}else{fd1;break;}}if(!fd)continue;fg1;if(ck(i))p.push_back({i,2*(v.size()1)});elsep.push_back({i,v.size()1});}if(!fg)coutSAD;for(auto[id,cnt]:p){if(!vis[id])coutid cnt\n;}return0;}代码解析ck(int x)试除法判断素数小于2直接返回非素数。f(int x)计算一个数各位数字的平方和返回迭代结果。主函数遍历区间[a,b]内每个数反复迭代计算平方和用局部st数组检测循环用v数组记录迭代路径。若迭代到1说明是幸福数计算其独立性并存入结果数组。迭代过程中所有中间数都标记全局vis为1表示该数依附于其他数字。最后遍历结果数组只输出未被vis标记的数字特立独行的幸福数。L2-030 冰岛人说明本题需要处理族谱构建、姓名拆分、性别判断、辈分计算、五代以内亲属判定等逻辑边界条件多、字符串处理编码和调试的时间成本高。在竞赛赛场中建议优先放弃本题将精力集中在其他更容易快速AC的题目上保障整体得分效率。L2-031 深入虎穴题目大意迷宫是一棵有根树结构每扇门节点背后通向若干扇其他门子节点且不存在两条路通向同一扇门。入口是入度为0的根节点情报藏在距离入口最远的门里要求输出这扇门的编号题目保证结果唯一。核心思路建图存树用邻接表存储每个节点的子节点同时统计每个节点的入度。寻找根节点入度为0的节点就是迷宫的入口树的根节点。深度优先遍历从根节点出发DFS记录每个节点的深度维护全局最大深度和对应的节点编号。关键细节树的边是有向的父节点指向子节点因此必须通过入度找根不能默认1号节点是根。DFS过程中实时更新最大深度和对应节点题目保证唯一最远点无需处理并列情况。也可以用BFS层序遍历实现效果一致可避免递归深度过大的问题。正解代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN1e59;intn,m,k,t,ans,d[N],du[N];vectorintv[N];voiddfs(intnow,intcnt){d[now]max(d[now],cnt);if(cntans){anscnt;mnow;}for(autont:v[now])dfs(nt,cnt1);}signedmain(){cinn;for(inti1;in;i){cink;for(intj0;jk;j){intnt;cinnt;du[nt];v[i].push_back(nt);}}introot;m1;for(inti1;in;i)if(du[i]0){rooti;break;}dfs(root,0);coutm;return0;}代码解析v[N]邻接表存储每个门通向的门编号。du[N]入度数组用于查找根节点。dfs(int now, int cnt)递归遍历子节点cnt为当前深度每次更新当前节点的最大深度若超过全局最大值则更新答案节点。主函数读取输入构建邻接表、统计入度找到根节点后启动DFS最终输出最远节点编号。L2-032 彩虹瓶题目大意需要按1到N的顺序装填颜色工厂按给定顺序发货。若当前货物正好是待装填的颜色则直接装填否则堆放到临时货架栈结构后进先出上。每次装填后检查栈顶是否为下一个待装填颜色是则取出装填。若货架堆积超过容量M或最终无法按顺序装填完成则判定失败。判断每组发货顺序是否能顺利完成装填。核心思路栈模拟用栈结构模拟临时货架严格遵循后进先出的规则。顺序标记用变量now标记当前待装填的颜色编号初始为1。逐次处理遍历每个发货的货物匹配则直接装填并连续弹出栈顶可匹配的货物不匹配则压入栈并检查容量。最终校验所有货物处理完毕后继续从栈顶按顺序弹出可匹配的货物最终栈为空则成功。关键细节每次装填完成后必须循环检查栈顶可能连续弹出多个符合顺序的箱子。货架容量超限需要立即标记失败但仍需读完当前组的所有输入。遍历结束后必须二次校验栈的剩余内容避免末尾可弹出的情况遗漏。正解代码#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN1e59;intn,m,k,t,ans,a[N],x;signedmain(){cinnmk;while(k--){stackintsk;intnow1;boolfg0;for(inti0;in;i){cinx;boolffg0;if(xnow){now;ffg1;}while(sk.size()sk.top()now){now;sk.pop();}if(!ffg){sk.push(x);if(sk.size()m)fg1;}}while(sk.size()sk.top()now){now;sk.pop();}if(sk.size()||fg)coutNO;elsecoutYES;cout\n;}return0;}代码解析stackint sk模拟临时货架。now当前需要装填的颜色序号初始值为1。fg标记是否出现货架超容的情况。遍历每个发货数字若等于now则直接装填now自增随后循环弹出栈顶匹配的元素。否则压入栈若栈大小超过容量M则标记失败。遍历结束后再循环弹出栈顶匹配元素最终栈非空或曾超容则输出NO否则输出YES。