題目鏈接：點擊查看

題目大意：我們需要構(gòu)造一個初始值start，范圍在[0,m]，要求使用這個初始值進行k次操作后得到的答案最大，每次操作分為三個類型：

AND x：讓當前答案與x進行按位與

OR x：讓當前答案與x進行按位或

XOR x：讓當前答案與x進行按位異或

現(xiàn)在我們需要構(gòu)造出這個start，使得經(jīng)過k次操作后得到的end最大，輸出end

題目分析：首先我們肯定不能直接枚舉m，然后維護最大值，因為m給到了1e9，單單只是枚舉一個m都會超時，就別再提每個m還需要n次操作，暴力的時間復雜度是n*m，都到了1e14，完全不用考慮了

我們需要知道關(guān)于位運算的一個主要特點：在二進制表示下不進位

換句話說，每一個數(shù)字的二進制都是相互獨立的，所以我們可以按位討論，這樣就能在logn的時間復雜度內(nèi)枚舉完m符合情況的狀態(tài)了，時間復雜度下降為n*logm，最多3e6

現(xiàn)在我們需要討論一下該怎么按位計算，如果這個題目沒有m的約束，那么我們按位從小到大枚舉和從大到小枚舉都是可以的，但是加了這個約束之后，我們就只能按位從大到小枚舉才能獲得最優(yōu)解了，因為如果我們從小到大枚舉的話，枚舉了其中一個比較小的位置，雖然對答案有貢獻，但卻占據(jù)了小于等于m的這個空間，若后續(xù)還有更大的位置可以做出貢獻，卻被m這個約束卡出去的話，那么此時答案必定不是最優(yōu)的

再就是討論一下某個位置該放0或1的情況，因為我們要貪心讓end盡可能的大，所以對于某一位置，我們計算一下res1和res0，res1和res0分別是在當前位置放1和放0情況下返回的答案，我們肯定會讓end加上兩者中較大的一個，如果兩者相等的話優(yōu)先放0，不過別忘了還有m這個約束，因為在放0放1對答案的貢獻相同的情況下，放1會占據(jù)m的空間，所以放0才是最優(yōu)解，總結(jié)下來在某一位放1還是放0可以分為兩種情況：start+res1<=m&&res1>res0滿足時放1，否則放0

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m;struct Node {char op[5];int val; }op[N];int cal(int bit,int x)//計算當前bit位，初始值為x的情況下得到的答案 {for(int i=1;i<=n;i++){int temp=op[i].val>>bit&1;if(op[i].op[0]=='A')x&=temp;else if(op[i].op[0]=='O')x|=temp;elsex^=temp;}return x<<bit; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s%d",op[i].op,&op[i].val);int start=0,end=0;//start:初始攻擊力 end:最終攻擊力 for(int i=30;i>=0;i--)//枚舉每一位，注意要從最高位開始枚舉才能達到最優(yōu)解 {int res1=cal(i,1);//當前第i位為1的情況下運算后得到的結(jié)果 int res0=cal(i,0);//當前第i位為0的情況下運算后得到的結(jié)果 if(start+res1<=m&&res1>res0)//滿足條件，第i位用res1填充{start+=res1;//實時更新start end+=res1;}else//否則用res0填充 end+=res0;}printf("%d\n",end);return 0; }

?

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。