Luogu 2114 [NOI2014]起床困难综合症

还挺简单的。

发现这几个二进制运算并不会进位，所以我们从高到低按位贪心，一位一位计算贡献。

发现$2^{30}$刚好大于$1e9$，所以最多只要算29位。

首先算出一个全都是$0$的二进制数和一个全都是$1$的二进制数通过所有的门之后每一位的情况，可以压成两个变量做。

最后贪心的时候先看看这一位取$0$能不能取到$1$，再看看这一位取$1$能不能取到$1$，如果可以就算上消耗$m$的代价取这个$1$。

因为高位取$1$一定比低位取$1$优，所以算出来的一定是最好答案。

一个每一位全都是$1$的二进制数可以通过机器补码的特性写成$-1$。

时间复杂度$O(nlogMaxInt)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

int n, m, v1, v0;

int main() {

//    freopen("testdata.in", "r", stdin);

    scanf("%d%d", &n, &m);

    v0 = , v1 = -;

    for(int i = ; i <= n; i++) {

        char op[]; scanf("%s", op);

        int now; scanf("%d", &now);

        if(op[] == 'A') v1 &= now, v0 &= now;

        if(op[] == 'O') v1 |= now, v0 |= now;

        if(op[] == 'X') v1 ^= now, v0 ^= now;

    }

    int ans = ;

    for(int i = ; i >= ; i--) {

        if((v0 >> i) & ) ans += ( << i);

        else if(((v1 >> i) & ) && ( << i) <= m) m -= ( << i), ans += ( << i);

    }

    printf("%d\n", ans);

    return ;

}

巴特西

Luogu 2114 [NOI2014]起床困难综合症

最新文章

热门文章