Time Limit: 20 Sec? Memory Limit: 128 MB
Submit: 1555? Solved: 809
[Submit][Status][Discuss]

Description

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

Input

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

Output

僅包一行，一個整數(shù)：最大的魔力值

Sample Input

3
1 10
2 20
3 30

Sample Output

50

HINT

由于有“魔法抵消”這一事實，每一種礦石最多使用一塊。
如果使用全部三種礦石，由于三者的元素序號異或起來：1 xor 2 xor 3 = 0 ，
則會發(fā)生魔法抵消，得不到法杖。
可以發(fā)現(xiàn)，最佳方案是選擇后兩種礦石，法力為 20+30=50。

對于全部的數(shù)據(jù)：N ≤ 1000，Numberi ≤ 10^18
，Magici ≤ 10^4
。

Source

Day2

?

題解：
?????? ①保證集合異或不為零，考慮線基。

?????? ②因為線基里面最多就n個數(shù)(n表示位數(shù)),那么肯定要先選擇權值的大就是最優(yōu)解了。

#include<stdio.h> #define ll long long #define S(x,y) (x^=y^=x^=y) #define go(i,a,b) for(int i=a;i<=b;i++) #define ro(i,a,b) for(int i=a;i>=b;i--) const int N=1003; int n,val[N],ans,Val;ll num[N]; struct Linear_Base {ll a[70];void Insert(ll x){if(x)ro(i,60,0)if((1ll<<(i))&x)!a[i]?a[i]=x,ans+=Val,i=0:x^=a[i];} }Base; int main() {scanf("%d",&n);go(i,1,n)scanf("%lld%d",num+i,val+i);go(i,1,n)go(j,i+1,n)if(val[i]<val[j])S(num[i],num[j]),S(val[i],val[j]);go(i,1,n)Val=val[i],Base.Insert(num[i]);printf("%d\n",ans);return 0; }//Paul_Guderian

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

用那最洶涌的卑微，救贖我們幻滅的渴望。————汪峰《滄浪之歌》

轉載于:https://www.cnblogs.com/Damitu/p/7692522.html

總結

以上是生活随笔為你收集整理的【BZOJ 2460 元素】的全部內容，希望文章能夠幫你解決所遇到的問題。

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