《算法竞赛进阶指南》扫题 - part1

2024-02-04 21:42:58

black_trees 的重来之路-part1：

这是lyd的蓝书的扫题计划。

共 323 题，预计在8个月之内扫完 80%。

我会单独新建一个文件夹，把所有我重来的代码都放进去。

在做完每个章节之后会有归档，进度可以在 Github 上查看。

这是快速幂的板子题，让你求 $a^b \% p$ 的值。

首先有一个非常重要的二进制拆分思想：

对于 $\forall x \in \mathbb{N}^* $ ，可以把 $x$ 的二进制表示写成如下形式 :

$c_1\times 2^{0} + c_2\times 2^{1} + ... + c_k\times 2^{k-1}$。

其中 $c_i$ 表示 $x$ 在二进制下的第 $i$ 位（从 $1$ 开始）的数字是多少。

然后我们考虑把 $b$ 这样子拆分。

实现只需要每次把 $b$ 的最低位 $i$ 取出来，如果为 $1$ 那么就把 $a^{2^{i-1}}$ 乘到答案里面，就能算出 $a^b$。

$a$ 可以利用 $a^{2^{k}}=(a^{2^{k-1}})^2$ 这个式子来递推处理。

记住答案最开始要设置成 $1$ 对 $p$ 取模以避免 $p=1$ 的时候答案出错。

考虑把 $b$ 像上一题一样拆分，那么每次令 $a=2a$ ，如果 $b$ 的当前最低位是 $1$ 那么累加答案。

依旧是快速幂的模板题。

只需要分别求个快速幂然后全部加起来即可。

不要忘记加的时候取模。

状压 DP 的模板题。

我们设 $f_msk$ 表示走到的点集合为 $msk$ 的时候的最短路径。

但是发现这样子没法表示状态，所以再加一维，$f_{msk,i}$ 表示表示走到的点集合为 $msk$ ，且当前在 $i$ 的时候的最短路径。

那么先枚举状态，然后枚举所有点对来转移即可。

很精妙。

我们发现如果直接去找这个数是什么会特别麻烦。

不妨换个思路，因为位运算的特点之一就是不进位（比如异或就是二进制下的不进位加法）。

所以每一位之间不会干扰。

我们考虑枚举答案的每一个数位到底是 $0$ 还是 $1$。

然后对于每个位置，我们取出每一扇门上数字在二进制下的这一位进行运算。

如果这一位选 $0$ 只需要记录当前的攻击力最大值即可，选 $1$ ，那么还需要累加答案。

复杂度在 $\log$ 级别。

不过我不是很明白，为什么我的Code里面，如果枚举的这个答案的位数是 $30,29$ 位才能过。

$32,31,28$ 都或多或少会挂一两个点呢？