當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

线性基（一

發(fā)布時間：2025/3/20 编程问答 12 豆豆

生活随笔收集整理的這篇文章主要介紹了线性基（一小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

1、線性基：

　　若干數(shù)的線性基是一組數(shù)a1,a2,...an

　　通過線性基中元素xor

2、線性基的構造法：

　　對每一個數(shù)p

3、查詢：

　　用線性基求這組數(shù)xor

4、判斷：

　　用線性基求一個數(shù)能否被xor

個人談一談對線性基的理解:

　　很多情況下，只有有關異或運算和求最值，就可以用到線性基。線性基有很多很好的性質(zhì)，比如說如果有很多個數(shù)，我們可以構出這些數(shù)的線性基，那么這個線性基可以通過互相xor

　　構造的方法有點像貪心，從大到小保證高位更大。也比較好理解。就是這幾行代碼：

1 2 3 4 5 6 7 8 9 10 11 12 13

for(int?i=1;i<=n;i++) {???? ????　　　　for(int?j=62;j>=0;j--) { ????????　　　　?if(!(a[i]>>j))?continue;//對線性基的這一位沒有貢獻??????????? ????????　　　　　　if(!p[j]) { p[j]=a[i];?break; }//選入線性基中??????????????????? ????????　　　　　　 a[i]^=p[j]; ????????　　　　 } ????　　　}

　　可以把n

　　查詢的話，也是一個貪心思想，如果可以使得ans

　　?1?for(int?i=62;i>=0;i--)?if((ans^p[i])>ans) ans=ans^p[i];//從線性基中得到最大值?

　　這就是線性基的基本用法和個人的一些理解。

下面看一些練習（例題）：

1、BZOJ2460

Description

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

正解：貪心+線性基

解題報告：

　　顯然這道題可以用線性基來維護一個我們選取的非空子集中不存在異或出0

2、BZOJ2115?

Description

正解：線性基

解題報告：

　　這道題要求從1到n的最大xor和路徑，存在重邊，允許經(jīng)過重復點、重復邊。那么?在圖上作圖嘗試之后就會發(fā)現(xiàn)，路徑一定是由許多的環(huán)和一條從1到n的路徑組成。容易發(fā)現(xiàn)，來回走是沒有任何意義的，因為來回走意味著抵消。考慮這道題求得是路徑xor和最大，所以必然我們要想辦法處理環(huán)的情況。我的做法是任意地先找出一條從1到n的路徑，把這條路徑上的xor和作為ans初值（先不管為什么可行），然后我們的任務就變成了求若干個環(huán)與這個ans初值所能組合成的xor最大值。顯然，我們需要預處理出圖上所有的環(huán)，并處理出所有環(huán)的環(huán)上xor值，這當然是dfs尋找，到n的路徑的時候順便求一下就可以了。

　　當我們得到了若干個環(huán)的xor值之后，因為是要求xor最大值，我們就可以構出這所有xor值的線性基。構出之后，再用ans在線性基上取max就可以了。

　　現(xiàn)在我們來討論上述做法的可行性。

　?　第一種情況：我們對最終答案產(chǎn)生貢獻的某個環(huán)離1到n的主路徑很遠，這樣的話，因為至少可以保證1可以到達這個環(huán)，那么我們可以走到這個環(huán)之后繞環(huán)一周之后原路返回，這樣從1走到環(huán)的路上這一段被重復經(jīng)過所以無效，但是環(huán)上的xor值被我們得到了，所以我們并不關心這個環(huán)和主路徑的關系，我們只關心環(huán)的權值。

　　第二種情況：我們?nèi)我膺x取的到n的路徑是否能保證最優(yōu)性。假設存在一條更優(yōu)的路徑從1到n，那么這條路徑與我們原來的路徑構成了一個環(huán)，也就會被納入線性基中，也會被計算貢獻，假如這個環(huán)會被經(jīng)過，那么最后的情況相當于是走了兩遍原來選取的路徑，抵消之后走了一次這個最優(yōu)路徑，所以我們無論選取的是哪條路徑作為ans初值，都可以通過與更優(yōu)情況構成環(huán)，然后得到一樣的結果。這一證明可以拓展到路徑上的任意點的路徑選取。

　　這樣我們就可以完美解決了。我第一次WA了一發(fā)，因為我沒有考慮到ans初值不為0，在線性基上取到xor的max的時候，不能單純以ans這一位是否為0來決定是否異或上基的這一位，必須要看異或之后取一個max做一個判斷才行。

3、codeforces724G

　　直接鏈接到我的那篇博客過去辣

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