「NOI 2014」起床困难综合征

发表于 | | 阅读次数:
字数统计: 647 字

Description

题目链接：BZOJ 3668

在深邃的太平洋海底中，出现了一条名为 drd 的巨龙。历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 的防御战线由 $n$ 扇防御门组成。每扇防御门包括一个运算 $op$ 和一个参数 $t$，其中运算一定是 $\text{OR},\text{XOR},\text{AND}$ 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 $x$，则其通过这扇防御门后攻击力将变为 $x\ op\ t$（$x$ 和 $t$ 经过 $op$ 运算后的结果）。最终 drd 受到的伤害为对方初始攻击力 $x$ 依次经过所有 $n$ 扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为 $0$ 到 $m$ 之间的一个整数。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

数据范围：$2\le n\le 10^5$，$2\le m\le 10^9$，$0\le t\le 10^9$

Solution

对于这种二进制的题目，由于每一位时完全独立的，所以第一感觉就是按位贪心！我们贪心 $m$ 的每一位的值，选择能够使答案的这一位最大的值就行了。

细节的处理：我们使用 $\text{DFS}$ 就行实现，这样可以方便处理贴紧上界的情况。如果对于 $m$ 这一位的所有取值，答案的这一位都相同，那么最小化 $m$。

时间复杂度：$O(n\log m)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <cstdio>
#include <algorithm>

const int N=1e5+5;
int n,m,len,a[N],bin[31],ans,opt[2];
char s[N][5];

void init() {
    for(;m;m>>=1) bin[++len]=m&1;
    while(len<30) bin[++len]=0;
}
int solve(int d,int x) {
    for(int i=1;i<=n;++i) {
        char opt=s[i][1];
        int num=(a[i]>>(d-1))&1;
        if(opt=='A') x&=num;
        if(opt=='O') x|=num;
        if(opt=='X') x^=num;
    }
    return x;
}
void work(int len,bool full) {
    if(!len) return;
    int up=full?bin[len]:1;
    opt[0]=opt[1]=-1;
    for(int i=0;i<=up;++i) opt[i]=solve(len,i);
    ans+=std::max(opt[0],opt[1])*(1<<(len-1));
    if(!full) work(len-1,0);
    else work(len-1,bin[len]?(opt[1]>opt[0]):1);
}
int main() {
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=n;++i) scanf("%s%d",s[i]+1,&a[i]);
    work(len,1);
    printf("%d\n",ans);
    return 0;
}
0%