[NOI 2014] 起床困难综合症

知识点

二进制位运算、贪心、上界约束

解题思路

分别让全0与低31位全1经过所有门，得到每一位输入0/1时的输出位。再从高到低：若输入0已输出1，就直接取0；只有输入0输出0、输入1输出1且当前已选值加该位不超过m时才取1；其他情况仍取0。累计对应输出值。

正确性说明

每个输出位仅由同位置输入位决定。高位输出优先级严格高于全部低位之和，应在可行范围内优先使其为1。两种输入输出相同时取0保留最大剩余预算；只有1优于0且可负担时取1。逐位归纳，前缀输出最优且在同输出下使用最小输入，最终全局最优。

易错点

经过门后的输出可以超过m，限制只针对初始值；不能只试0和m；选择无收益的1会浪费预算。

复杂度

时间O(n+31)，空间O(1)在线合成映射。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long m;cin>>n>>m;long long z=0,o=(1LL<<31)-1;for(int i=0;i<n;i++){string op;long long t;cin>>op>>t;if(op=="AND")z&=t,o&=t;else if(op=="OR")z|=t,o|=t;else z^=t,o^=t;}long long used=0,ans=0;for(int b=30;b>=0;b--){long long bit=1LL<<b;if(z&bit)ans|=bit;else if((o&bit)&&used+bit<=m)used+=bit,ans|=bit;}cout<<ans<<'\n';}