按位单独处理

  |  

摘要: 按位单独处理的技巧

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文来看一种位运算中的常见操作 — 按位单独处理。

关于位运算的基础知识,可以看这两篇文章: 位运算操作位运算疑难杂症

位运算的一个主要特点就是在二进制表示下不进位因此如果一个数经过一系列运算得到另一个数,而这些运算都是位运算的话,那么各个二进制位是可以单独处理的。


题目

998. 起床困难综合症

一个人的初始攻击力 x0,经过 n 道门,第 i 道门有一个运算 opti 和一个参数 ti,运算是 AND, OR, XOR 中的一种,参数是非负整数。

攻击力为 x 的人经过第 i 道门后,攻击力变为 x opti ti。

从 [0, m] 中选择一个数作为初始攻击力 x0,使得其依次经过 n 道门后的攻击力最大。求这个经过 n 道门后的最大攻击力。

算法

由于每道门的运算都是 AND, OR, XOR, 因此 x0 在经过每个门的运算时,二进制下是无进位的,也就是最终的攻击力的某个二进制位是 1 还是 0,仅取决于初始值 x0 中该位的值以及每道门的运算以及 ti 中该位的值。因此我们可以对每个位单独处理

对 m 从高位向低位枚举,每一位都取尽可能使得最终的 x 的该位为 1 的选择。

但是有一种情况要注意:如果最高位选择 1 会使得最终 x 的该位为 1,那么最高位就选 1,此时较低位由于 m 的大小限制可能无法自由选择。所以我们用一个 flag 表示当前是否已经可以自由选择,也就是不论选 0 还是 1,都不会超限, flag 为 true 表示已经可以自由选择。

第 i 位的选择过程如下:

1
2
3
4
5
6
7
8
9
10
如果 flag 为 false:
m 的第 i 位为 0,那么该位只能直接选 0
m 的第 i 位为 1,那么选择使得最终 x 的第 i 位为 1 的数:
如果两种选择都会使得最终 x 的该位为 1,那就选 0。
如果两种选择都会使得最终 x 的该位为 0,那也选 0。
如果其中一种选择会使得最终 x 的该位为 1,就做出该选择。
若最终选择为 0,flag 变为 true

如果 flag 为 true:
那么选择使得最终 x 的第 i 位为 1 的数,选 0 选 1 均可,已经不重要

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int forward(int j, int x, const vector<string>& op, const vector<int>& t)
{
int n = op.size();
for(int i = 0; i < n; ++i)
{
if(op[i] == "AND")
x = x & (t[i] >> j & 1);
else if(op[i] == "OR")
x = x | (t[i] >> j & 1);
else
x = x ^ (t[i] >> j & 1);
}
return x;
}

int main()
{
int n, m;
cin >> n >> m;
vector<string> op(n);
vector<int> t(n);
for(int i = 0; i < n; ++i)
cin >> op[i] >> t[i];
bool flag = false;
int ans = 0;
for(int j = 31; j >= 0; --j)
{
if(!flag)
{
if((m >> j & 1) == 0)
{
int x0 = forward(j, 0, op, t);
ans = ans | (x0 << j);
}
else
{
int x0 = forward(j, 0, op, t);
int x1 = forward(j, 1, op, t);
if((x0 ^ x1) == 0 || x0 == 1)
{
ans = ans | (x0 << j);
flag = true;
}
else
ans = ans | (x1 << j);
}
}
else
{
int x0 = forward(j, 0, op, t);
int x1 = forward(j, 1, op, t);
if(x0 == 1)
ans = ans | (x0 << j);
else
ans = ans | (x1 << j);
}
}
cout << ans << endl;
}

216. Rainbow的信号 (求数学期望)

给定一个信号数列 a,a 的长度为 N。

在 1∼N 这 N 个数中,等概率地选取两个数 l、r,如果 l > r,则交换 l、r。数列 a 的第 l 个数到第 r 个数的子数列记为 P。

A = 数列 P 的 xor 和的期望;B = 数列 P 的 and 和的期望;C = 数列 P 的 or 和的期望。

求 A, B, C 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入格式
第一行一个正整数 N。
第二行 N 个自然数,a[0] ~ a[N - 1],表示 Freda 接到的信号。

输出格式
一行三个实数,分别表示 xor 和、and 和、or 和的期望,四舍五入保留 3 位小数,相邻两个实数之间用一个空格隔开。

数据范围:
0<=N<=1e5
a[i] <= 1e9

输入样例:
2
4 5
输出样例:
2.750 4.250 4.750

算法

题目比较长,简单来说整个过程分为两步,第一步选出 l 和 r,第二步是在 l, r 确定的情况下,求 A[l..r] 的 and 和、or 和、xor 和的数学期望。

这两步通过全期望公式,合成最终答案。全期望公式如下

其中 p(Y=y) 是 l, r 的各种可能性的概率,E(X|Y=y) 是条件期望,l, r 固定时,所求目标的期望。

