企业官网建设流程全解析

招聘网站分析报告怎么做,外贸出口流程12步骤,游戏开发需要多少钱?,营销型网站建站推广2024年12月GESP真题及题解(C八级): 排队 题目描述 小杨所在班级共有 nnn 位同学#xff0c;依次以 1,2,…,n1,2,\dots,n1,2,…,n 标号。这 nnn 位同学想排成一行队伍#xff0c;其中有些同学之间关系非常好#xff0c;在队伍里需要排在相邻的位置。具体来说#xff0c;有 …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^971097取模的结果。输入格式第一行两个整数n , m n,mn,m分别表示同学们的数量与关系数量。接下来m mm行每行两个整数a i , b i a_i,b_iai​,bi​表示一对关系。输出格式一行一个整数表示答案对10 9 7 10^971097取模的结果。输入输出样例 1输入 14 2 1 3 2 4输出 12输入输出样例 2输入 23 0输出 26输入输出样例 3输入 33 2 1 2 2 1输出 30说明/提示对于20 % 20\%20%的测试数据点保证1 ≤ n ≤ 8 1\leq n\leq 81≤n≤80 ≤ m ≤ 10 0\leq m\leq 100≤m≤10。对于另外20 % 20\%20%的测试数据点保证1 ≤ n ≤ 10 3 1\leq n\leq 10^31≤n≤1030 ≤ m ≤ 1 0\leq m\leq 10≤m≤1。对于所有测试数据点保证1 ≤ n ≤ 2 × 10 5 1\leq n\leq 2\times 10^51≤n≤2×1050 ≤ 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^971097取模。如果没有约束条件方案数就是n ! n!n!。加入约束条件后我们可以将约束条件视为将两个人绑定成一个“块”并且块内顺序固定。多个约束条件可能会将更多人绑定成一个更大的块形成一条链。最终整个队伍由若干个块组成块内部顺序固定块之间可以任意排列。因此方案数等于块数的阶乘前提是约束条件合法。约束条件合法的要求每个节点最多只能有一个前驱和一个后继因为队伍是线性的一个人最多和两个人相邻。不能形成环否则无法排成直线。约束条件的方向必须一致不能出现冲突例如一个块中不能出现两个不同的顺序要求。我们可以用并查集来维护块同时记录每个节点的前驱和后继。对于每个约束( a , b ) (a, b)(a,b)如果a aa和b bb已经在同一个块中则必须满足a aa是b bb的直接前驱否则冲突。如果不在同一个块则必须满足a aa是它所在块的最后一个节点即没有后继且b bb是它所在块的第一个节点即没有前驱否则冲突。合并两个块时将a aa的后继设为b bbb bb的前驱设为a aa并将两个块的并查集合并。最终块的数量等于并查集中根节点的数量每个根节点对应一个块的头节点即没有前驱的节点。方案数为块数的阶乘取模。代码实现#includebits/stdc.husingnamespacestd;constintN200005;// 最大人数constintMOD1e97;// 模数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和ba必须排在b前面且相邻// 成功返回true失败返回false表示冲突boolmerge(inta,intb){inthafind(a),hbfind(b);if(hahb){// a和b已经在同一个块中检查a是否是b的直接前驱if(nxt[a]bpre[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);cinnm;// 初始化for(inti1;in;i){fa[i]i;// 初始时每个人自己是一个块pre[i]nxt[i]0;// 没有前后继}boolvalidtrue;// 标记当前约束是否都合法for(inti0;im;i){inta,b;cinab;if(!valid)continue;// 已经出现冲突继续读入但不处理if(!merge(a,b)){validfalse;// 出现冲突}}if(!valid){// 存在冲突方案数为0cout0endl;return0;}// 统计块数即并查集中根节点的个数没有前驱的节点intcnt0;for(inti1;in;i){if(find(i)i){cnt;}}// 计算阶乘 cnt! % MODlonglongans1;for(inti2;icnt;i){ansans*i%MOD;}coutansendl;return0;}功能分析1.数据结构并查集fa维护每个节点所属的块根节点为块的头节点没有前驱的节点。前驱数组pre和后继数组nxt记录每个节点的直接前驱和后继用于检查约束的合法性。2.合并操作对于每个约束(a, b)首先检查a和b是否在同一个块中。如果在同一个块则必须满足a是b的直接前驱否则冲突。如果不在同一个块则必须满足a是它所在块的最后一个节点无后继b是它所在块的第一个节点无前驱否则冲突。若满足合并条件则连接a和b并合并两个块的并查集。3.冲突检测自环a b会被检测为冲突因为a不能同时是自己的前驱和后继。重复约束会被忽略已经满足则跳过。如果出现环或分叉如一个节点有两个后继或两个前驱合并时会检测到冲突。4.结果计算统计并查集中根节点的数量即块的数量。方案数为块数的阶乘对10^97取模。5.复杂度分析时间复杂度O ( n m α ( n ) ) O(n m \alpha(n))O(nmα(n))其中α ( n ) \alpha(n)α(n)是并查集操作的均摊复杂度近似常数。空间复杂度O ( n ) O(n)O(n)用于存储并查集、前驱和后继数组。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、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.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}