重要知识点

卡特兰数

以下是一些卡特兰数 $C_n$ 的应用：

• 二叉树计数

  • $n$ 个结点的不同形态的二叉树的数量是卡特兰数 $C_n$。

• 括号匹配

  • $n$ 对括号的有效组合数。

• 栈操作序列（出栈顺序）

  • $n$ 个元素的出栈顺序数。

• 凸多边形的三角划分

  • $n+2$ 条边的凸多边形划分成三角形的方法数。

• Dyck路径（格路问题）

  • 从 $(0,0)$ 到 $(2n,0)$，每次向右上或右下移动一步，且不越过 $x$ 轴的路径数。

• 满二叉树计数

  • $n+1$ 个叶子的满二叉树的数量。

• 表达式加括号

  • $n+1$ 个因子的乘法表达式加括号的方式数，例如：$4$ 个因子 $a,b,c,d$ 有 $5$ 种加括号方式：$(a(b(cd))),(a((bc)d)),((ab)(cd)),((a(bc))d),(((ab)c)d)$。

• 棋盘不相交对角线

  • $n\times n$棋盘上放置不相交的对角线（从左上到右下）的方法数。

• 凸多边形划分

  • $n+2$ 边形的顶点配对成不相交的弦的方式数。

---

主定理

主定理（Master Theorem）是用于求解分治算法递归式时间复杂度的一个强大工具。它适用于形式如下的递归关系：

$$T(n)=a\times T(\frac{n}{b})+f(n)$$

其中：

• $a\ge 1$（子问题的数量）；

• $b>1$（问题规模缩小的倍数）；

• $f(n)$ 是递归之外的计算成本（分割和合并的成本）。

主定理通过比较 $f(n)$ 和 $n^{{\log }_{b}a}$ 的大小关系，将递归式的解分为三种情况：

• $f(n)<n^{{\log }_{b}a}$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$；

• $f(n)=n^{{\log }_{b}a}$，则 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$；

• $f(n)>n^{{\log }_{b}a}$，则 $T(n)=\mathrm{\Theta }(f(n))$。

这只是简化过的情况，可以自行去了解更加详细的主定理。

---

存储单位

$\text{bit}$（比特，即一位二进制）

$\text{Byte}$（字节，即一个英文字符）

$1\text{Byte}=8\text{bit}$

$\text{KB}\to \text{MB}\to \text{GB}\to \text{TB}\to \text{PB}$

---

Windows 与 Linux 的一些操作命令

操作描述	Windows 命令	Linux / Unix 命令
列出目录内容	dir	ls
改变当前目录	cd <目录路径>	cd <目录路径>
返回上一级目录	cd ..	cd ..
显示当前目录路径	cd	pwd
创建新目录	mkdir <目录名>	mkdir <目录名>
删除空目录	rmdir <目录名>	rmdir <目录名>
删除文件	del	rm
复制文件	copy	cp
移动/重命名文件	move	mv
查看文件内容	type	cat
分页查看文件内容	more	less
查找文件	dir /s <文件名>	find / -name <文件名>
查找文本	findstr "文本" <文件>	grep "文本" <文件>

---

排序

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	是否稳定
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
基数排序	$O(n\times k)$	$O(n\times k)$	$O(n\times k)$	$O(n+k)$	稳定
希尔排序	$O(n^{1.3})$	$O(n)$ 或 $O(n\log n)$	$O(n^2)$	$O(1)$	不稳定
TimSort	$O(n\log n)$	$O(n)$	$O(n\log n)$	$O(n)$	稳定

• 基于关键字比较的算法：冒泡排序，选择排序，插入排序，快速排序，归并排序，堆排序。

---

09/16

• 层次遍历是按层从小到大，每一层从左到右的顺序遍历。

• 5 个没有区别的结点构成不同形态的二叉树的种类的个数。

  • 因为卡特兰数 $C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$ 能表示具有 $n$ 个结点的不同二叉树的形态数，所以答案为 $C_5=\frac{1}{6}(\genfrac{}{}{0ex}{}{10}{5})=42$；
  • 由于我比较蒟蒻，我的方法是令 $f_{i,j,k}$ 表示 $i$ 个点，$j$ 层数，最后一层有 $k$ 个点的方案数，然后慢慢转移。其实 $5$ 个点还是能接受的。

• 线性表若采用链表存储结构，内存中可用存储单元的地址可以是不连续的（即不一定要求地址连续）。

  • 链表不需要连续的内存空间，而是利用分散的内存块通过指针串联起来。这与数组（顺序存储结构）形成对比，数组要求连续的内存空间。

• 在 Linux 系统中，比较两个文件有无不同之处的命令是 diff。

  • 在 Windows 系统中应该是 fc。

• 断电之后仍能保存数据的（非易失性存储器）有 硬盘、固态硬盘、U盘/闪存驱动器、光盘、ROM（只读存储器） 等；易失性存储器有 RAM (可读写储存器)、Cache (高速缓存)、显存 （VRAM） 等。

• 田忌赛马问题

  • 站在田忌角度思考问题，考虑贪心，对两人的马的能力值进行排序，先比较两人最好的马，若不能赢，则比较两人最差的马，若还不能赢，就用田忌最差的马去换齐王最好的马，尽量平局。
  • 证明：其实就是能赢就赢嘛，如果想用田忌较弱的赢齐王较强的，再用田忌较强的赢齐王较弱的，那么这样的对局也可以变成用田忌较强的赢齐王较强的，再用田忌较弱的赢齐王较弱的，后者的方法不劣。

