OI

以下所有操作均可以通过递归DFS每一位并作相应判断实现。但以下写法实现简洁、常数较小，不失为一种优美的技巧。

下文采用$S_i$表示第$i$个集合，$\text{msk}$表示其二进制表示。

简单集合运算

• 并：$S_1 \cup S_2 \leftarrow \text{msk}_1 \mid \text{msk}_2$
• 交：$S_1 \cap S_2 \leftarrow \text{msk}_1\space\&\space\text{msk}_2$
• 差：$S_1 \setminus S_2 \leftarrow \text{msk}_1\space\&\space(\sim\text{msk}_2)$
• （相对于该二进制数类型最大值的）补集：$\sim\text{msk}$
• 对称差集：$S_1 \Delta S_2 \leftarrow {\text{msk}_1}^{\space\land}\space \text{msk}_2$

（更多…）

介值定理

若有连续函数$f: [a, b] \mapsto \mathbb{R}$，且不失一般性地，令$a< b, f(a)< f(b)$，则对于任意实数$x\in [f(a), f(b)]$，存在$c \in (a, b), f(c)=x$。

容易由实数完备性证明。直观理解，即可以画出一段连续曲线，其两端点分别为$(a, f(a)), (b, f(b))$，而笔不离开纸面。

离散函数值上的介值定理

若存在函数$f(x) \in \mathbb{Z}, x \in \mathbb{Z}$，且满足$|f(x)-f(x+1)|\leq 1$，则对于$a<b, f(a)<f(b)$，若有整数$x \in [f(a), f(b)]$，存在一个$c \in (a, b), f(c)=x$。

证明显然。

在OI中的实际意义？

我们常遇到这样一类函数：在某些数列上进行统计，邻项函数值之间的差为$\{-1, 0, 1\}$，如括号序前缀和（$\text{‘(‘} \rightarrow +1, \text{‘)’} \rightarrow -1$），则可以通过上述性质判断某两点之间函数值是否存在。

例如CF1695C – Zero Path，本质上路径上数字和是一个满足上述条件的整数离散函数。

再例如CF1658F – Juju and Binary String，可以将题意转化为一个函数$f(x) \in [0, n], x \in [0, n] \land \exists x_p, f(x_p) >0$，且满足上述性质；同时有函数$g(x)=x, x \in [1, n]$，则可以证明一定存在$x_0, g(x_0)=f(x_0)$。

考虑合并若干重叠线段。使其有序化后考虑每两个线段的交，如果其为空则新建一条独立线段，反之合并。

最后应当恰好有$7$条水平线段，$8$条垂直线段，否则依题意不可能拼凑出“$\textbf{THUPC}$”图形。

DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝，亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为$\mathrm{O}(7^5\times 8^5)$，实际远远达不到。

赛时1A（实际上因为无主函数返回值RE了两次）$7\text{KB}$代码： （更多…）

广义斐波那契数列

定义：任何形如$f_i=f_{i-1}+f_{i-2}, f_1=x,f_2=y$的数列，称为广义斐波那契数列。

$F_1=F_2=1$的斐波那契数列的通项公式

$$F_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$

证明方法多样，可惜我都不会。知乎 – 斐波那契通项公式是怎样推导出来的？

下文中以$F_n$代指斐波那契数列的第$n$项，$f_n$代表广义斐波那契数列的第$n$项。

（更多…）