1.5 起床困难综合症
原题链接
给定 n,m以及n个数和该数所对应的运算,其中运算有 与、或、异或 三种,问在所有不大于m的非负整数中,对给定的n个数都按该数所对应的运算运算一遍后,能得到得最大的值是多少。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
pair<string,int>a[100005];
int n,m;
int calc(int bit,int now)//假设参数为now值,填入,n次操作数的第bit位进行运算,返回预计now值
{
for(int i=0;i<n;i++)
{
int x=a[i].second>>bit&1;//取第bit位
if(a[i].first=="AND")now&=x;
else if(a[i].first=="OR")now|=x;
else now^=x;
}
return now;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
string str;
int x;
cin>>str;
scanf("%d",&x);
a[i]=make_pair(str,x);
}
int val=0,ans=0;
for(int bit=29;bit>=0;bit--)
{
int res0=calc(bit,0);
int res1=calc(bit,1);
if(res0<res1&&val+(1<<bit)<=m)//预计结果为0<1,且已经填好的更高位构成的数值加上1<<bit后不超过m,填1
{
val+=1<<bit;
ans+=res1<<bit;
}
else
ans+=res0<<bit;//其余情况,都填0
}
printf("%d",ans);
return 0;
}