Duanyll's Blog

CSP 初赛数学复习

17 October 2019 | duanyll | Tags: 数学

数学逻辑记号

与 或 非
$\land$ $\lor$ $\lnot$

C++ 运算符优先级:

排列组合

排列的定义: 从$n$个不同元素中, 任取$m$个元素, 按照一定的顺序排成一列, 叫做从$n$个不同元素中取出$m$个元素的一个排列.

\[P_n^m=\frac{n!}{(n-m)!}\]

组合的定义: 从n个不同元素中, 任取m个元素, 并成一组, 叫做从n个不同元素中取出m个元素的一个组合.

\[C_n^m=\frac{n!}{m!(n-m)!}\]

与顺序有关的用排列, 与顺序无关的用组合

加法原理, 乘法原理.

一些重要思想

学校师生合影，共8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式?

插入法: 对于要求某几个元素不相邻的问题, 可以考虑先排好其他的元素, 而对于不相邻的元素从其他元素排好后的的序列中枚举空位插入. 答案: $P_8^8 * P_7^4$

5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法?

捆绑法: 要求相邻的元素可以视作一个元素参加排列, 注意捆绑的元素内部也能产生排列. 答案: $P_6^6 * P_3^3$

袋中有不同年份生产的5分硬币23个, 不同年份生产的1角硬币10个, 如果从袋中取出2元钱, 有多少种取法?

剩余法: 硬币共有2.15元, 取出两元即留下0.15元, 可以是$0.05 * 3$或$0.1 + 0.05$, 分别运用加法原理乘法原理得答案: $C_{23}^{3}+C_{23}^1*C_{10}^1$

学校安排考试科目9门, 语文要在数学之前考, 有多少种不同的安排顺序?

对等法: “语文在数学之前”和”语文在数学之后”的情况是等价的, 所以答案就是$P_9^9/2$

某个班级共有43位同学, 从中任抽5人, 正、副班长、团支部书记至少有一人在内的抽法有多少种?

排异法: 用总情况数减去三人都不选的情况, 避免分类讨论. 答案: $C_{43}^5-C_{40}^5$

将8个相同的球放入3个不同盒子中, 每个盒子至少放一个, 有几种方法?

隔板法: 7个空位放2个板, 有$C_7^2$中办法.

将8个相同的球放入3个不同盒子中, 盒子可以为空, 有几种方法?

隔板法: 两块板 + 8个球共10个元素, 方法数相当于从10个位置里选两个放板, 所以有$C_{10}^2$种方法

推荐阅读 排列组合之“捆绑法”、“插空法”、“插板法”

隔板法和插空法的区别: 隔板法要求球相同

特殊的排列组合问题

圆排列: 从n个不同的元素中取r个沿一圆周排列.

\[\frac{P_n^r}{r}\]

有重复元素的排列: 分别有$n_1, n_2, \cdots, n_i$个不同的元素.

\[\frac{(n_1+n_2+\cdots+n_i)!}{n_1!n_2!\cdots n_i!}\]

递推关系

错排问题

第i个元素不在i位置上的排列总数. 考虑两种情况:

  • 先错排前$n-1$个, 然后$n$与前$n-1$之一交换.
  • $n$与前$n-1$个之一交换, 再剩下$n-2$个.
\[f(n) = (n-1)*(f(n-1)+f(n-2))\] \[f(1) = 0, f(2) = 1\] \[f(n) = n!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots+(-1)^n\frac{1}{n!})\]

第一类 Stirling 数

n个不同元素构成m个圆排列的方案数. 考虑第n个元素:

  • 单独组成一个圆排列
  • 插到之前$n-1$个数之一的左边
\[S(n,m) = S(n-1,m-1) + (n-1)S(n-1, m)\]

第二类 Stirling 数

将n个不同的元素拆分成m个集合的方案数.

n个有区别的球放到m个相同的盒子中, 要求无一空盒, 其不同的方案数用$S(n,m)$表示，称为第二类 Stirling 数. 设有每个球分别为$b_1, b_2, \cdots, b_n$, 考虑放置$b_n$

  • 令$b_n$独占一个新的盒子.
  • 把$b_n$放进现有的一个放了球的盒子里
\[S(n,m) = S(n-1,m-1) + mS(n-1,m)\] \[S(n,1) = 1, S(n,n) = 1, S(n,0) = 0\]

注意隔板法是相同球进不同盒, 这里是不同球进相同盒.

Catalan 数

推荐阅读: 卡特兰数 — 计数的映射方法的伟大胜利

令$C(0)=1, C(1)=1$, Catalan 数满足:

\[C(n) = C(0)C(n-1) + C(1)C(n-2) + \cdots + C(n-1)C(0)\] \[C(n) = \frac{4n-2}{n+1}C(n-1)\] \[C(n) = \frac{C_{2n}^n}{n+1} = \frac{P_{2n}^n}{(n+1)!} = \frac{(2n)!}{n!(n+1)!}\]
  • 一个足够大的栈的进栈序列对应的出栈序列的种数: 考虑最后出栈的是第i个元素, 所以比i先出栈有$C(i-1)$种方案, 比i后出栈有$C(n-i)$种方案, i取遍1到n就是上面的递推式.
  • n个节点的二叉树种类数: 考虑中序遍历的序列, 树根为i, 则左子树的方案数为$C(i-1)$, 右子树的方案数为$C(n-i)$, 又得到了上面的递推式

  • 凸多边形的三角形划分: 一个凸的n边形, 用直线连接他的两个顶点使之分成多个三角形, 每条直线不能相交, 问一共有多少种划分方案. 解法见图:

    image.png

  • $n\times n$的方格图中, 只能向右或向上, 从$(1,1)\rightarrow(n,n)$不跨越对角线的方法数. HDU 3398. 其他的一些也可以抽象为这个走格子的模型.
  • 由n对括号形成的合法括号表达式数: 类比出栈序列.

  • 用n个长方形去填充一个高度为n的阶梯图形的方法数:

    image.png

    考虑包含最左上角的方块的矩形对应的是哪一个阶梯, 然后分为下边和右边两部分, 得到卡特兰数的递推公式.

