[BZOJ3668][Noi2014]起床困難綜合癥（貪心）

2019-11-11 02:14:26

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

我們需要還原初始的x，將x按二進制位分開來考慮每一位不是0就是1，所以將0和1分別做一下下面那一坨操作（操作的數也是對應的這一位），最終得到兩個數如果0做了這一坨操作之后變成了1，那很顯然這一位填0更優(yōu) 否則，如果1做了這一坨操作之后還是1，那么先把這一位暫且記為1 再否則1和0都會變成0，那么毫無疑問填0 然后將每一位合起來得到了一個x 但是這個x是有可能大于m的，所以從高位向低位枚舉，貪心地去掉一些1, 如果這一位m是1，那么x填01都可以，不變；不過，如果x填了0的話，x之后的位就可以隨便填了如果這一位m是0，那么x只能填0，如果原先填的是1需要修改這樣保證先滿足較高位的，一定是最優(yōu)的方案

代碼

#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;} } 總結

位運算的題目一定要考慮按位分開，這一點很重要