算法基础算法

按位单独处理

字数统计: 2.4k字   |   阅读时长: 10分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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^2，l != r 的情况的概率为 2 / N^2

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

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

我们先检查序列 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