[BZOJ3668][Noi2014]起床困难综合症（贪心）

2019-11-11 02:14:26

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

我们需要还原初始的x，将x按二进制位分开来考虑每一位不是0就是1，所以将0和1分别做一下下面那一坨操作（操作的数也是对应的这一位），最终得到两个数如果0做了这一坨操作之后变成了1，那很显然这一位填0更优否则，如果1做了这一坨操作之后还是1，那么先把这一位暂且记为1 再否则1和0都会变成0，那么毫无疑问填0 然后将每一位合起来得到了一个x 但是这个x是有可能大于m的，所以从高位向低位枚举，贪心地去掉一些1, 如果这一位m是1，那么x填01都可以，不变；不过，如果x填了0的话，x之后的位就可以随便填了如果这一位m是0，那么x只能填0，如果原先填的是1需要修改这样保证先满足较高位的，一定是最优的方案

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 100005#define sz 30char s[10];int n,m,t,ans0,ans1,ans;int opt[N],dig[N][sz],mdig[sz];bool flag;int main(){ scanf("%d%d",&n,&m); for (int i=sz-1;i>=0;--i) mdig[i]=m>>i&1; for (int i=1;i<=n;++i) { scanf("%s",s); if (s[0]=='A') opt[i]=1; else if (s[0]=='O') opt[i]=2; else opt[i]=3; scanf("%d",&t); for (int j=sz-1;j>=0;--j) dig[i][j]=t>>j&1; } flag=0; for (int j=sz-1;j>=0;--j) { ans0=0;ans1=1; for (int i=1;i<=n;++i) { switch(opt[i]) { case 1: { ans0&=dig[i][j]; ans1&=dig[i][j]; break; } case 2: { ans0|=dig[i][j]; ans1|=dig[i][j]; break; } case 3: { ans0^=dig[i][j]; ans1^=dig[i][j]; break; } } } if (ans0) { ans|=1<<j; if (mdig[j]) flag=1; } else if(ans1){if(mdig[j]||flag)ans|=1<<j;} else {if(mdig[j])flag=1;} } PRintf("%d/n",ans);}