2025年【江苏“信息与未来”编程思维】真题及题解（T4：成语接龙）

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

输入 1

10 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

输出 #1

1

说明/提示

对于40 % 40\%40%的数据，n ≤ 100 n ≤ 100n≤100。

对于100 % 100\%100%的数据，10 ≤ n ≤ 10 4 10 ≤ n ≤ 10^410≤n≤104，且输入中的所有成语均来自真实的成语词典。成语词典中没有重复的成语。

思路分析

本题要求统计所有满足特定成语接龙条件的 4×4 方阵数量。每个成语由四个字符串（代表四个汉字）组成，首字和尾字是关键。方阵的六个成语分别位于：

1. 第一行（从左到右）：首字a，尾字b
2. 最后一列（从上到下）：首字b，尾字c
3. 最后一行（从右到左）：首字c，尾字d
4. 第一列（从下到上）：首字d，尾字a
5. 主对角线（左上到右下）：首字a，尾字c
6. 副对角线（右上到左下）：首字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³)，但实际数据中首尾组合有限，且候选列表很小，可以通过。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=10010;intn;// 成语总数intu[N],v[N];// u[i]: 第i个成语的首字ID, v[i]: 尾字IDunordered_map<string,int>id;// 汉字字符串 -> 编号unordered_map<ll,vector<int>>dict;// key = (首字ID<<32)|尾字ID, value = 成语编号列表unordered_map<int,vector<int>>out;// 首字ID -> 以该字开头的成语编号列表// 获取字符串对应的ID，若不存在则新建intgetid(conststring&s){if(id.count(s))returnid[s];intnewid=id.size();id[s]=newid;returnnewid;}intmain(){cin>>n;string s[4];for(inti=1;i<=n;++i){cin>>s[0]>>s[1]>>s[2]>>s[3];inta=getid(s[0]),b=getid(s[3]);// 首字和尾字u[i]=a;v[i]=b;ll key=((ll)a<<32)|(ll)b;// 组合成唯一键dict[key].push_back(i);out[a].push_back(i);}ll ans=0;// 枚举第一条边界成语 e1: a -> bfor(inti1=1;i1<=n;++i1){inta=u[i1],b=v[i1];// 枚举第二条边界成语 e2: b -> c，首字必须为 bfor(inti2:out[b]){if(i2==i1)continue;// 不能重复intc=v[i2];// 枚举第三条边界成语 e3: c -> d，首字必须为 cfor(inti3:out[c]){if(i3==i1||i3==i2)continue;intd=v[i3];// ---- 现在四个角 a,b,c,d 已确定 ----// 准备四个候选列表vector<int>L4,L5,L6;// 候选 e4: (d, a)ll k4=((ll)d<<32)|(ll)a;if(dict.count(k4)){for(intx:dict[k4]){if(x!=i1&&x!=i2&&x!=i3)L4.push_back(x);}}if(L4.empty())continue;// 候选 e5: (a, c)ll k5=((ll)a<<32)|(ll)c;if(dict.count(k5)){for(intx:dict[k5]){if(x!=i1&&x!=i2&&x!=i3)L5.push_back(x);}}if(L5.empty())continue;// 候选 e6: (b, d)ll k6=((ll)b<<32)|(ll)d;if(dict.count(k6)){for(intx:dict[k6]){if(x!=i1&&x!=i2&&x!=i3)L6.push_back(x);}}if(L6.empty())continue;// 统计所有合法的 (e4,e5,e6) 组合，三者必须互不相同// 因为候选列表一般很小，直接三重循环计数for(inte4:L4){for(inte5:L5){if(e5==e4)continue;// e4 和 e5 不能相同for(inte6:L6){if(e6==e4||e6==e5)continue;++ans;// 找到一个合法方阵}}}}}}cout<<ans<<'\n';return0;}

功能分析

【秘籍汇总】（完整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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}