首页 > 代码库 > BZOJ 3668 NOI2014 起床困难综合症 贪心
BZOJ 3668 NOI2014 起床困难综合症 贪心
题干一堆废话。。
题目大意:给定n次操作(与,或,异或),在0~m中选择一个数,使这个数经过n次操作后得到的值最大
丰年好大水 AC如土分如铁。。
这尼玛根本就是水题好不 枚举选择数字的每一位 分三种情况讨论:
1.该位取0时经过n次操作结果取1 这自然是最理想的情况 必须选择0
2.情况1不满足 该为取1时经过n次操作结果取1 且取1后值不超过m 这样我们也选择1
3.上两种情况不满足 则该位取0一定比取1小 更不容易超过m
于是这题就水过去了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100100 using namespace std; struct abcd{ int p,x; int cross(int y) { if(p==0) return x&y; if(p==1) return x|y; return x^y; } }a[M]; int n,m; char s[100]; int cross(int x) { int i; for(i=1;i<=n;i++) x=a[i].cross(x); return x; } int main() { int i,ans=0,now; cin>>n>>m; for(i=1;i<=n;i++) { scanf("%s",s); if(s[0]=='A') a[i].p=0; else if(s[0]=='O') a[i].p=1; else a[i].p=2; scanf("%d",&a[i].x); } for(now=1;now<=m;now<<=1); for(now>>=1;now;now>>=1) { if(cross(0)&now) continue; if(ans+now<=m&&cross(now)&now) ans+=now; } printf("%d\n",cross(ans)); }
BZOJ 3668 NOI2014 起床困难综合症 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。