很明显是有关 二进制的的题
- and 即 & （按位与）
二进制下同一位同为1，位运算后为1
例如 (1001 & 0111 = 0001)
(1001)
(&0111)
(=0001)
(1&1=1 1&0=1 0&1=1 0&0=0) - or 即 | （按位或）
二进制下只要一位为1，位运算后为1
例如 (1001|0111 = 1111)
(1001)
(|0111)
(=0001)
$1|1=1 1|0=1 0|1=0 0|0=0 $ - xor 即 ^ （按位异或）
二进制下相同为0，不同为1，也有人称之为不进位加法
例如 (1001 ^ 0111 = 1110)
(1001)
(^0111)
(=1110)
(1^1=1 0^1=1 0^1=1 0^0=0)
介绍完基础操作后，暴力的思路其实很好想
枚举(1-m)所有数，每个数都(n)次进行操作，然后记录最大值
（是不是很简单啊，然后你发现你就tle了）
如果涉及到二进制操作，其实可以考虑枚举二进制的每一位（毕竟最多64位）
题目要求取最大值，根据这个思路（枚举二进制的每一位），我们是不是希望最终答案的二进制的每一位都为1，就能满足取得的最大值了
那么答案的二进制位怎么来的了？
由(1-m) 之间的某个数来的，我们只需要构造一个数满足(1-m) ，且经过n次位运算后，能尽可能的使答案的二进制位每位为1
然而我们并不用直接构造这么一个数，只需要每次确认1或0经过n次位运算之后，此位是否为1，如果0经过n次位运算之后能变为1，那么这位数为0，否则为1，并且让(m)减去(（1<
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e5+10;
int n,m;
int t[maxn],op[maxn];
int ans=0;
bool book(bool check,int j){//计算这一个位，经过n次位运算之后的，为1还是0
for(int i=0;i<n;++i){ bool k="(t[i]">>j)&1;
if(op[i]==1) check&=k;
if(op[i]==2) check|=k;
if(op[i]==3) check^=k;
}
return check;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;++i){ string s;cin>>s>>t[i];
if(s[0]=='A') op[i]=1;
if(s[0]=='O') op[i]=2;
if(s[0]=='X') op[i]=3;
}
for(int i=31;i>=0;--i){
if(m>>i){//最大值这位有1，说明我们所求的答案这位可以为1或0
bool x=book(0,i),y=book(1,i);//x代表原数此位为0时，经过n次位运算为几，y同理
if(x>=y) ans|=x<<i; 此时x>=y满足三种情况
//1.x=0,y=0 无论原数此位填0还是1，都最终为0，所以还是填0更加合适
//2.x=1,y=0 原数此位填0之后，能使最终答案更大
//3.x=1,y=1 原数此位无论填0还是1，都最终为1，都能使最终答案更大
//为什么填0更合适，如果高位填0填的越多那么，低位能选择1的可能性就更大
else ans|=y<<i,m-=1<<i; 减去填1之后的数，保证原数小于m } else ans|="book(0,i)<<i;//此位为0，原数只能填0，最终答案只能为由0进行位运算的结果" }cout<<ans<<endl;return 0; < code></i,m-=1<<i;></i;></n;++i){></n;++i){></iostream></cstring></cstdio>
如果牵扯到二进制，直接暴力很有可能tle，可以考虑试着枚举位数，一般都能大大降低时间复杂度
ZFY AK IOI
Original: https://www.cnblogs.com/guiyou/p/15185500.html
Author: 归游
Title: [NOI2014] 起床困难综合症
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584594/
转载文章受原作者版权保护。转载请注明原作者出处！