前情提要

一些基礎運算操作用法看看上一篇；

起床困難綜合征（貪心，位運算）

題目原文

[P2114 NOI2014] 起床困難綜合癥 - 洛谷

思路分析

題目很長，意思是讓我們在[0,m]之間選一個數x，在經過給定的n次運算后，使最后的結果an盡可能的大；

最簡單的思路可是枚舉1~m的所有數，最后找到最大的那個數就是所求的答案；但是m的范圍去到了10⁹所以會超時不能過所有的點；

因為給出的操作都是位運算所以不難想到這題需要利用位運算去模擬；在這里就用到了位、位運算在二進制數表示下不用進位的特點；所以我們選取的數x時參與運算的各個位置上的數之間都是獨立的互不影響的；所以我們就可以去利用貪心的思想；從最高位遍歷到在低位；依次考慮每一位上去填幾；

用二進制數去模擬只用一次判斷每一位上的情況即可；枚舉所有m的情況，m取到10⁹相當于2²⁹左右，所以在二進制下最多29位；大大縮短了時間；

比如在x的第i位時：

• 已經填好的更高位構成的數加上1<<i后不超過m并且用每個操作時的數的第i位和x的第i位運算過后不改變第i為上原本的值（操作前后相等）；此時我們就可以在an的第i位上填上1；
• 如果不滿足上面的情況，就說明填1可能會超過m的范圍或者不如0更優；所以就填0；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fi first
#define se second
const int N=1e7;
pair <string,int> a[N];
int n,m;
int f(int w,int x){ // 位數，當前位的數for(int i=1;i<=n;i++){ // n組操作int c=a[i].se>>w&1; // 把每個操作對應的數的對應位上的數截出來if(a[i].fi[0]=='A')x&=c;if(a[i].fi[0]=='O')x|=c;if(a[i].fi[0]=='X')x^=c;}return x;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se; // 先將操作存起來int val=0,an=0; // 當前的值，和答案值for(int i=29;i>=0;i--){ // 枚舉所有m的情況，m取到10的9次方，在二進制下最多29位int x0=f(i,0); // 這一位是0時操作后的值int x1=f(i,1); // 這一位是1時操作后的值if(val+(1<<i)<=m&&x0<x1) // 不超m，并且1比0大val+=1<<i,an+=x1<<i; // 就選1作為這一位elsean+=x0<<i; // 反之選0}cout<<an;
} 

當然在這里也可以進行簡化；

初始兩個變量一個全為0（也就是0）一個全為1（也就是 -1 因為二進制數的第一位表示符號，所以要想全是1那就取-1就好了 ）去進行題目給出的操作；

其實就是把上面

int x0=f(i,0); // 這一位是0時操作后的值
int x1=f(i,1); // 這一位是1時操作后的值

這一部分給提前處理了；最后貪心的時候還需要每一位分開看；

最后得到兩個結果；貪心時就能用0換1就換，能用1換1也換，不能換不換就好了；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e7;
signed main(){int n,m;cin>>n>>m;int x=0,y=-1; // 初始兩個全1和全0的狀態while(n--){string a;cin>>a;int c;cin>>c;if(a[0]=='A')x&=c,y&=c;if(a[0]=='O')x|=c,y|=c;if(a[0]=='X')x^=c,y^=c;}int an=0;for(int i=29;i>=0;i--){ // 枚舉每一位上的情況，貪心的思路與上面類似if(x>>i&1)			// 這里是不能填0的情況就變成1an+=1<<i; else if(y>>i&1&&(1<<i)<=m)an+=1<<i,m-=1<<i; // 直接在m上面減就不用在設立val變量}cout<<an<<endl;
} 

---