由 l, r 的选取方式,l = r 的情况的概率为 1 / N^2l != r 的情况的概率为 2 / N^2

由于 and, or, xor 都是没有进位的,因此各个二进制位取 0 还是 1 是独立的。所以我们想到按位计算答案,枚举二进制下的每一位,枚举 A1 ~ AN 的每个数,当前枚举到第 i 个数,此时可以利用前面维护的值更新答案。

当前枚举到的数位为 k,设 B 是长为 N 的 01 序列,Bi 为 Ai 的第 k 位,值为 v(0 或 1)

我们先检查序列 B 的每个数是否为 1,如果是,则累加 (2^k) / (N^2) 到答案中。这是 l = r 的部分。

接下来,只需要统计 and 和、or 和,xor 和为 1 且长度 >= 2 的区间个数即可。这是 l != r 的部分。

整个枚举过程如下

依次枚举右端点 r,设 last[v] (v=0,1)表示数字v上一次出现的位置。

(1) 对于 and 和

当 B[r] = 1 且 l 属于 [last[0] + 1, r - 1] 时,B[l..r] 的 and 和为 1,否则为 0

所以如果 B[r] = 1,则可以累加 2^k * ((r - 1) - (last[0] + 1) + 1) * 2 / N^2 到答案中。

(2) 对于 or 和

当 B[r] = 1,l 属于任何值时,B[l..r] 的 or 和都是 1

所以若 B[r] = 1,则可以累加 2^k * (r - 1) * 2 / N^2 到答案中。

当 B[r] = 0,l 属于 [1, last[1]],则 B[l..r] 的 or 和是 1。

所以若 B[r] = 0,则可以累加 2^k * last[1] * 2 / N^2 到答案中。

(3) 对于 xor 和

xor 的情况比较复杂。我们假设 l 从左向右扫描,遇到 0 时,B[l..r] 的 xor 和不变,遇到 1 时,B[l..r] 的 xor 和取反。

因此我们将序列 B 中的数字以 1 作为分界,把序列 B 分成几段,同一段中的位置作为 l 时,B[l..r] 的 xor 和相等。相邻两端的两个位置作为 l 时,B[l..r] 的 xor 和相反。

例如下图的 B 序列的例子,当 l 取阴影位置,B[l..r] 的 xor 和为 1,当 l 取白色位置,B[l..r] 的 xor 和为 0

在枚举 r 的时候,我们始终维护两个变量 c1, c2,其中

c1 表示 [0..r-1] 中,从 r - 1 往前数第 1, 3, 5 段的总长度
c2 表示 [0..r-1] 中,从 r - 1 往前数第 2, 4, 6 段的总长度

如果 B[r] = 0,c2 就是使得 B[l..r] 的 xor 和为 1 的 l 的数量,将 2^k * c2 * 2 / N^2 加入答案。

如果 B[r] = 1,c1 就是使得 B[l..r] 的 xor 和为 1 的 l 的数量,将 2^k * c1 * 2 / N^2 加入答案。

c 的更新方式如下

当 r 变为 r + 1 时,c1 加 1,如果 B[r] = 1,则交换 c1 和 c2

代码 (C++)

前面的分析中,l, r, 以及 last[0], last[1] 记录的值都是从 1 开始的,在下面的代码中是从 0 开始的,需要稍微做下转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; ++i)
cin >> A[i];

double ans_and = 0; // 记录 and 和的期望
double ans_or = 0; // 记录 or 和的期望
double ans_xor = 0; // 记录 xor 和的期望

for(int k = 0; k < 31; ++k)
{
// 枚举到第 k 位
for(int i = 0; i < N; ++i)
{
// l = r 的部分
if((A[i] >> k) & 1)
{
ans_and += (double)pow(2, k) / N / N;
ans_or += (double)pow(2, k) / N / N;
ans_xor += (double)pow(2, k) / N / N;
}
}
// c[0] 对应算法中的 c1
// c[1] 对应算法中的 c2
vector<int> c(2, 0);
vector<int> last{-1, -1};
for(int r = 0; r < N; ++r)
{
// l < r 的部分
if((A[r] >> k) & 1)
{
ans_and += (double)pow(2, k) * ((r - 1) - (last[0] + 1) + 1) * 2 / N / N;
ans_or += (double)pow(2, k) * r * 2 / N / N;
ans_xor += (double)pow(2, k) * c[0] * 2 / N / N;
last[1] = r;
c[0] += 1;
swap(c[0], c[1]);
}
else
{
ans_or += (double)pow(2, k) * (last[1] + 1) * 2 / N / N;
ans_xor += (double)pow(2, k) * c[1] * 2 / N / N;
last[0] = r;
c[0] += 1;
}
}
}
cout << std::fixed << std::setprecision(3);
cout << ans_xor << " " << ans_and << " " << ans_or << endl;
}

Share