題意：
?相傳，在遠(yuǎn)古時(shí)期，位于西方大陸的 Magic Land 上，人們已經(jīng)掌握了用魔
法礦石煉制法杖的技術(shù)。那時(shí)人們就認(rèn)識(shí)到，一個(gè)法杖的法力取決于使用的礦石。
一般地，礦石越多則法力越強(qiáng)，但物極必反：有時(shí)，人們?yōu)榱双@取更強(qiáng)的法力而
使用了很多礦石，卻在煉制過(guò)程中發(fā)現(xiàn)魔法礦石全部消失了，從而無(wú)法煉制
出法杖，這個(gè)現(xiàn)象被稱(chēng)為“魔法抵消” 。特別地，如果在煉制過(guò)程中使用超過(guò)
一塊同一種礦石，那么一定會(huì)發(fā)生“魔法抵消”。
后來(lái)，隨著人們認(rèn)知水平的提高，這個(gè)現(xiàn)象得到了很好的解釋。經(jīng)過(guò)了大量
的實(shí)驗(yàn)后，著名法師 Dmitri 發(fā)現(xiàn)：如果給現(xiàn)在發(fā)現(xiàn)的每一種礦石進(jìn)行合理的編
號(hào)（編號(hào)為正整數(shù)，稱(chēng)為該礦石的元素序號(hào)），那么，一個(gè)礦石組合會(huì)產(chǎn)生“魔
法抵消”當(dāng)且僅當(dāng)存在一個(gè)非空子集，那些礦石的元素序號(hào)按位異或起來(lái)
為零。 （如果你不清楚什么是異或，請(qǐng)參見(jiàn)下一頁(yè)的名詞解釋。 ）例如，使用兩
個(gè)同樣的礦石必將發(fā)生“魔法抵消”，因?yàn)檫@兩種礦石的元素序號(hào)相同，異或起
來(lái)為零。
并且人們有了測(cè)定魔力的有效途徑，已經(jīng)知道了：合成出來(lái)的法杖的魔力
等于每一種礦石的法力之和。人們已經(jīng)測(cè)定了現(xiàn)今發(fā)現(xiàn)的所有礦石的法力值，
并且通過(guò)實(shí)驗(yàn)推算出每一種礦石的元素序號(hào)。
現(xiàn)在，給定你以上的礦石信息，請(qǐng)你來(lái)計(jì)算一下當(dāng)時(shí)可以煉制出的法杖最多
有多大的魔力。

3
1 10
2 20
3 30
輸出

50

題意懂了就好了,用到了線(xiàn)性基的一個(gè)性質(zhì),線(xiàn)性基中的每?jī)蓚€(gè)數(shù)xor都不會(huì)等于0，
然后在貪心的對(duì)獲取的能量進(jìn)行求和，最終就是可以得到的最大值。
?

#include<bits/stdc++.h> #include <iostream> #include <cmath> #include <cstdio> #include <stdlib.h> #include <ctime> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e6 + 5; ll a[maxn]; struct Point{ll num,val;}point[maxn]; bool operator <(Point a,Point b){return a.val>b.val;} int Build(ll p) {for(int x=63;x>=0;--x){if(p&(ll(1ll<<x))){if(!a[x]){a[x]=p;break;}p^=a[x];}}if(p) return 1;return 0; }int main() {int n;cin>>n;memset(a,0,sizeof(a));for(int i=0;i<n;++i) cin>>point[i].num>>point[i].val;sort(point,point+n);ll ans=0;for(int i=0;i<n;++i)if(Build(point[i].num))ans+=point[i].val;cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【bzoj 2460 [BeiJing2011]元素】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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