3668: [Noi2014]起床困难综合症

https://www.lydsy.com/JudgeOnline/problem.php?id=3668

分析：

　　每一位分开考虑。

　　算出每一位为1，计算完后是否产生贡献，每一位为0是否会产生贡献。

　　然后从高位考虑：

如果这一位为0，并且可以产生(1<<i)的贡献，那么就让它为0。
如果这一位位1，可以产生贡献，并且在小于等于m，就让它为1。
不可以产生贡献的话，直接为0.

　　如果在某一步，可以比m小了，就是m这位为1，而答案是0了，那么后面的就可以随便选了，否则，这位选的数必须小于等于m的这位。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int N = 100005;
22 
23 char s[N][5];
24 int a[N], f[N], n, m;
25 
26 int Calc(int x) {
27     for (int i=1; i<=n; ++i) 
28         if (s[i][0] == 'A') x &= a[i];
29         else if (s[i][0] == 'O') x |= a[i];
30         else if (s[i][0] == 'X') x ^= a[i];
31     return x;
32 }
33 
34 int main() {    
35     n = read(), m = read();
36     for (int i=1; i<=n; ++i) {
37         scanf("%s%d", s[i], &a[i]);
38     }
39     int t = Calc(0);
40     for (int i=30; i>=0; --i) f[i] = Calc(1 << i) & (1 << i);
41     int ans = 0;
42     bool flag = false;
43     for (int i=30; i>=0; --i) {
44         if ((t >> i) & 1) { 
45             ans += (1 << i);
46             if ((m >> i) & 1) flag = true;
47         }
48         else if (f[i]) {
49             if (flag) ans += f[i];
50             else if ((m >> i) & 1) ans += f[i]; 
51         }
52         else if ((m >> i) & 1) flag = true;
53     }
54     cout << ans;
55     return 0;
56 }