具體說來，drd 的防御戰線由 nn 扇防御門組成。每扇防御門包括一個運算 opop 和一個參數 tt，其中運算一定是 OR,XOR,AND 中的一種，參數則一定為非負整數。如果還未通過防御門時攻擊力為 x，則其通過這扇防御門后攻擊力將變為 x op t。最終 drd 受到的傷害為對方初始攻擊力 x 依次經過所有 nn 扇防御門后轉變得到的攻擊力。
由于 atm 水平有限，他的初始攻擊力只能為 0 到 m 之間的一個整數（即他的初始攻擊力只能在 0,1,…,m 中任選，但在通過防御門之后的攻擊力不受 m 的限制）。為了節省體力，他希望通過選擇合適的初始攻擊力使得他的攻擊能讓 drd 受到最大的傷害，請你幫他計算一下，他的一次攻擊最多能使 drd 受到多少傷害。
輸入格式
輸入文件的第 1 行包含 2 個整數，依次為 n,m，表示 drd 有 n 扇防御門，atm 的初始攻擊力為 0 到 m 之間的整數。
接下來 n 行，依次表示每一扇防御門。每行包括一個字符串 op 和一個非負整數 t，兩者由一個空格隔開，且 op 在前，t在后，op 表示該防御門所對應的操作，t 表示對應的參數。
輸出格式
輸出一行一個整數，表示 atm 的一次攻擊最多使 drd 受到多少傷害。
輸入輸出樣例
輸入 #1復制
3 10
AND 5
OR 6
XOR 7
輸出 #1復制
1
說明/提示
【樣例說明】
atm 可以選擇的初始攻擊力為 0,1,…,10。
假設初始攻擊力為 4，最終攻擊力經過了如下計算
4 AND 5=4
4 OR 6=6
6 XOR 7=1
類似的，我們可以計算出初始攻擊力為 1,3,5,7,9 時最終攻擊力為 0，初始攻擊力為 0,2,4,6,8,10 時最終攻擊力為 1，因此atm的一次攻擊最多使drd受到的傷害值為 1。
2 <=n<=10 ^ 5，2<=m<=10 ^ 9

知識點：
1、與1異或，可以使特定位翻轉 ，與0異或，保留其值 0101 0101 ^ 1111 0000 = 1010(翻轉) 0101(保留)
2、相同的值異或為0 a^a=0
3、1除了最低位，其他位都為0，所以按位與結果取決于n最后一位，如果n最后一位是1，則結果為1，反之結果為0
4、0的二進制是： 00000000…………
-1的二進制是：1111111111…………
只用0和-1進行位運算，就可以得到任何一位的任何情況進行位運算的結果

思路：
1、目的是從(0，m)中選出一個最好的初始攻擊數據K，然后通過n道門之后，數最大
2、如果把m中的每個數據都枚舉一遍，肯定不可以，所以反向思考得到最佳數據
3、過程肯定是將初始值K，攻擊n道門，將K轉化成二進制后，其實也就是二進制數上的每一位數都攻擊過n道門（位運算的性質，每個數之間相互不影響）
可以通過一個函數：

int t[N]; // t 存輸入的 n 個數 string op[N]; // op 存 n 個數對應的操作 bool jisuan(bool x, int j) // jisuan 用于計算 x 經過所有數的第 j 位操作后所得到的結果 {for (int i = 0; i < n; i ++ ) // 當前數字，遍歷n道門if (op[i] == "OR") x |= t[i] >> j & 1; else if (op[i] == "XOR") x ^= t[i] >> j & 1; else x &= t[i] >> j & 1; return x; }

4、接下來就是把所有二進制位數遍歷一遍，因為本題中 m 最大是 10 ^ 9，log2(10 ^ 9) < 30，最多30位
5、當前數字一定是0 或 1，判斷，誰合適當前位就填誰

bool x = jisuan(0, i), y = jisuan(1, i); // 先分別處理出該位填 0 的結果和該位填 1 的結果 if (m >> i && x < y) // 判斷是否超過最大值，如果 m 右移 i 位仍不為 0，該位填 1 比該位填 0 更優，就填1 //如果填1不必0更優,那么為了讓剩下能填的數更大，在該位填 0 {sum |= y << i;m -= 1 << i; // 填完后讓 m 減去該位填 1 的結果，這樣在后面填數的時候只用考慮是否大于 m 就可以了 } else sum |= x << i; // 該位只能填 0

完整代碼：

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <iomanip>using namespace std; typedef long long ull; ull n,m,k,c,sum=0,x; int t[100005]; // t 存輸入的 n 個數 string op[100005]; // op 存 n 個數對應的操作 bool jisuan(bool x, int j) // jisuan 用于計算 x 經過所有數的第 j 位操作后所得到的結果 {for (int i = 0; i < n; i ++ ) // 當前數字，遍歷n道門if (op[i] == "OR") x |= t[i] >> j & 1;else if (op[i] == "XOR") x ^= t[i] >> j & 1;else x &= t[i] >> j & 1;return x; } int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=0; i<n; i++){cin>>op[i]>>t[i];}for(int i=29; i>=0; i--){bool x = jisuan(0, i), y = jisuan(1, i); if (m >> i && x<y) {sum |= y << i; m -= 1 << i; }else sum |= x << i; }cout<<sum<<endl;return 0; }

下面是一個更技巧的寫法，真神奇
利用：
0的二進制是： 00000000…………
-1的二進制是：1111111111…………
只用0和-1進行位運算，就可以得到任何一位的任何情況進行位運算的結果

我們本來是循環一次就判斷一次n道門后，0和1誰更合適
令a=0,b=-1, 把函數省掉，不用每次都判斷當前這位數經過n道門之后的結果，在輸入的時候直接保存了每一位數的結果

#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <iomanip> #include <queue> #include <list> #include <stack>using namespace std; typedef long long ull; ull n,t,m,k,c,sum=0,x; const int M=1<<29; string s;int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a=0,b=-1;cin>>n>>m;for(int i=1;i<=n;i++){cin>>s>>x;if(s=="AND") a&=x,b&=x;else if(s=="OR") a|=x,b|=x;else a^=x,b^=x;}k=0;for(int i=29;i>=0;i--){bool x=a>>i&1,y=b>>i&1;if(m>>i && x<y) //填1{sum |= 1<<i;m -= 1 << i;}else sum |= x<<i; //填0}cout<<sum<<endl;return 0; }

總結

以上是生活随笔為你收集整理的起床困难综合征(位运算)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。