M_sea

洛谷2114 [NOI2014]起床困难综合症
Luogu算法贪心。按照顺序从左至右贪心,如果第$x$位经过一系列位运算操作之后能得到$1$,那么第$x$位所放置...
扫描右侧二维码阅读全文
05
2018/04

洛谷2114 [NOI2014]起床困难综合症

Luogu

算法

贪心。

按照顺序从左至右贪心,如果第$x$位经过一系列位运算操作之后能得到$1$,那么第$x$位所放置的数一定是这个经过位运算得到$1$的数;如果第$x$位放置$0$或$1$都可以得到$1$,那么我们选择放置$0$,因为这样会使初始攻击力更小,使之后的贪心操作有更大的选择范围。

但是这样得出的结果可能会超过$m$。那么设$m$有$len$位。我们的答案就只需要找后面$len-1$位就可以保证不会超出范围了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
int n,m;
struct Door { int op,t; } door[100010];
char input[10];
inline int Calc(int k) { //计算初始值为k最后的攻击力是多少 
    for (re int i=1;i<=n;i++) {
        if (door[i].op==1) k&=door[i].t;
        else if (door[i].op==2) k|=door[i].t;
        else k^=door[i].t;
    }
    return k;
}
int main() {
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=n;i++) {
        scanf("%s%d",input,&door[i].t);
        if (input[0]=='A') door[i].op=1;
        else if (input[0]=='O') door[i].op=2;
        else door[i].op=3;
    }
    int tmp=0,len=0;
    do { tmp=(tmp<<1)|1; len++; } while (tmp<m);
    int zero=Calc(0),one=Calc(tmp),ans=0;
    for (re int i=len-1;i>=0;i--) //枚举每一位
        if (!(zero&(1<<i))&&(one&(1<<i))&&(ans|(1<<i))<=m)
            ans|=(1<<i);
    printf("%d\n",Calc(ans));
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 50 PM

发表评论