当前位置: 首页 > news >正文

P11380 [GESP202412 八级] 排队

解题思路

这个问题可以看作是一个图论中的链式关系计数问题。我们需要将n个同学排成一队,其中有些同学必须相邻且保持前后顺序。

核心思路:

  1. 将必须相邻的同学对视为一个整体(链),每个这样的链在最终排列中作为一个整体出现

  2. 使用并查集来维护这些链,将必须相邻的同学合并到同一个集合中

  3. 检查约束条件的合法性:

    • 不能有循环依赖(如A在B前,B在A前)

    • 每个同学最多只能有一个前驱和一个后继

  4. 最终答案:如果有k个链(包括单个同学的链),那么排列方式就是k!,因为每个链作为一个整体参与排列

代码注释:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10,inf = 0x3f3f3f3f;
int n,m,f[N],d[N];
int pre[N],nex[N];  // pre[i]: 必须在i前面的同学,nex[i]: 必须在i后面的同学// 并查集查找
int find(int x)
{if(f[x] != x) f[x] = find(f[x]);return f[x];
}// 并查集合并
void merge(int x,int y)
{int fx = find(x),fy = find(y);f[fy] = fx;
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) f[i] = i;  // 初始化并查集for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;// 如果关系已经存在,跳过(避免重复处理)if(pre[y] == x || nex[x] == y) continue;// 合法性检查:如果y已经有前驱,或x已经有后继,或x和y已经在同一个链中(形成环)if(pre[y] != 0 || nex[x] != 0 || find(x) == find(y)){cout << 0;  // 存在冲突,无解return 0;}merge(x,y);   // 将x和y合并到同一个链中pre[y] = x;   // 记录y的前驱是xnex[x] = y;   // 记录x的后继是y
    }ll sum = 0,p = 1e9 + 7,ans = 1;// 统计有多少个独立的链(包括单个同学的链)for(int i = 1; i <= n; i++) {if(f[i] == i) sum++;  // 并查集的根节点数量就是链的数量
    }// 计算链的排列数:sum!for(int i = 1; i <= sum; i++){ans = ans * i % p;}cout << ans;return 0;
}

 

http://www.hskmm.com/?act=detail&tid=26872

相关文章:

  • 数据增强操作
  • HTML5实现简洁的端午节节日网站源码 - 实践
  • Visio的图片,粘到word中显示不全,右边和下面显示不出来
  • 25国庆总结
  • 某平台增强排序脚本
  • 印度乡村AI计划:用JAN AI打造人工智能优先村庄
  • # Java方法学习:动手动脑与课后实验整理
  • CF2155D Batteries
  • JAVA语法基础》动手动脑与实验问题全整理
  • 崩铁壁纸
  • PotPlayer 播放器
  • 10.8动手动孬
  • [迷宫寻路 Round 3] 七连击
  • 《程序员修炼之道:从小工到专家》阅读笔记
  • [笔记]树论笔记+做题记录
  • 云服务器部署大数据组件
  • 规模化网站SSL证书终极方案
  • 详细介绍:录制mp4
  • 10月8日
  • 【OpenGL ES】光栅化插值原理和射线拾取原理
  • HTML 速查列表 - 教程
  • Exp1
  • 20_uv_wsl_installation
  • 学习问题日记-4
  • Codeforces Round 1042 (CF2131) 补题笔记(A-E)
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名AI编程助手框架需求探索
  • 表格数据自动机器学习技术解析
  • 10/8
  • 2025.10.8
  • 【QT】QString 与QString区别 - 教程