原題

解題思路一（錯(cuò)誤）：

順著做（每個(gè)數(shù)用數(shù)組存）的思路是人腦思路，但是電腦會(huì)TLE。我們可以反著來(lái)。

大概的思路就是先假設(shè)一個(gè)最終結(jié)果的最大值。

然后問(wèn)電腦：這數(shù)運(yùn)算回去（按照輸入的門的順序，逆著順序運(yùn)算回去）在我的m范圍之內(nèi)嗎？

在，我就得寸進(jìn)尺，我用11000000試（看是否 <= m）；否則用01000000作為ans嘗試。原則總是最高位優(yōu)先，逐漸考慮低位。

錯(cuò)誤原因：想當(dāng)然。因?yàn)槿鏰&b|c = d并不能得到 d|c&b = a，不能直接逆過(guò)去

?

解題思路二（超時(shí)）：

#include <bits/stdc++.h> using namespace std; const int N=1e5+5; struct data{int op,k; }qry[N]; char s[10]; int n,m; int suan(int a){for(int i=1;i<=n;i++){if(qry[i].op==1) a&=qry[i].k;if(qry[i].op==2) a|=qry[i].k;if(qry[i].op==3) a^=qry[i].k;}return a; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s%d",s,&qry[i].k);if(s[0]=='A')qry[i].op=1;if(s[0]=='O')qry[i].op=2;if(s[0]=='X')qry[i].op=3;}int maxn=0;for(int i=0;i<=m;i++){ maxn = max(maxn,suan(i));}printf("%d\n",maxn);return 0; }

思路就是遍歷從0到m，每次取結(jié)果的最大值。但部分超時(shí)。

分析時(shí)間復(fù)雜度，n <= 1e5,m <= 1e9，相乘是1e14，超時(shí)是肯定的。所以我們要優(yōu)化想法。

?

可以這樣思考，比方說(shuō)進(jìn)門前的數(shù)字是1001?000，是10011000出門后比10010000出門后結(jié)果要大，那么10010000粗體0的低3位000無(wú)需考慮了！這是一個(gè)很關(guān)鍵的想法，因?yàn)槲贿\(yùn)算的每一位都是獨(dú)立的。10011000的出門結(jié)果比10010000大，則表明從右往左第4位應(yīng)該選用1而不是0，這樣出門的結(jié)果對(duì)應(yīng)的這一位也就是1.

那么，縱然第3位，10010000的輸出是111，也不如10011000的出門結(jié)果大了。這是一種貪心的想法，因?yàn)橹灰呶槐容^大，無(wú)論低位如何，肯定是高位大的那個(gè)數(shù)結(jié)果大。這樣就引入了下面的想法：

?

解題思路三（正確）：

要盡量保持經(jīng)過(guò)每個(gè)門運(yùn)算之后，得到的結(jié)果最大。我們可以對(duì)通過(guò)門前的數(shù)進(jìn)行逐位調(diào)整：在<m的前提下，如果某位是1使通過(guò)門后結(jié)果更大，那么就讓這一位是1；否則不變（默認(rèn)是0）.

這樣對(duì)最多31位進(jìn)行考慮，運(yùn)算的數(shù)量級(jí)和門的數(shù)量差一個(gè)常數(shù)，即1e5，不會(huì)超時(shí)。

//AC代碼 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; struct data{int op,k; }qry[N]; char s[10]; int n,m; int cal(int a){for(int i=1;i<=n;i++){if(qry[i].op==1) a&=qry[i].k;if(qry[i].op==2) a|=qry[i].k;if(qry[i].op==3) a^=qry[i].k;}return a; } int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){scanf("%s%d",s,&qry[i].k);if(s[0]=='A') qry[i].op = 1;if(s[0]=='O') qry[i].op = 2;if(s[0]=='X') qry[i].op = 3;}int ans = 0;for(int i = 30;i >= 0;i--){ if(ans + (1 << i) > m) continue;if(cal(ans) < cal(ans + (1 << i))) ans += 1<<i;//如果入門前的數(shù)第i位是1時(shí)結(jié)果更大，則入門時(shí)的該位設(shè)置為1；否則不變 }printf("%d\n",cal(ans));return 0; }

?

?

問(wèn)：能否將① for(int i = 30;i >= 0;i--){
?? ??? ?if(ans + (1 << i) > m)?? ?continue;
?? ??? ?if(cal(ans) < cal(ans + (1 << i)))?? ?ans += 1<<i;
??? }

?

改成

②? for(int i = 0;i <= 30;i++){
?? ??? ?if(ans + (1 << i) > m)?? ?continue;
?? ??? ?if(cal(ans) < cal(ans + (1 << i)))?? ?ans += 1<<i;
??? }

也就是說(shuō)從最低位開始找使此位的最大輸出的入門值？

?

答：不能！比方說(shuō)可能最低位是1時(shí)得到該位的最大輸出了，同時(shí)最高位是1也是最高位的最大輸出。而這樣組合得到的數(shù)超過(guò)了m的范圍，就不符合題意，continue掉了。那么得到的答案就是一個(gè)較小的答案，這樣得到的最終輸出結(jié)果，是小于100000作為入門值的最終輸出。

因?yàn)?#xff1a;最終輸出的結(jié)果，高位大的則整個(gè)數(shù)大。所以我們很自然地要優(yōu)先滿足高位輸出最大的要求。

比方說(shuō)這樣一個(gè)例子：

輸入流為：

1 4

AND 5

Span	Doors	Op
000	1	&101
001	?	?
010
011
100

在①寫法得到的結(jié)果是4；而在②寫法得到的結(jié)果是1.

原因已經(jīng)解釋完畢。

總結(jié)

以上是生活随笔為你收集整理的【位运算】起床困难综合症（包含错误思路点拨）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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