题目描述

萌新第一次写题解，如果有什么不正确或者写得不好的地方请各位大佬指出

21世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。

作为一名青春阳光好少年，atm一直坚持与起床困难综合症作斗争。

通过研究相关文献，他找到了该病的发病原因： 在深邃的太平洋海底中，出现了一条名为drd的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。

正是由于drd的活动，起床困难综合症愈演愈烈， 以惊人的速度在世界上传播。

为了彻底消灭这种病，atm决定前往海底，消灭这条恶龙。

历经千辛万苦，atm终于来到了drd所在的地方，准备与其展开艰苦卓绝的战斗。

drd有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。

具体说来，drd的防御战线由n扇防御门组成。

每扇防御门包括一个运算op和一个参数t，其中运算一定是OR,XOR,AND中的一种，参数则一定为非负整数。

如果还未通过防御门时攻击力为x，则其通过这扇防御门后攻击力将变为x op t。

最终drd受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。

由于atm水平有限，他的初始攻击力只能为0到m之间的一个整数（即他的初始攻击力只能在 0, 1, … , m中任选，但在通过防御门之后的攻击力不受m的限制）。

为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让drd受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使drd受到多少伤害。

样例

• 输入

3 10
AND 5
OR 6
XOR 7

• 输出

1

算法1

暴力 $O(n*m)$

• 由于可以选择初始攻击力，直接将初始攻击力从0枚举到m，每一次攻击力进行位运算，最后取最大值即可

时间复杂度

• 暴力需要外层枚举m次，内层每次需要进行位运算n次，总共时间复杂度为$O(m*n)$
• 该题时间为1s，最大数据量为10^9*10^5，暴力算法肯定超时

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
pair<string, int> a[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    int maxn = 0;
    for(int i = 0; i <= m; i++){
        int c = i;
        for(int j = 0; j < n; j++){
            if(a[j].first == "OR") c |= a[j].second;
            else if(a[j].first == "XOR") c ^= a[j].second;
            else if(a[j].first == "AND") c &= a[j].second;
        }
        maxn = max(c, maxn);
    }
    cout << maxn;
    return 0;
}

算法2

位运算优化 $O(logm*m)$

• 二进制位运算最大的特点在于每次计算之后没有进位与借位，每一位计算的时候都是独立计算
• 根据独立计算可得，我们可以确定攻击的二进制的每一位，自然而然就确定答案的每一位了
• 如何确定攻击的每一位填1还是填0
  • 填1必须满足：
    • 该位为1了以后总和不能大于最大的攻击力
    • 填1了之后运算过后答案的二进制位上还是1
  • 其余情况填1也会变成0，否则就大于了m，还不如填0有效

时间复杂度

参考文献

• 算法竞赛进阶指南

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
pair<string, int> a[N];
int n, m;

int calc(int bit, int now){// 代表现在运算的是二进制的第几位， now有两种情况，需要运算过后返回
    for(int i = 0; i < n; i++){
        int x = a[i].second >> bit & 1;// 首先取出第i次运算中的第几位进行二进制运算
        if(a[i].first == "OR") now |= x;
        else if(a[i].first == "XOR") now ^= x;
        else now &= x;
    }
    return now;// 现在返回的就是运算过后的二进制位
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;
    int ans = 0, v = 0;
    for(int i = 29; i >= 0; i--){// m最多有29个二进制位，直接从高位到低位枚举每一位
        int r1 = calc(i, 0);// 查看填0之后是否变化
        int r2 = calc(i, 1);// 查看填1之后是否变化， 如果没有变化，加上该位后又小于m，就可以填1
        // 这里仅有四种情况 分别为0 0， 0 1， 1 0， 1 1
        // 仅有0 1 是满足可以填一的一个条件的，其他情况运算过后这一位都相反了，填0，后面运算还可能填1
        if(v + (1<<i) <= m && r2 > r1) v += (1 << i), ans += r2 << i;// 满足填1的条件，直接填1
        else ans += r1 << i;// 不能填1，直接填0
    }
    cout << ans << endl;// 最后的答案
    return 0;
}