---

09/17

• 有红、黄、蓝、绿四种颜色的小旗，分别有 $2,2,3,3$ 面，任意取出三面按顺序排成一行，表示一种信号，那么这些旗子总共可以表示不同的信号的种数。

  • 考虑分类计数： 1.三个颜色都不同时，有 $A_4^3=24$ 种； 2.两个颜色相同，一个不同时，有 $4\times 3\times (\genfrac{}{}{0ex}{}{3}{1})=36$ 种，其中重复的颜色有 $4$ 种选择，剩下 $3$ 种颜色中选出一个单独放进去，位置有 $(\genfrac{}{}{0ex}{}{3}{1})$ 种选择； 3.三个颜色都相同时，只能放蓝和绿色的小旗，故有 $2$ 种。
  • 综上所述，这些旗子总共可以表示不同的信号种数为 $24+36+2=62$ 种。

• $T(n)$ 表示某个算法输入规模为 $n$ 时的运算次数。如果 $T(1)$ 为常数，且有递归式 $T(n)=2\times T(\frac{n}{2})+n-3$，求 $T(n)$。

  • 有两种做法：递归树法和主定理法。这里将主定理法： $a=2,b=2,f(n)=n-3$； $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$； $f(n)=n-3=\mathrm{\Theta }(n)$； 所以属于第二种情况 $f(n)=n^{{\log }_{b}a}$ 时，$T(n)=\mathrm{\Theta }(n\log n)$。

• 某学校来了一位新老师，三个同学猜测新老师教什么科目，小美说：“不是教语文，也不是教数学”；小元说：“不是教数学，一定是教英语”；小天说：“不是教英语，一定是教数学”。他们三人中有一人全猜对了，一人全猜错了，还有一人只猜对了一半。问：新老师究竟教什么科目？

  • 分别假设新老师为语文，数学，英语老师，接着判断三人的正确性，结合提示，得出最后的结果即可。

• 方程 $a\times b=(a\vee b)\times (a\wedge b)$，在 $a,b$ 都取 $[0,15]$ 中的整数时，存在解的组数。

  • 成立的前提是 $a$ 的二进制位是 $b$ 的子集，或 $b$ 的二进制位是 $a$ 的子集（即一个数包含另一个数的所有位置）。
  • 那么答案就是 $2\times 3^4-16=146$，其中： 枚举 $a$ 的子集 $b$ 为 $\sum _{k=0}^4(\genfrac{}{}{0ex}{}{4}{k})2^k$，利用二项式定理，得为 ${(1+2)}^4=81$，$a$，由于对称 $a\subseteq b$ 和 $b\subseteq a$ 的情况，乘以 $2$；最后减去 $a=b$ 时重复计算的 $16$ 次。

---

09/18

零碎的做了一些题，虽然依旧被薄纱（特别是 2024-S 最后一题），但是没什么特别必要记录的题。

做前面的选择题还要考虑暴力模拟 dp 吗？？？

• 关于 memset

memset(a,x,sizeof a) 中 $x$ 可能为 0x00,0xff,0x1f,0x3f,0x7f,0x80,0xcf,0xef 等。

拿 0x3f 举例，在 int 下就是 $(3F3F3F3F{)}_{16}$，在 long long 下就是 $(3F3F3F3F3F3F3F3F{)}_{16}$。

初始化值	int 数组效果 (32位)	long long 数组效果 (64位)	有符号 int 值	有符号 long long 值	常见语义
0x00	0x00000000	0x0000000000000000	$0$	$0$	零
0xFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF	$-1$	$-1$	负一
0x3F	0x3F3F3F3F	0x3F3F3F3F3F3F3F3F	$1,061,109,567$	$4,557,014,598,15,606,335$	安全正无穷
0x7F	0x7F7F7F7F	0x7F7F7F7F7F7F7F7F	$2,139,062,143$	$9,223,372,036,854,775,807$	较大正数
0x80	0x80808080	0x8080808080808080	$-2,139,062,144$	$-9,223,372,036,854,775,808$	负无穷
0xCF	0xCFCFCFCF	0xCFCFCFCFCFCFCFCF	$-808,464,433$	$-3,619,344,231,715,046,737$	大负数
0xEF	0xEFEFEFEF	0xEFEFEFEFEFEFEFEF	$-272,716,322$	$-1,172,812,30,314,442,385$	较大负数

注意事项：

• "正无穷" → 选择 0x3F

• "负无穷" → 选择 0x80

• "-1" → 选择 0xFF

• 避免使用 0x7F：有溢出风险（$2\times \text{0x3F}<\text{0x7F}$）

• 谨慎使用 0xCF、0xEF

• 特殊的时候可能运用到其他的类似于 0x1f。

---

09/19

初赛前最后一晚，复习些啥好呢？？？

• 阅读程序小技巧：

  • 对于二进制函数 $(x,y)$，可以先化简再分别代入 $x=0/1,y=0/1$ 列表找规律。
  • $\vee$ 是不进位加，$\oplus$ 是不退位减。

• 关于二进制之间的转化：

  • $x+y=x\wedge y+x\vee y$
  • $x\oplus y=(x\wedge \mathrm{\neg }y)\vee (\mathrm{\neg }x\wedge y)$
  • $(x\wedge y)\oplus ((x\oplus y)\vee (\mathrm{\neg }x\wedge y)$（2024-S 中出现，可以通过找规律得到）