前言
文章作为面向团队内部成员的读物，我就语言不那么严谨直接开始瞎胡扯了。
根据 @Tighnarri 的建议，我们来写一些大家可能会用到的与二进制有关的简单小玩意，希望大家喜欢。
常识部分
世界上只有 \(10\) 种人，一种的懂二进制的人，一种是不懂二进制的人。
1、原码、补码、反码
机器存储中，二进制数的第一位代表符号位，正数为 \(0\)，负数为 \(1\)。
- 原码：符号位加上真值的绝对值。
- 反码：正数的反码是其本身；负数的反码就是在其原码的基础上，符号位不变，其余各位取反。
- 补码：正数的补码就是其本身；负数的补码就是在原码的基础上，符号位不变，其余各位取反，最后 \(+ 1\)。即，在反码的基础上 \(+1\)。
这有啥用呢。
当你想表示一个数，其二进制下全是 \(1\) 时，这个数是 \(-1\)。
2、双目运算
一个数的二进制数是一个 \(01\) 串，这十分简单。
于是我们有 \(\&\) \(|\) \(\oplus\) 等双目运算符，本质是把两个数在二进制下的 \(01\) 串进行位运算。
我们常用的还有左右移位，右移后在最低位补 \(0\)，左移后在最高位补符号位。
状态压缩
把每个物品看做一个二进制串的某一位，存在就是 \(1\)，不存在就是 \(0\)，把这个 \(01\) 串表示为一个十进制数，就得到了当前的状态。
同时我们还得会一些小玩意。
- 合并两种状态用 \(|\)
- 判断第 \(k\) 低位是几用 \((S>>(k-1))\&1\)
- 两种状态叠加后会改变原状态用 \(\oplus\)
- 判断两种状态是否有交集用 \(\&\)
- 枚举子集用 \(S_{0} = S,S_{0}=S\&(S_{0}-1)\)
- \(\_\_builtin\) 系列函数，我会在文章末尾列举一些常用的
1、就是单纯的状态压缩
这十分简单且有用，所以我们来看一道最短路题（千辛万苦找的最短路）。
给出 \(n \times m\) 的地下城的地图：
\(@\) 代表起点，\(\#\) 代表终点；
\(.\) \(\space\) 代表空地，\(*\) 代表障碍物；\(A \sim Z\) 代表带锁的门,对应的钥匙分别为 \(a \sim z\)；
\(a \sim z\) 代表钥匙。每一步只能往上下左右4个方向走一格，求最少步数。
可能存在多个同样的钥匙或门，用钥匙开门并不消耗掉钥匙。\(n,m \le 30\)
关键问题显然在于当走到一个门时，我需要知道当前自己是否携带了钥匙。
钥匙只有 \(26\) 种，所以我们完全可以用一个 \(26\) 位的十进制数表示出当前携带了哪些钥匙，于是这道题就做完了。
const int N = 25,INF = 0x3f3f3f3f;
int vis[N][N][1025]; char g[N][N];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n,m,sx,sy,fx,fy;
struct node{
int x,y; ll k;
int step;
};
inline int bfs(int x,int y){//最短路不用说吧
queue <node> q;
vis[x][y][0] = 1;
q.push({x,y,0,0});
while(q.size()){
node now = q.front();
q.pop();
if(now.x==fx && now.y==fy){//到地方了
printf("%d",now.step);
return 1;
}
for(int i=0;i<4;++i){
int tx = now.x+dx[i];
int ty = now.y+dy[i];
ll tk = now.k;
//如果当前能拿钥匙就拿，注意双目运算符
if(g[tx][ty]>='a' && g[tx][ty]<='z') tk |= (1ll<<(g[tx][ty]-'a'));
//如果当前是门，看看有没有带着对应的钥匙，注意判断二进制数某一位是否为一
else if(g[tx][ty]>='A' && g[tx][ty]<='Z')
if(!((tk>>(g[tx][ty]-'A'))&1)) continue;
if(tx<1 || ty<1 || tx>n || ty>m || g[tx][ty]=='*' || vis[tx][ty][tk]) continue;
vis[tx][ty][tk] = 1;
q.push({tx,ty,tk,now.step+1});
}
}
return 0;
}
int main(){
read(n,m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> g[i][j];
if(g[i][j]=='@'){
sx = i;
sy = j;
}
else if(g[i][j]=='#'){
fx = i;
fy = j;
}
}
}
bfs(sx,sy) ? 0 : printf("-1");
return 0;
}
2、状压 DP
就是把压缩的状态放到转移的数组里，就没了。
十分简单且不简单，所以我们来看一道简单的状压 \(dp\)。
P3118 [USACO15JAN] Moovie Mooving G
有 \(N\) 部电影，每部时长为 \(val_i\) 共放映 \(num_i\) 场，且第 \(i\) 部电影第 \(j\) 场的开场时间为 \(tim_{i,j}\)。
每部电影只能看一次，看电影的中途可以换电影，求连续看满时长 \(L\) 最少要看几部电影。
\(1\le N\le 20\)
\(N\le 20\) 所以直接状压，设 \(dp_s\) 表示在状态 \(s\) 时，可以连续看多久电影。
对于每个状态 \(s\)，暴力枚举接下来我们要看的电影。
因为要求看的电影数量尽可能少，所以每次应该选择最后一个不大于当前时间的电影场次。这个操作可以用 upper_bound 解决。
设当前选到了电影 \(i\)，只有 \(i\) 存在不大于当前时间的场次，才进行转移。当前状态应当与电影结束时间取最大值。
const int N = 25,INF = 0x3f3f3f3f;
int n,L;
int val[N],num[N],tim[N][1100];
int ans=INF,dp[(1<<20)+10];
int main(){
read(n,L);
for(int i=1;i<=n;++i){
read(val[i],num[i]);//电影时长、场次数量
for(int j=1;j<=num[i];++j){
read(tim[i][j]);//每场的开始时间
}
}
for(int s=0;s<1<<n;++s){
for(int i=1;i<=n;++i){
if((1<<(i-1))&s) continue;//电影已经看过
int idx = upper_bound(tim[i]+1,tim[i]+num[i]+1,dp[s])-(tim[i]+1);
if(idx>0) dp[s|(1<<(i-1))] = max(dp[s|(1<<(i-1))],tim[i][idx]+val[i]); //存在场次
}
if(dp[s]>=L) ans = min(ans,__builtin_popcount(s));//popcount求s中 1 的个数
}
printf("%d",ans==INF? -1 : ans);
return 0;
}
二进制拆分
二进制拆也是我们很喜欢的东西。
我们可以把一个数拆成若干个系数为一的 \(2\) 的幂的和，这可以做很多事情。
1、lowbit
对于个二进制数，如何求其最后一位 \(1\) 在哪。
最后一位 \(1\) 为：\(S\&(-S)\)。
可以粗略证明：
我们假设 \(S > 0\)，设 \(S\) 的二进制表示中，第 \(k\) 位为 \(1\)，第 \(0\) 至第 \(k-1\) 位都为 \(0\)。
现在我们对 \(S\) 的二进制进行取反操作，可以得到 ~\(S\) 的二进制表示中，第 k 位为 \(0\) ，第 \(0\) 至第 \(k-1\) 位都为 \(1\)。我们再将 ~\(S\) 进行加 \(1\) 操作，可以得到一个结果，就是 ~\(S+1\) 的第 \(k+1\) 位至其最高位都为 \(S\) 的二进制表示中相反的数字。然后我们再将 ~\(S+1\) 与 \(S\) 进行与运算，就可以得到我们想要的结果了。
负数同理。
于是可以快速对某个数二进制拆分。
我们只需要它的 \(1\) 位，直接 \(lowbit\) 即可。
2、二进制分组优化多重背包
多重背包中每个物品可以选多次，但当物品数量较大时，遍历每个数量并不优。
注意，我们对每个物品的数量进行二进制拆分。这样一个可以选 \(k\) 次的物品就变成了 \(\log{k}\) 个可以选一次的物品。
据说有人写过，不展开说了。
3、底数为 2 的运算
二进制还有一些比较有趣的性质。
- \(2^k = 1 << (k-1)\)
- \(S \mod 2^k\) 相当于取 \(S\) 二进制下的后 \(k\) 位
- \(S \div 2^k\) 相当于 \(S\) 左移 \(k\) 位
- \(S \times 2^k\) 相当于 \(S\) 右移 \(k\) 位
- \(\log{S}\) 相当于求 \(S\) 的最高位 \(1\) 的位置
我们最喜欢的 DS
我没啥会的，就瞎说俩奥。
1、树状数组
我管这个东西叫线段树中序遍历。
树状数组每个节点存一个前缀值。
我们对其管辖前缀 \(k\)，进行二进制拆分，其子树内节点为 \(k\) 二进制拆分后的值。
二进制拆分我们用 \(lowbit\) 即可，十分简单且快速。
\(BIT\) 不但常数优秀，而且还比递归线段树好写 \(\Large \theta\) 倍。
然而我不会并 \(BIT\)，所以就不继续讲了大家等 Bow 讲吧，我估计会很抽象。
2、01 Trie
建一棵二叉树，钦定边权为 \(0\) 和 \(1\)，这个树叫 \(01\) Trie。
考虑对两个数 \(k\) 和 \(q\) 做双目运算，需要对它们的二进制数每一位进行比较。
我们对 \(k\) 和 \(q\) 的二进制数从低位到高位建一棵 \(01\) Trie，钦定边权，于是此时的双目运算过程可以看作 \(01\) Trie 上走路。以此实现一些比较有趣的操作。
非常简单易懂，我们来看个简单的 01 Trie 题。
P4551 最长异或路径
给定一棵 \(n\) 个点的带权树，结点下标 \(1\sim n\)。
寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
\(n\le 1e6,w\le 2^{31}\)
显然对于一条从 \(u\) 到 \(v\) 的路径异或，我们看作两点
分别到根的路径异或值。
由于一个二进制数最高位越大，数就越大。所以我们贪心地在 \(01\) Trie 上走路，只要有一位不同就一定走过去。
模拟树上走路即可。
const int N = 2e6+10;
int n,ans;
struct{
int to,nex,w;
}edge[N<<1];
int head[N],edge_num;
inline void add(int x,int y,int w){
edge[++edge_num].to = y;
edge[edge_num].nex = head[x];
head[x] = edge_num;
edge[edge_num].w = w;
}
int sum[N];
void dfs(int now,int fu){//预处理
for(int i=head[now]; i;i=edge[i].nex){
int tto = edge[i].to;
if(tto==fu) continue;
sum[tto]=sum[now]^edge[i].w;
dfs(tto,now);
}
}
struct trie{
int ch[2];
}t[N];
int tot;
void build(int val,int x){
for(int i=(1<<30);i;i>>=1){
bool c=val&i;//取出二进制下这个数的当前位置
if(!t[x].ch[c]){
t[x].ch[c] = ++tot;
}
x = t[x].ch[c];
}
}
int query(int val,int x){
int ans=0;
for(int i=(1<<30);i;i>>=1){
bool c=val&i;
if(t[x].ch[!c]){//如果这一位可以进行异或就沿着这一条往下走
ans += i;
x = t[x].ch[!c];
}
else x = t[x].ch[c];//否则就沿着另一条路往下走
}
return ans;
}
int main(){
read(n);
for(int i=1,u,v,w;i<n;++i){
read(u,v,w);
add(u,v,w); add(v,u,w);
}
dfs(1,0);//预处理
for(int i=1;i<=n;++i) build(sum[i],0);//建 01 Trie
for(int i=1;i<=n;++i) ans = Max(ans,query(sum[i],0));//查询，取最大值
printf("%d\n",ans);
return 0;
}
然后我们再来看一道充满了我们喜欢的二进制的题。
P6587 超超的序列
给定一个序列 \(a_N\)，每次给出 \(x\) 和 \(y\)。每次对所有满足 \(i\equiv y\pmod{2^x}\) 的 \(a_i\) 进行修改和查询。
\(n\le 1e3,x\le 20,y\le 2^x\)
其他东西
1、二进制求 gcd
inline ll Gcd(ll x,ll y){
if(!x || !y) return x|y;
ll xz = __builtin_ctzll(x);
ll yz = __builtin_ctzll(y);
ll z = Min(xz,yz),diff;
y >>= yz;
while(x){
x >>= xz;
diff = x-y;
xz = __builtin_ctzll(diff);
y = Min(x,y);
x = Abs(diff);
}
return y << z;
}
2、__builtin 系列函数
__builtin 系列用来对数的二进制表示进行一些运算，复杂度近似 \(O(1)\)。
- __builtin_ctz 末尾 \(0\) 的个数
- __buitlin_clz 前导 \(0\) 的个数
- __builtin_popcount \(1\) 的个数
- __builtin_parity \(1\) 的个数的奇偶性
- __builtin_ffs 最高位 \(1\) 的位置
- __builtin_sqrt 开平方
常用于快速求 \(\log\)，以及状态压缩中的一些事情。
询问较少时，比提前预处理 \(\log\) 和 \(1\) 的个数要快很多。
后记
依旧是建议配合 OIWiki 食用。
题都是从我写过的题解里随机 rand 的，质量保真度 \(70\%\) 左右，请自行辨并进行选择。
看来下次得放多点 DS 压压惊了。