題目描述

相傳，在遠(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)參見(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í)可以煉制出的法杖最多有多大的魔力。?

輸入

第一行包含一個(gè)正整數(shù)N，表示礦石的種類數(shù)。?

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

輸出

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

樣例輸入

3
1 10
2 20
3 30

樣例輸出

50

---

題解

貪心+高斯消元求線性基

題目要求不存在非空子集的異或和為0，即線性無(wú)關(guān)組。所以我們肯定使用最大線性無(wú)關(guān)組，即線性基。

擬陣最優(yōu)化問(wèn)題考慮貪心，求線性基時(shí)，對(duì)于相同最高位的，選擇權(quán)值最大的作為線性基加到答案中。

#include <cstdio> #include <algorithm> #define N 1010 using namespace std; typedef long long ll; struct data {ll num;int val; }a[N]; int n; int gauss() {ll i;int j , ans = 0 , tot = 0 , p;for(i = 1ll << 62 ; i ; i >>= 1){for(p = 0 , j = ++tot ; j <= n ; j ++ )if(a[j].num & i && a[j].val > a[p].val)p = j;if(!p){tot -- ;continue;}swap(a[tot] , a[p]) , ans += a[tot].val;for(j = 1 ; j <= n ; j ++ )if(j != tot && a[j].num & i)a[j].num ^= a[tot].num;}return ans; } int main() {int i;scanf("%d" , &n);for(i = 1 ; i <= n ; i ++ ) scanf("%lld%d" , &a[i].num , &a[i].val);printf("%d\n" , gauss());return 0; }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7054863.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2460】[BeiJing2011]元素 贪心+高斯消元求线性基的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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