集合取数问题

设$f(n,k)$是从集合${1,2,\cdots,n}$中能够选择的没有两个连续整数的k个元素子集的数目, 求递归式$f(n,k)$. 考虑第n个数:

  • 要放第n个数, 所以不能放第$n-1$个数
  • 不放第n个数
\[f(n,k) = f(n-2,k-1) + f(n-1, k)\] \[f(n,1)=1, f(n,k)=0(n\leq k)\]

也可以用插空法模型来解决问题.

整数划分问题

将整数n分成k份, 且每份不能为空, 不考虑顺序互不相同的方法数. 令$f(n, k)$表示把n分为k份的方案数, 两种情况:

  • 分出来的k份每一份都大于一, 所以先从n中取出k来摊在每一份上, 再分了剩下的$n-k$.
  • 分了一个1出来. 剩下的再说.
\[f(n, k) = f(n-k, k) + f(n-1,k-1)\] \[f(n, 1) = 1, f(n, k) = 0 (n < k)\]

自然数n的拆分方案:

\[\sum_{i=2}^n(f(n, i))\]

特征根法

数列${f}$满足递推关系式:

\[f_n = af_{n-1} + bf_{n-2}\]

为得到其函数形式, 需将两边整理为类似$\lambda(f_n-rf_{n-1})=f_{n-1}-rf_{n-2}$的结构. 展开得

\[f_n=\frac{r+1}{\lambda}f_{n-1} - \frac{r}{\lambda}f_{n-2}\] \[\lambda+r = a, \lambda r = -b\]

即$\lambda, r$是方程$x^2=ax+b$的两根.

经过化简可得到

\[f_n = c\lambda^n+ds^n\]

其中$c,d$可通过待定系数法解得.

不动点法

数列${f}$满足递推关系式:

\[f_n = \frac{af_{n-1}+b}{cf_{n-1}+d}\]

令$p,q$为方程$x = \frac{ax+b}{cx+d}$的两根

  • 若$p\neq q$

    则$\frac{f_n-p}{f_n-q}$是以$\frac{a-cp}{a-cq}$为公比的等比数列, 进一步可用待定系数法确定$f_n$.

  • 若$p=q$

    则$\frac{1}{f_n-p}$是以$\frac{1}{a_1-p}$为首项, $\frac{2c}{a+d}$为公差的等差数列.

时间复杂度

NOIP2017 D1T2

P, NP, NPC, NP-Hard

推荐阅读: P问题、NP问题、NP完全问题和NP难问题

简称 英文 定义 例子
P问题 P: polynominal 存在多项式时间算法的问题 冒泡排序
NP问题 NP: Nondeterministic polynominal 能在多项式时间内验证一个正确解的问题 TSP
NPC问题 NPC: Nondeterminism Polynomial Complete 存在这样一个NP问题, 所有的NP问题都可以约化成它. (只要解决了这个问题, 那么所有的NP问题都解决了) 逻辑电路问题(给定一个逻辑电路, 问是否存在一种输入使输出为False), Hamilton 回路, TSP
NP 难问题 NP Hard 所有的NP问题都能约化到它, 但是他不一定是一个NP问题 并没有

我们感兴趣NP问题是否都是P问题(P == NP?)(如果是的, 那么所有NP问题都可以用计算机来解决了), 在研究这一点的过程中, 我们发现了一类特殊的NP问题, 解决它就可以解决所有的NP问题, 称之为NPC问题. 解决NP-Hard问题也可以解决NP问题, 但是NP-Hard问题不一定是NP问题.

image.png

P=NP至今仍未被证明或推翻, NPC问题的发现使得情况更加微妙了.

Master 定理

推荐阅读: Master 定理学习笔记

记号 意义
$\Theta$ 等于
$O$ 小于等于
$o$ 小于
$\Omega$ 大于等于
$\omega$ 大于

记不到就都当做一样的就是了

简单来说, 如果一个算法的时间复杂度能表示为一个如下所示的递推关系式:

\[T(n) = aT(\frac{n}{b}) + f(n)\]

那么$T(n)$的复杂度可以通过如下分类讨论得到:

  • $f(n)=O(n^c), c<\log_ba$则有

    \[T(n) = O(n^{\log_ba})\]

    如$T(n)=8T(\frac{n}{2})+1000n^2$的复杂度为$O(n^{\log_28})=O(n^3)$.

  • $f(n)=O(n^c), c>\log_ba$则有

    \[T(n) = O(f(n))\]

    如$T(n)=2T(\frac{n}{2})+n^2$的复杂度为$O(n^2)$.

  • 存在一个非负整数$k$使$f(n)=\Theta(n^{\log_ba}\log^kn)$

    \[T(n)=\Theta(n^{\log_ba}\log^{k+1}n)\]

    如$T(n)=2T(\frac{n}{2})+10n$的复杂度为$\Theta(n\log n)$

简单来说就是$f(n)$和$n^{\log_ba}$谁增长快听谁的, 两个一样加个$\log n$.