CSP 初赛

日期:
标签: oi

主定理

对于一个递推关系式子:。其复杂度为:

参考维基百科,与算法导论对应章节。

其实就是找 两个部分复杂度较大的。

复杂度记号

指和 有关的多项式,同理 实际上就是 ,即和 有关的多项式。

错排问题

考虑容斥,若存在 个数在原来的位置上,这种情况的数量是 ,所以可以得到错排公式:

也可以考虑递推,对于第 个数,假设它被放到位置 构成错排,考虑第 个数的位置:

故得到递推公式:

OEIS: A000166

卡特兰数

从最经典的出栈序列计数开始。将入栈记作 -1,出栈记作 +1,可以得到一个长度为 2n 的序列,一个合法的出栈序列满足其任意一个前缀和非负,且总和为 0。

考虑统计不合法的出栈序列。对于任意一个不合法的出栈序列,找到第一个满足前缀和等于 -1,的位置 p,将 p 之前的所有数翻转,即 -1 变为 +1,+1 变为 -1,得到一个长度为 2n 且有 n+1 个 +1,n-1 个 -1 的序列。容易得到对于任意一个有 n+1 个 +1,n-1 个 -1 的序列都能对应一个不合法的出栈序列,这是个双射。故不合法序列的总数为 ,总共合法序列的数量为

OEIS: A000108

Twelvefold way

个球, 个盒子。

个有标号球放入 个有标号盒子

个有标号球放入 个有标号盒子,每个盒子至多一个球

个有标号球放入 个有标号盒子,每个盒子至少一个球

第二类斯特林数统计的是不区分盒子时的数量,乘上 表示考虑 个盒子的顺序。

个无标号球放入 个有标号盒子

每个盒子预先放上一个球,即转化为 个无标号球放入 个有标号盒子,每个盒子至少一个球。

个无标号球放入 个有标号盒子,每个盒子至多一个球

考虑哪些盒子放了球。

个无标号球放入 个有标号盒子,每个盒子至少一个球

插板法,考虑 个球之间有 个空位,在这些空位中插入 个分隔。

个有标号球放入 个无标号盒子

盒子是可空的,所以枚举有多少个盒子空,转化为每个盒子至少一个球的问题。

个有标号球放入 个无标号盒子,每个盒子至多一个球

个有标号球放入 个无标号盒子,每个盒子至少一个球

第二类斯特林数就是这样定义的。

计算第二类斯特林数,有递推公式:

考虑第 个球应该放在哪里。如果它单独放一个盒子,那么就是转化为 ;如果它放入一个现有的非空盒子,那么就是

个无标号球放入 个无标号盒子

每个盒子预先放上一个球,即转化为 个无标号球放入 个有标号盒子,每个盒子至少一个球。

个无标号球放入 个无标号盒子,每个盒子至多一个球

个无标号球放入 个无标号盒子,每个盒子至少一个球

相当于将 拆分成恰好 个正整数的方案数。

计算 ,有转移方程:

即考虑拆分方案中不存在 和存在 的情况。如果不存在 ,那么把方案中所有数减一,转化为 ;如果存在 ,那么去掉这个 ,转化为

命令

就列一些常用的。我非常反感考这种东西。

历史

2023 年,第 40 届 NOI,第 29 届 NOIp,第 35 届 IOI,第 5 届 CSP。

ASCII

哈夫曼树

  1. 对于给定的 个权值,先建立 个有 个节点的树。
  2. 不断进行以下操作,直到剩下 棵树:
    1. 选取权值最小的两棵树 ,将他们分别为左右子树,构造一颗新的树,其权值为 的权值加 的权值。
    2. 删除

补码

对于一个长度为 的二进制数 ,其补码为