2024年12月GESP真题及题解(C++八级): 排队
2024年12月GESP真题及题解(C++八级): 排队
题目描述
小杨所在班级共有n nn位同学，依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n标号。这n nn位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有m mm对这样的关系（m mm是一个非负整数）。当m ≥ 1 m\geq 1m≥1时，第i ii对关系（1 ≤ i ≤ m 1\leq i\leq m1≤i≤m）给出a i , b i a_i,b_iai,bi，表示排队时编号为a i a_iai的同学需要排在编号为b i b_ibi的同学前面，并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对10 9 + 7 10^9+7109+7取模的结果。
输入格式
第一行，两个整数n , m n,mn,m，分别表示同学们的数量与关系数量。
接下来m mm行，每行两个整数a i , b i a_i,b_iai,bi，表示一对关系。
输出格式
一行，一个整数，表示答案对10 9 + 7 10^9+7109+7取模的结果。
输入输出样例 1
输入 1
4 2 1 3 2 4输出 1
2输入输出样例 2
输入 2
3 0输出 2
6输入输出样例 3
输入 3
3 2 1 2 2 1输出 3
0说明/提示
对于20 % 20\%20%的测试数据点，保证1 ≤ n ≤ 8 1\leq n\leq 81≤n≤8，0 ≤ m ≤ 10 0\leq m\leq 100≤m≤10。
对于另外20 % 20\%20%的测试数据点，保证1 ≤ n ≤ 10 3 1\leq n\leq 10^31≤n≤103，0 ≤ m ≤ 1 0\leq m\leq 10≤m≤1。
对于所有测试数据点，保证1 ≤ n ≤ 2 × 10 5 1\leq n\leq 2\times 10^51≤n≤2×105，0 ≤ m ≤ 2 × 10 5 0\leq m\leq 2\times 10^50≤m≤2×105。
题目分析
这道题是一个排列计数问题，有n nn个人排成一队，给出m mm个约束条件，每个约束条件( a i , b i ) (a_i, b_i)(ai,bi)表示a i a_iai必须排在b i b_ibi的前面且相邻。我们需要计算满足所有约束条件的排队方案数，并对10 9 + 7 10^9+7109+7取模。
如果没有约束条件，方案数就是n ! n!n!。加入约束条件后，我们可以将约束条件视为将两个人绑定成一个“块”，并且块内顺序固定。多个约束条件可能会将更多人绑定成一个更大的块（形成一条链）。最终，整个队伍由若干个块组成，块内部顺序固定，块之间可以任意排列。因此，方案数等于块数的阶乘，前提是约束条件合法。
约束条件合法的要求：
- 每个节点最多只能有一个前驱和一个后继（因为队伍是线性的，一个人最多和两个人相邻）。
- 不能形成环（否则无法排成直线）。
- 约束条件的方向必须一致，不能出现冲突（例如，一个块中不能出现两个不同的顺序要求）。
我们可以用并查集来维护块，同时记录每个节点的前驱和后继。对于每个约束( a , b ) (a, b)(a,b)：
- 如果a aa和b bb已经在同一个块中，则必须满足a aa是b bb的直接前驱，否则冲突。
- 如果不在同一个块，则必须满足a aa是它所在块的最后一个节点（即没有后继），且b bb是它所在块的第一个节点（即没有前驱），否则冲突。
- 合并两个块时，将a aa的后继设为b bb，b bb的前驱设为a aa，并将两个块的并查集合并。
最终，块的数量等于并查集中根节点的数量（每个根节点对应一个块的头节点，即没有前驱的节点）。方案数为块数的阶乘取模。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=200005;// 最大人数constintMOD=1e9+7;// 模数intn,m;intfa[N];// 并查集，fa[i]表示i所在块的头节点（根）intpre[N];// pre[i]表示i的前驱节点，0表示没有intnxt[N];// nxt[i]表示i的后继节点，0表示没有// 并查集查找根节点（带路径压缩）intfind(intx){if(fa[x]!=x){fa[x]=find(fa[x]);}returnfa[x];}// 尝试合并a和b，a必须排在b前面且相邻// 成功返回true，失败返回false（表示冲突）boolmerge(inta,intb){intha=find(a),hb=find(b);if(ha==hb){// a和b已经在同一个块中，检查a是否是b的直接前驱if(nxt[a]==b&&pre[b]==a){returntrue;// 该约束已经满足，忽略}else{returnfalse;// 冲突：同一个块中a不是b的直接前驱}}else{// 检查a是否没有后继，b是否没有前驱if(nxt[a]!=0||pre[b]!=0){returnfalse;// 冲突：a有后继或b有前驱}// 连接a和bnxt[a]=b;pre[b]=a;// 合并两个块：将hb所在块合并到ha所在块fa[hb]=ha;returntrue;}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;// 初始化for(inti=1;i<=n;i++){fa[i]=i;// 初始时每个人自己是一个块pre[i]=nxt[i]=0;// 没有前后继}boolvalid=true;// 标记当前约束是否都合法for(inti=0;i<m;i++){inta,b;cin>>a>>b;if(!valid)continue;// 已经出现冲突，继续读入但不处理if(!merge(a,b)){valid=false;// 出现冲突}}if(!valid){// 存在冲突，方案数为0cout<<0<<endl;return0;}// 统计块数：即并查集中根节点的个数（没有前驱的节点）intcnt=0;for(inti=1;i<=n;i++){if(find(i)==i){cnt++;}}// 计算阶乘 cnt! % MODlonglongans=1;for(inti=2;i<=cnt;i++){ans=ans*i%MOD;}cout<<ans<<endl;return0;}功能分析
1.数据结构：
- 并查集
fa：维护每个节点所属的块，根节点为块的头节点（没有前驱的节点）。 - 前驱数组
pre和后继数组nxt：记录每个节点的直接前驱和后继，用于检查约束的合法性。
2.合并操作：
- 对于每个约束
(a, b)，首先检查a和b是否在同一个块中。- 如果在同一个块，则必须满足
a是b的直接前驱，否则冲突。 - 如果不在同一个块，则必须满足
a是它所在块的最后一个节点（无后继），b是它所在块的第一个节点（无前驱），否则冲突。
- 如果在同一个块，则必须满足
- 若满足合并条件，则连接
a和b，并合并两个块的并查集。
3.冲突检测：
- 自环（
a == b）会被检测为冲突，因为a不能同时是自己的前驱和后继。 - 重复约束会被忽略（已经满足则跳过）。
- 如果出现环或分叉（如一个节点有两个后继或两个前驱），合并时会检测到冲突。
4.结果计算：
- 统计并查集中根节点的数量，即块的数量。
- 方案数为块数的阶乘，对
10^9+7取模。
5.复杂度分析：
- 时间复杂度：O ( n + m α ( n ) ) O(n + m \alpha(n))O(n+mα(n))，其中α ( n ) \alpha(n)α(n)是并查集操作的均摊复杂度，近似常数。
- 空间复杂度：O ( n ) O(n)O(n)，用于存储并查集、前驱和后继数组。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、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
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、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
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}