「OI」OI 中的位运算和 bitset

本文来讲一讲 OI 中的位运算和位运算的应用

比如状压, 多重背包, bitset 各种优化 /cy

前备知识

位运算是啥?

位运算就是二进制运算

常见二进制运算 : and, or, not, xor

这里就不再详细介绍了 = = , 如果实在不会直接去 Google

左移 / 右移

比如 x << yx >> y

x << y 等价于 x×2yx \times 2^y 其中 yy 好像自动对大小 (width of type) 取模

img

好像使用位运算会比较快 乘 22 的整数次幂使用这个就可以了

x >> y 等价于 x2yx \over 2^y 其中 yy 好像也自动对大小 (width of type) 取模 这个是严格向下取整的, 直接在 C++x2yx \over 2^y 是向 00 取整的

位运算的一些应用

一些实用技巧(

lowbit(x) = x & (-x)

x - lowbit(x) = x & (x - 1)

xx 的后 ii 位: x & ((1 << i) - 1)

xx 的第 ii 位是否为1: (x & (1 << i)) > 0

一个例题

给定 mm,求 [0,2m)[0,2^m) 中有⼏个 xx 满⾜ xx ^(异或) 3x=2x3x = 2x

m106m \le 10^6

移项变成 x ^ (2x) = 3x

因为 x + 2x = 3x,所以这个异或不能抵消任何的 11

所以 xx 的⼆进制表示下不能有相邻的 11

所以 f[m]=f[m1]+f[m2]f[m]=f[m-1]+f[m-2]

二进制代表集合

集合二进制操作

集合可以使用一个 bool 类型的数组表示, fif_i 代表第 ii 个元素是否在集合里

在全集⼤⼩⽐较⼩(通常在 3232 以内)的情况 我们可以使用⼀个 unsigned int 表⽰⼀个⼦集。

⼆进制位为1代表⼦集中有这个元素, 0代表没有。

其中我们可以通过位运算获取状态

下面给出一些操作的代码

定义一个二进制集合

1
unsigned int a;

获取第 pos 个元素是否在集合中

1
2
3
inline bool get (const int &pos) {
return a >> pos & 1;
}

aa 中插入第 pos 个元素

1
2
3
inline void add(const int &pos) {
a |= 1U << pos;
}

aa 中删除第 pos 个元素

1
2
3
inline void del(const int &pos) {
a &= ~ (1U << pos);
}

aa 中第 pos 个元素存在性取反

1
2
3
inline void change(const int &pos) {
a ^= 1U << pos;
}

求两个几何的交 / 并 / 异或

1
2
3
4
5
unsigned int a, b;
// ...
a & b; // 交
a | b; // 并
a ^ b; // 异或

aa 集合的补

1
2
3
inline unsigned int ex() {
return ~a;
}

二进制枚举子集

1
2
3
4
int S; // the set
for (register int i = S; i > 0; i = (i - 1) & S) {
/* .. Code .. */
}

简单的题目

一个例题 「CTSC2017」吉夫特

给定⼀个数组 a[1n]a[1\to n],求它有⼏个⼦序列 b[1m]b[1\to m] 满⾜对于 [2,m][2,m] 中的所有 ii 都有 (b[i] & b[i1])=b[i1](b[i]\ \&\ b[i-1]) = b[i-1]

保证 aa ⾥的元素互不相同

1n211985, 1a[i]2333331\le n\le 211985,\ 1\le a[i] \le 233333

一个很暴力的想法

fif_i 表示以 aia_i 结尾的满⾜条件的⼦序列有⼏个

计算 fjf_j 时,枚举 aja_j 的⼦集,看看在不在 a1(j1)a_{1\to (j - 1)} ⾥,然后转移

时间复杂度 O(318)O(3^{18})

看上去复杂度很⼤,实际上是能过的 (wys)

考虑折半思想

考虑现在要计算 fif_i

tx,y=(fj)t_{x,y} = \sum(f_j),其中 jj 满⾜:

  1. 1j<i1\le j < i
  2. aj=c(29)+ba_j=c*(2^9)+b,则有 b=yb=yx&c=cx\&c=c

则假设 ai=c(29)+ba_i=c*(2^9)+b,枚举 bb 的⼦集 rrfi+=tc,rf_i += t_{c,r}

时间复杂度: O(n×29)O(n\times 2^9)

二进制入门

如何⽐较两个数的⼤⼩

这个咋做啊

⽐较两个数的⼤⼩ 对于两个数 AABB,⽐较数的⼤⼩是从⾼位往低位找到第⼀ 个 AABB 不同的位,然后⽐较即可

对于⼆进制也同理,例如 11000111110000,从⾼往低位找,发现左数第三位这两个数不同,通过判断这⼀位可以发现后者较⼤

通过这个很显然的原理,我们可以进⾏⼀些 简单 的贪⼼

一些题目

一些题目 「NOI2014」起床困难综合征

nn 扇⻔,每⼀扇⻔由⼀个位运算符( & , ^ , | )和⼀个数 xx 组成,通过这扇⻔后,如果原来的攻击⼒为t,那么攻击⼒会变成 xxtt 做对应的位运算

现在你要从 [0,m][0,m] 中选⼀个初始攻击⼒,然后依次通过这 nn 扇⻔,要求最⼤后最后得到的攻击⼒

n105n\le 10^50Input1090\le \text{Input}\le 10^9

一句话题解:

从⾼位往低位确定

每次模拟⼀下这⼀位是 vv 的话,经过所有⻔后变成什么, 然后贪⼼选就⾏了

一些题目 ⼀道数位dp题

给定 nn , mm ,问有⼏个不⼤于 nn 的数 xx,满⾜对于所有 i>0i > 0,有 x & ((1 << i) - 1) <= m & ((1 << i) - 1)

n,m260n,m\le 2^{60}

考虑从低位往⾼位进⾏ 数位 dp

记录⼀下当前已经确定的位和 nn, mm 的⼤⼩关系

或的单调性

(XY)>=X(X|Y)>=X

给定⼀个⻓度为 nn 的数组 a[1n]a[1\to n],定义 f(l,r)=a[l]a[i+1]..a[r]f(l,r)=a[l]\;|\;a[i+1]\;|\;..a[r]

求有⼏种不同的 f(l,r)

1n1051\le n\le 10^5 0A[i]<2310\le A[i]<2^{31}

固定 ll,只有 O(logA[i])O(\log A[i]) 个不同的 f(l,r)f(l,r)

考虑固定 ll 后,从左往右枚举 rr,每次 f(l,r)f(l,r) 变化,当且仅当 a[r]a[r] 有某⼀位是 11,且 a[lr1]a[l\to r-1] ⾥这⼀位都不是 11

所以预处理⼀下:在 a[ln]a[l\to n] ⾥,对于每⼀位 ii ,第⼀个 满⾜第 ii 位是 11 的数,假设这个位置是 w[i]w[i]

那么 check ⼀下所有 f(l,w[i])f(l,w[i]) 即可,最后再⼤⼒去重⼀下

时间复杂度: O(nlogA[i])O(n\log A[i])

异或排序

题目来源: Hihocoder 1509 异或排序

给定⼀个⻓度为 nn 的⾮负整数序列 A[1n]A[1\to n],求有多少个不同的整数 SS 满⾜以下条件

  1. 0S<2600\le S < 2^{60}
  2. 对于所有 [1,n1][1,n-1] 中的 ii ,有 (A[i](A[i]^S)<=(A[i+1]S)<=(A[i+1]^S)S)

1n20,0A[i]<2601\le n\le 20, 0\le A[i] < 2^{60}

考虑⼀下对于 a,b ,有哪些 S 满⾜ (aS)<=(bS)(a^S)<=(b^S)

找到 aa ^ bb 的最⾼位,如果这⼀位⾥ aa00bb11,那么 SS 这⼀位必须是 00,否则必须是 11

所以每个 (A[i](A[i] ^ S)(A[i+1]S)\le (A[i+1] ^ S)S) 其实是限制了 SS 的某⼀位的 值

把限制全部搞出来算⼀下就⾏了

时间复杂度: O(nlogn)O(n\log n)

序列的值

定义 f(b[1m])f(b[1\to m]) 为:有⼏个 [0,m1][0,m-1] 中的 ii 满⾜: b[1i]b[1\to i] 的异或和 <b[1i+1]< b[1\to i+1] 的异或和

给定⼀个数组 a[1n]a[1\to n],对于 a[1n]a[1\to n] 的每个⼦序列 b[1m]b[1\to m],求 f(b[1..m])f(b[1..m]) 的和

1n105,0A[i]<2311\le n\le 10^5, 0\le A[i]<2^{31},答案对 998244353998244353 取模


先写到这里吧QAQ (有空再补

坚持原创技术分享,您的支持将鼓励我继续创作!