0x01|998. 起床困难综合症 位运算奇解数学题

上一次我们看了下位运算的3道题，其实漏了一题，因为当时没看明白就没写，现在补上，算是一个比较典型的位运算算法题，这道题最大的特点是将一个看起来很复杂的数学问题用位操作的方式轻松化解，一起来看题吧。

题目比较长，是非常长，可以看原文链接，这里转译一下，也就是：

对于一个数字x(

)，经过n次位运算（固定了AND OR XOR三种运算），问最终结果最大能是多少？

比如输入如下：

3 10
AND 5
OR 6
XOR 7

其中3是运算次数，10是m，也就是

，接下来3行是位运算操作。

这个问题中m不超过

。

暴力朴素解法自然是遍历每一个数字，然后选一个最大值，这种做法在数字非常大的情况下会很慢，那么，如何高效解决呢？

先来研究下m和位的性质。

「特性」1：m的二进制最多29位

所以m的二进制表示最多29位。

「特性」2：位运算不发散

对于AND OR XOR三个位操作，都不会影响其他位的数字。

这样我们可以从高位到低位来确定数ans的每一位。

m右移29位，得到的是30这个位的值，处理m，如果这个30位为1，那么m减去1<<29（消去这一位）；

m右移28位，得到的是29这个位的值，如上处理；

依次处理27...1位，确定最终ans的值。

那么如何处理m呢？

如果右移的值等于0，说明这里只可能为0，比如m的二级制是1011，我们将m右移29位，显然结果是0，但是这个0最终可能参与位运算，ans需要计算这个位的最终值，如下，calc函数指的是对0在第29位进行n次位运算，如果算出的结果位1，那么ans需要将其合并。

ans |= calc(0, 29) << i;

如果右移的值是1，那么这一位有可能是0，也有可能是1。还是假设m的值是1011，m右移3位，结果是1。此时我们可以选择0和1，我们通过calc函数来计算是0的结果大还是1的结果大，哪个大就选哪个。

只有0和1的结果相等的情况，我们需要优先选择0，这是为什么呢？

因为我们第一位选择1的话，那么1011的第二位就不能选择1了，因为这样就会超过m的值，所有优先选择0，让后面的数字可以有更多选择。

对于每一位，只有0和1两种情况，我们将0和1分别进行n次位计算，对应的值为

和

，如果

比

大，说明这里填0更合适，如果

<

，则填1，注意如果填1后m需要减去这个位的值，不然后面的递推会失效。

具体实现如下：

#include <stdio.h>

const int N = 100005;

int n, m;
int ans;
int t[N];
short op[N];
char str[4];

bool calc(bool x, int j)
{
    // n次计算
    for (int i = 0; i < n; i++)
        if (op[i] == 1)
            x |= t[i] >> j & 1;
        else if (op[i] == 2)
            x ^= t[i] >> j & 1;
        else
            x &= t[i] >> j & 1;
    return x;
}

// 初始x(x<=m)，经过n次计算，算出最大值
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("\n%s %d", str, t + i);
        if (*str == 'O')
            op[i] = 1;
        else if (*str == 'X')
            op[i] = 2;
        else
            op[i] = 3;
    }

    for (int i = 29; ~i; i--) 
        if (m >> i)
        {
            bool x = calc(0, i), y = calc(1, i); 
            if (x >= y)
                ans |= x << i;
            else
                ans |= y << i, m -= 1 << i;
        }
        else
            ans |= calc(0, i) << i;

    printf("%d\n", ans);
    return 0;
}

算法总结：

这道题型对于第一次接触的童鞋是比较难的题目，因为比较难想到通过填位的方式来解决一个数学问题，在填位的过程中，需要注意是从高位（30位）到低位进行递推，而且不管哪一位是0还是1，都可能要合并到ans中。特别的，如果填了1，后面那一位就可能不能填1，所以在0和1进行位运算的结果相等的情况下需要优先填0。

这个题目理解起来同样需要一些时间，一次看不明白就多用几个例子在纸上画画，小编实在是比较弱，刚开始硬着头皮也看不懂，不过回几次头想想又想通了，所以没有解不了的题，就看你愿不愿意花时间啦。

唠唠嗑

最近到年底了，工作比较忙，要发游戏版本不然年不好过啦，除了维护公众号（主要还是cwolf9童鞋大力支持帮忙写lc的题解），业余主要时间都在写极简笔记——一款现代化的Markdown笔记（可以在公众号的菜单上查看链接），最近只要把Latex用C++重新实现这个功能做完，后面就会多花一些时间给大家写题解哈。本号的新老粉丝，真的是希望多包容，最近号里广告也比较多，哎真的惭愧（就知道赚钱），打工人真的是忙不开（借口。。）。

然后后面主要还是写算法进阶指南的题解，本来还给AcWing的闫总做个代理，签了代理合同，也是拖了几个星期一直没抽出时间来宣传一下，大家刷题或者从零开始学习算法竞赛可以多上AcWing，如果要买课的也可以找我，拼团价给大家。

原创不易，点个赞ha！