首次寫這解析

題目介紹：
【背景介紹】
古堡，暗鴉，斜陽，和深淵……
等了三年，我獨自一人，終于來到了這里……
“終焉的試煉嗎？就在這里嗎？”我自言自語道。
“終焉的試煉啊！就在這里啊！”我再一次自言自語道。
“這背后可能有那個東西嗎？”我自言自語道。
“這背后一定有那個東西呢！”我又一次自言自語道。
我沉默著，踏上黑漆漆的索橋，小心翼翼地，拿出鋒利的注入我靈魂的雙劍……
“那么，我們開始吧……”我最后一次自言自語道。
【題目描述】
My soul of my sowrd!
終焉的試煉即將到來，作為一名有修養的劍士，雖然沒有習得n刀流但是二刀流還是沒問題的。然而我也是個劍的收藏者，家里屯著n把劍，每一把劍都有一個靈魂值a[i]，由于一些劍之間可能有共鳴，所以我需要兩把契合度最高的劍。據劍圣所說，兩把編號為i,j劍的契合度為a[i] and a[j]。如何深得劍的靈魂呢？
注：AND 為按位與運算，先將數轉成二進制，不滿位數的補全0，然后成為兩個長度相同的二進制數，處理的時候，兩個相應的二進制位都為1，該位的結果值才為1，否則為0。

n ≤ 1,000,000，0 ≤ a[i] < 2^31
———————————–華麗分割線————————————

題目簡述：給一堆數，求其中最大的任意兩個數的and值。 及求max（a[i] and a[j]）。

——————————–現在告訴你—————————————

思路：
因為這個n<= 106 ,所以要是 n2 的話你可以看看你的電腦是否有高配的計算速度。

考慮到這a[i]的位數頂死只有31位，又和位運算有關，我們可以分位考慮。

正解
兩個數and后，要使其最大，就是讓越高為為1越好，所以我們可以從高往低搜。遵循以下兩個原則即可更行答案。
設現在選的答案為ans,當前正在選第i位，當前的數為a[j]。
1:a[j]必須與之前所選的每一位都要符合，即：a[j]&ans=ans;
2:a[j]的第i位必須為1，即：a[j]&(2^(i-1))=2^(i-1)；
符合這兩個條件就可以的a[j]如果超過兩個就可以更新答案了。

時間復雜度：O(31*n); 空間復雜度：O(n);

代碼

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(int i=a; i<=b; i++) #define fod(i,a,b) for(int i=a; i>=b; i--)using namespace std;const int maxn=1000005; int n; long long a[maxn],ans;int main() {freopen("sword.in","r",stdin);freopen("sword.out","w",stdout);scanf("%d",&n);fo(i,1,n) scanf("%d",&a[i]);fod(i,31,1){int t=0;fo(j,1,n)if (((ans&a[j])==ans)&&((a[j]&(1<<(i-1)))!=0)) ++t;if (t>=2) ans+=(1<<(i-1));}printf("%lld",ans); }

—————————華麗分割線——————————————-

那么第一次寫就這樣結束了，中途中我還問了不少的人這個符號那個符號怎么打。不過打完后覺得挺爽的。

總結

以上是生活随笔為你收集整理的【NOIP2015模拟10.28B组】终章-剑之魂的全部內容，希望文章能夠幫你解決所遇到的問題。

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