題目描述

相傳，在遠(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)象被稱為“魔法抵消” 。特別地，如果在煉制過(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ù)，稱為該礦石的元素序號(hào)），那么，一個(gè)礦石組合會(huì)產(chǎn)生“魔法抵消”當(dāng)且僅當(dāng)存在一個(gè)非空子集，那些礦石的元素序號(hào)按位異或起來(lái)為零。（如果你不清楚什么是異或，請(qǐng)參見下一頁(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í)可以煉制出的法杖最多有多大的魔力。

輸入輸出格式

輸入格式：

第一行包含一個(gè)正整數(shù)N，表示礦石的種類數(shù)。
接下來(lái) NN行，每行兩個(gè)正整數(shù) Numberi?和 Magici，表示這種礦石的元素序號(hào)和魔力值。

輸出格式：

僅包一行，一個(gè)整數(shù)代表最大的魔力值。

輸入輸出樣例

輸入樣例#1：

3?
1 10?
2 20?
3 30

輸出樣例#1：

50

思路：與?元素（HYSBZ-2460）同一個(gè)題

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 1000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;struct LinearBasis {LL d[60+5];//線性基LinearBasis() {memset(d,0,sizeof(d));}bool add(LL x){for(int i=60; i>=0; i--)if(x&(1LL<<i)) {if(d[i])//插入失敗，異或x^=d[i];else {//插入成功，保存后退出d[i]=x;break;}}return x>0;//x>0插入成功} }lb; struct Node{LL a,b;bool operator <(const Node &rhs)const{return b>rhs.b;} }node[N]; int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&node[i].a,&node[i].b);sort(node+1,node+1+n);LL res=0;for(int i=1;i<=n;i++)if(lb.add(node[i].a))res+=node[i].b;printf("%lld\n",res);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的元素（洛谷-P4570）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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