初赛知识

Wanderer

2026-08-19 20:52:37

发布于：广东

13阅读

0回复

0点赞

~~喵~ 喵~ 喵~~~

组合数学

公式定义

$A_n^m = \frac{n!}{(n-m)!}$

$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$

插板法1

n个相同苹果放入m个有编号的箱子,即

$x_1+x_2+\cdots+x_n= n, \quad x_i \geq 1 \ (i = 1, 2, \ldots, n)$

$\text{方案数} = C_{n-1}^{m-1}$

插板法2

n个相同苹果放入m个有编号的箱子,即

$x_1 + x_2 + \cdots + x_n = n, \quad x_i \geq 0 \ (i = 1, 2, \ldots, n)$

$\text{方案数} = C_{n+m-1}^{m-1}$

多重集合排列

同一元素多次出现求排列组合

$\text{排列数} = \frac{n!}{n_1! \, n_2! \, \cdots \, n_r!}, \quad n_1 + n_2 + \cdots + n_r = n$

相邻不能选择问题

从n个排成一行的数中选k个,要求任意两个数不相邻的方案数

$\text{方案数} = C_{k}^{n-k+1}$

容斥原理

三容斥原理问题

$\begin{aligned} |A \cup B \cup C| = \; & |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{aligned}$

四容斥原理问题

$\begin{aligned} |A_1 \cup A_2 \cup A_3 \cup A_4| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{aligned}$

其他数学知识

欧拉回路

定义:每条边恰好经过一次,最终回到起点

欧拉路径

定义:每条边恰好经过一次,起点和终点可以不同

二分图

定义:顶点可以分成两组,任意相邻两点属于不同组

联通与强联通

只有有向图可以说强联通,意思是任意两点可到达;
联通分量指的是任意两点可到达的子图

排序时间复杂度

排序算法	最优时间复杂度	最差时间复杂度	平均时间复杂度	实现大致思路
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	反复遍历相邻元素并交换逆序对，每轮将最大元素"冒泡"到末尾；可加标志位优化已有序情况
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	将未排序元素逐个插入到已排序序列的正确位置，类似整理扑克牌
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	每轮从未排序部分选出最小（大）元素，放到已排序序列末尾
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	分治法：递归地将数组二分至单元素，再自底向上合并两个有序子数组
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	分治法：选基准值将数组分为小于和大于基准的两部分，递归排序两部分；最差情况可通过随机化/三数取中避免
计数排序	$O(n + k)$	$O(n + k)$	$O(n + k)$	非比较排序：统计每个值出现次数，按值域顺序还原； $k$ 为值域范围，仅适用于整数且 $k$ 不太大时
基数排序	$O(d \cdot (n + k))$	$O(d \cdot (n + k))$	$O(d \cdot (n + k))$	非比较排序：按位（个十百…）依次进行稳定排序（通常用计数排序作子过程）； $d$ 为位数， $k$ 为每位基数

Linux系统指令

命令	作用
`mkdir`	创建目录
`cd`	切换目录
`ls`	查看文件
`pwd`	查看当前路径
`rm`	删除
`cp`	复制
`mv`	移动 / 重命名

有帮助，赞一个

去预览

0/2000

全部评论 3

集团-陈超杰
$C_{n+m-1}^{m-1}$ 写反了组合数
最差情况不能通过随机化/三数取中避免，最坏情况还是O(n^2) 只是概率更小

1小时前来自广东
1
- Wanderer
  回复
  集团-陈超杰
  哦哦
  
  2分钟前来自广东
  0
Wanderer
求点赞评论拿罐头

1小时前来自广东
1
KP-kouto
d

1小时前来自广东
0