SOS Dynamic Programming [Tutorial] – usaxena95 on CodeForces
通过优化，将子集求和类相关问题的时间复杂度由朴素的 $\mathrm{O}(3^n)$ 优化到 $\mathrm{O}(n\times 2^n)$。
作者： NGC5457
-
第二届天元编程邀请赛（提高组） 解题报告
一场相当有收获的比赛。比赛链接
A – 石老板举世无双
解法一
尝试观察规律。我们发现，在完成$s$次操作以后，左端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]$，右端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)$。假如现在我们达到最终状态，其$l=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}$。那么，在$x$的二进制表示中，如果从高到底第$\mathrm{pos}$位为$1$，则在第$\mathrm{pos}$轮中，有
check (mid) == 0，向右区间递归；否则向左区间递归。这是很容易解释的：若向右递归，则右端点不变。而在下一层，右端点表示中$a, b$的所有系数乘$2$，所以体现为二进制位末尾添一个$0$。反之，就变成$(x+(x+1))/2$，在下一层中体现为$2x+1$。如果其有$\operatorname{popc}(x)$位为$1$，则到达该状态的概率为$p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$。以$s=3$时的状态$l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}$为例。$2$的三位二进制表示为$\text{0b010}$，则推断出在前三轮分别向右、左、右区间递归，到达其的概率为$p_0p_1^2$。 （更多…）
-
随记 – 五月二日 – 初探格雷码
格雷码（Gray code）是一种任意两相邻项有且仅有一位不同的二进制编码。
直观来看，其构造方式如下：假如我们构造出了格雷码$g_{0, 1, \cdots, 2^m-1}$，现在考虑构造$m+1$位格雷码。我们将前$2^m$位复制一遍，然后反转在原序列中的位置，也即$g’_{2^m+i}=g_{2^m-1-i}, i \in [0, 2^m)$；然后在最后$2^m$项格雷码的左侧分别添上$1$。由此有$g_{2^m+i}=g_{2^m-1-i}+2^m$。
实际操作时，可以采用相邻两项的异或值与前缀异或和快速构造。假若有$g_x$与$g_{x-1}$的异或值序列$s_{1, 2, \cdots, 2^m-1}$，那么便有$s_{2^m+i}=s_{i}, i \in [1, 2^m)$，同时有$s_{2^m+1}=g_{2^m+1} \oplus g_{2^m}=2^m$。
例如，前8项格雷码的二进制表示为：$\{\text{0b}000, \text{0b}00{\color{blue}1}, \text{0b}0{\color{blue}1}1, \text{0b}01{\color{blue}0}, \text{0b}{\color{blue}1}10, \text{0b}11{\color{blue}1}, \text{0b}1{\color{blue}0}1, \text{0b}10{\color{blue}0}\}$，相邻两项异或值为$\{1,2,1,4,1,2,1\}$。
-
转载与模板 – Bron-Kerboscht 极大团算法
Algorithm 457: Finding All Cliques of an Undirected Graph [H] – Coen Bron* and Joep Kerboscht – Archives of Communication of ACM
原Essay详细而准确地描述了该算法的过程，不需要额外的注解也能轻松理解。若英语阅读吃力，也有一份不错的中文详述：
极大团(maximal clique)算法:Bron-Kerbosch算法 – Bowiee – 简书
下面给出一份参考实现，能够找出所有极大团。使用
unsigned long long存储各状态点的集合，二进制表示下从低到高第$(x-1)$位为$1$表示点$x$存在于集合中。 （更多…） -
AtCoder ARC138D – Differ by K bits 简略题解
考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。
由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。
考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。
可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。
下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。 （更多…）
-
随记 – 四月九日 – 利用二进制数高效枚举集合
以下所有操作均可以通过递归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)$。
-
随记 – THUPC 2022 初赛 J – 画图 7KB的大模拟……？
考虑合并若干重叠线段。使其有序化后考虑每两个线段的交，如果其为空则新建一条独立线段，反之合并。
最后应当恰好有$7$条水平线段，$8$条垂直线段，否则依题意不可能拼凑出“$\textbf{THUPC}$”图形。
DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝，亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为$\mathrm{O}(7^5\times 8^5)$，实际远远达不到。
赛时
1A（实际上因为无主函数返回值RE了两次）$7\text{KB}$代码：
（更多…） -
CF1649F – Serious Business – 题解与思路重现
CodeForces Round #755 Div.2 F / Div.1 D Serious Business
此题整整困了我一天半，耗费了好几张草稿纸。实在走投无路，翻看题解，却发现正解曾经近在咫尺。有必要稍作整理。
考虑DP。
错误转移1
这道题与清理班次（《算法竞赛进阶指南》上的一道例题）过于相似，都是“给定一些段落$[l_p, r_p]$，选择其中一些完整覆盖$[l_0,r_0]$，求最小花费”的形式。记上述花费为$f(l_0, r_0)$。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在$x_2$位置从第$2$行转到第$3$行，利用数据结构维护所有$x_1\leq x_2$，在$x_1$转移到第二行，解锁到达$x_2$的最小代价。对于各行前缀和，我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在$\mathrm{O}(n \log n)$的时间内，计算出对于一个固定的起点$l_0$，所有$f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0$的值。 （更多…）
-
随记 – 三月四日 – DP求解强制包含部分元素的序列计数问题
被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。
为什么题解TMD是错的？即$g(i,j,k)$表示“每个位置有$i$类元素可选，且序列中必须包含指定的$j$类元素的，长度为$k$的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数：$\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$。
通过容斥原理，我们可以计算出至少有$0,1,2,\dots,j$个$T$中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即：
$$g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$$。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为$\mathrm{O}(j)$。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解（虽然DP更加简洁直观）。