题目描述
概括一下 给你n个操作,一个数字m表示范围, 每一个操作都是将目前在m范围内的一个数字进行按照操作给出的位运算(&, |, ^)进行运算,问在n个操作之后最大为几.
样例
3 10
AND 5
OR 6
XOR 7
1
算法1
$O(nlogm)$
借由《算法进阶指南》这本书上所说, 对于m范围内的一个数字x,参与位运算的各个位之间是无关的, 因此我们只要去从高到低位枚举每一位是0还是1就好.
这里主要想讲的是val,跟ans, 假设当前我们枚举第i位, 那么我们可以让第i位是1或者0, 对应代码:
res0 = calc(i, 0);
res1 = calc(i, 1);
这里我们会得到i这个位置分别取0, 1 后的值, 我们这里填写1的条件是:
1. 我们当前已经获得的值加上第i位的1(即1 << i)不会超过m
2. res1 > res0, 注意这里res1, res0只会返回0,1
对应代码:
if(val + (1 << i) <= m && res1 > res0)
接下来来说明val的意义, val存储的是我们当前的值.
举个例子:
假如我们已经枚举了前i - 1位 目前是 000000110011xxxxxxx, 也就是说我们现在正在枚举第i位 也就是第一个x的位置(从左往右数)
假如我们现在可以让第i位填写1, 那么我们当前的val就要加上1 << i (这里i是6,从右往左数, 因为我们是从高位往低位枚举)也就是加上64, 假设000000110011xxxxxxx的值是X, 如果X + 64 <= m那么就是说明这里可以
让这一位变成1, 因此val += (1 << i)
以上就是val的意义
这里我在看代码的时候, 一直在想为什么要同时有val 跟 res,下面进行解释:
我们会发现 如果要进入第一个判断, 我们不仅要判断这一位填写1是否会越界,同时也要判断res0 跟 res1的大小关系, 这里就要说明res0 res1的意义了
1.res0是如果将第i位变成0经过n次操作的结果
2.res1是如果将第i位变成1经过n次操作的结果
也就是说 这个1 我们可以由res0 获得 也可以由 res1获得,或者同时获得
但是我们要记住 这里res0,res1获得的结果是将第i位变成0, 1经过n次操作过后的结果, 跟原本第i位填写0,1是不同的。
假如说res0 = 1, res1 = 0, 为了我们最后能获得最大的答案, 我们这里要取res0 = 1,其实质是说:
这里第i位要填写0, 并且这个第i位经过n次操作后能变成1.
因此 在else的判断之中我们不用将val += (0 << i), 因为这没有意义, 但是我们要将res += (res0 << i), 因为这里res0 = 1.
时间复杂度
参考文献
<<算法进阶指南>>
C++ 代码
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <string>
using namespace std;
const int N = 1e5 + 1000, M = 30;
typedef pair<string, int> PSI;
PSI p[N];
int n, m;
int calc(int bit, int op){
for(int i = 1; i <= n; i ++){
string s = p[i].first;
int x = p[i].second >> bit & 1;
if(s == "AND") op &= x;
else if(s == "OR") op |= x;
else op ^= x;
}
return op;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
int x;
string s;
cin >> s >> x;
p[i] = {s, x};
}
int val = 0, res = 0;
for(int i = M - 1; i >= 0; i --){
int res0 = calc(i, 0);
int res1 = calc(i, 1);
if(val + (1 << i) <= m && res1 > res0){
res += (res1 << i);
val += (1 << i);
}
else res += (res0 << i);
// cout << res << " " << val << endl;
// cout << res0 << " " << res1 << endl;
// cout << endl;
}
cout << res;
return 0;
}