DDOSvoid's Blog

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

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2114

Solution

首先每一位分别考虑，虽然有 $m$ 的限制，但是我们依然可以从高位开始贪心

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
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <map>
#define maxn 100010
using namespace std;

int n, m;

map<char, int> ma;

struct Query {
    int opt, v;
} Q[maxn];

int now, ans;
int main(){
    ma['A'] = 1; ma['O'] = 2; ma['X'] = 3;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        char c[5]; scanf("%s%d", c, &Q[i].v);
        Q[i].opt = ma[c[0]];
    }
    for (int k = 30; ~k; --k) {
        int s = 0;
        for (int i = 1; i <= n; ++i) {
            int opt = Q[i].opt, v = Q[i].v >> k & 1;
            switch (opt) {
            case 1 : s &= v; break;
            case 2 : s |= v; break;
            case 3 : s ^= v; break;
            }
        }
        if (s) { ans += 1 << k; continue; }
        s = 1;
        for (int i = 1; i <= n; ++i) {
            int opt = Q[i].opt, v = Q[i].v >> k & 1;
            switch (opt) {
            case 1 : s &= v; break;
            case 2 : s |= v; break;
            case 3 : s ^= v; break;
            }
        }
        if (!s || now + (1 << k) > m) continue;
        now += 1 << k; ans += 1 << k;
    }
    cout << ans << endl; 
    return 0;
}