2025年【江苏“信息与未来”编程思维】真题及题解T4成语接龙题目描述小朋友们都很喜欢成语接龙但如果遇到可以无限接龙的 “防不胜防”、“忍无可忍” 和 “为所欲为”游戏就会陷入僵局。Dr. X 发明了改进版的成语接龙把16 1616个汉字写在4 44行4 44列的方阵中要求第一行从左往右读是一个四字成语。最后一列从上往下读是一个四字成语。最后一行从右往左读是一个四字成语。第一列从下往上读是一个四字成语。对角线从左上到右下读是一个四字成语。对角线从右上到左下读是一个四字成语。上面6 66个成语各不相同。下面是一个满足条件的成语接龙Dr. X 找到了一本成语词典你能帮 Dr. X 编程找到词典中所有满足条件的成语接龙方阵吗输入格式输入第一行是整数n nn表示成语词典中成语的数量。接下来n nn行每行四个空格分开的、长度不超过8 88的字符串由小写字母和数字组成。相同的字符串代表同一个汉字。输出格式输出一个整数代表不同成语接龙方阵的数量。对于两个4 × 4 4 × 44×4的方阵只要存在任意位置的汉字不同就认为是不同的方阵。输入输出样例 1输入 110 hua xiang niao yu yu miao tian xia xia li ba ren ren mian tao hua hua qian yue xia yu chu jing ren ji xiang ru yi xin xiang shi cheng cong ming ling li jian kang cheng zhang输出 #11说明/提示对于40 % 40\%40%的数据n ≤ 100 n ≤ 100n≤100。对于100 % 100\%100%的数据10 ≤ n ≤ 10 4 10 ≤ n ≤ 10^410≤n≤104且输入中的所有成语均来自真实的成语词典。成语词典中没有重复的成语。思路分析本题要求统计所有满足特定成语接龙条件的 4×4 方阵数量。每个成语由四个字符串代表四个汉字组成首字和尾字是关键。方阵的六个成语分别位于第一行从左到右首字a尾字b最后一列从上到下首字b尾字c最后一行从右到左首字c尾字d第一列从下到上首字d尾字a主对角线左上到右下首字a尾字c副对角线右上到左下首字b尾字d其中a,b,c,d是方阵四个角上的汉字字符串。因此一个方阵完全由四条边界成语(a→b), (b→c), (c→d), (d→a)决定而两条对角线成语则必须存在于词典中且不能与边界成语重复。枚举策略直接枚举 6 个成语会超时。我们枚举前三个边界成语第一行、最后一列、最后一行第四个边界成语由(d,a)自动确定只需检查是否存在。然后检查两条对角线是否存在且不重复。数据结构将每个成语映射为(首字ID, 尾字ID)并存储该组合对应的所有成语编号。用out[x]存储所有以x为首字的成语编号方便枚举e2和e3。成语编号从 1 到n保证唯一性。去重与计数对于固定的e1,e2,e3我们得到a,b,c,d。此时候选e4所有首尾为(d,a)且编号不在{e1,e2,e3}中的成语。候选e5所有首尾为(a,c)且编号不在{e1,e2,e3}中的成语。候选e6所有首尾为(b,d)且编号不在{e1,e2,e3}中的成语。然后统计所有选择(e4,e5,e6)且三者互不相同的方案数每个位置选一个成语。用三重循环枚举候选列表即可因为候选列表通常很小首尾组合有限。复杂度枚举e1为 O(n)枚举e2为 O(出度)枚举e3为 O(出度)。最坏可能 O(n³)但实际数据中首尾组合有限且候选列表很小可以通过。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN10010;intn;// 成语总数intu[N],v[N];// u[i]: 第i个成语的首字ID, v[i]: 尾字IDunordered_mapstring,intid;// 汉字字符串 - 编号unordered_mapll,vectorintdict;// key (首字ID32)|尾字ID, value 成语编号列表unordered_mapint,vectorintout;// 首字ID - 以该字开头的成语编号列表// 获取字符串对应的ID若不存在则新建intgetid(conststrings){if(id.count(s))returnid[s];intnewidid.size();id[s]newid;returnnewid;}intmain(){cinn;string s[4];for(inti1;in;i){cins[0]s[1]s[2]s[3];intagetid(s[0]),bgetid(s[3]);// 首字和尾字u[i]a;v[i]b;ll key((ll)a32)|(ll)b;// 组合成唯一键dict[key].push_back(i);out[a].push_back(i);}ll ans0;// 枚举第一条边界成语 e1: a - bfor(inti11;i1n;i1){intau[i1],bv[i1];// 枚举第二条边界成语 e2: b - c首字必须为 bfor(inti2:out[b]){if(i2i1)continue;// 不能重复intcv[i2];// 枚举第三条边界成语 e3: c - d首字必须为 cfor(inti3:out[c]){if(i3i1||i3i2)continue;intdv[i3];// ---- 现在四个角 a,b,c,d 已确定 ----// 准备四个候选列表vectorintL4,L5,L6;// 候选 e4: (d, a)ll k4((ll)d32)|(ll)a;if(dict.count(k4)){for(intx:dict[k4]){if(x!i1x!i2x!i3)L4.push_back(x);}}if(L4.empty())continue;// 候选 e5: (a, c)ll k5((ll)a32)|(ll)c;if(dict.count(k5)){for(intx:dict[k5]){if(x!i1x!i2x!i3)L5.push_back(x);}}if(L5.empty())continue;// 候选 e6: (b, d)ll k6((ll)b32)|(ll)d;if(dict.count(k6)){for(intx:dict[k6]){if(x!i1x!i2x!i3)L6.push_back(x);}}if(L6.empty())continue;// 统计所有合法的 (e4,e5,e6) 组合三者必须互不相同// 因为候选列表一般很小直接三重循环计数for(inte4:L4){for(inte5:L5){if(e5e4)continue;// e4 和 e5 不能相同for(inte6:L6){if(e6e4||e6e5)continue;ans;// 找到一个合法方阵}}}}}}coutans\n;return0;}功能分析功能模块关键解析汉字编码使用unordered_mapstring,int将每个汉字字符串映射为唯一整数 ID方便后续快速比较和组合键构造。成语存储用u[i]、v[i]分别存储成语的首字 ID 和尾字 ID用dict存储所有(首字,尾字)组合对应的成语编号列表用out存储每个首字对应的所有成语编号便于枚举。枚举边界三层循环枚举e1第一行、e2最后一列、e3最后一行。通过out限制首字保证每条边都能接上。每次枚举检查三个成语互不相同。生成候选由a,b,c,d计算e4首尾(d,a)、e5(a,c)、e6(b,d)的候选列表并排除已用的e1,e2,e3。计数合法组合对三个候选列表进行三重循环要求三个编号互不相同计数加 1。这保证了六个成语各不相同。【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}