描述

---

分析

• 我把文庫里的粘了過來.

• 只知道點(diǎn)1到點(diǎn)N的一條路徑和圖中若干個(gè)環(huán)，就能通過異或，表示成所有路徑。那么，需要多少環(huán)才能保證必定能表示成所有路徑呢？其實(shí)，并不需要很多， 因?yàn)橐恍┉h(huán)可以通過其他的環(huán)異或得到，只需保證環(huán)是相互 獨(dú)立的，兩兩之間存在著不同的邊(乘數(shù))。構(gòu)建一棵生成樹，統(tǒng)計(jì)非樹邊與生成樹形成的環(huán)即可，最多只有M-N+1個(gè)環(huán)。可用dfs實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(M)。

• 結(jié)合上述性質(zhì)，可以設(shè)計(jì)貪心說法：將x表示成二進(jìn)制數(shù)，從高位到低位枚舉，當(dāng)前位能取1則取1。

• 從高位到低位枚舉當(dāng)前位；
• 在a數(shù)組中選取一個(gè)當(dāng)前位為1的數(shù)a[i]，假如不存在a[i]，則轉(zhuǎn)1）；
• 假如x的當(dāng)前位為0,則x=x xor a[i]；
• 將a數(shù)組中所有當(dāng)前位為1的數(shù)a[j]與a[i]異或，a[j]=a[j] xor a[i]， 轉(zhuǎn)1）。

• 最終x保證必定是最大的，時(shí)間復(fù)雜度為O (NB)。（N為a數(shù)組的大小，B為二進(jìn)制位數(shù)）

• 看了上面的解析就去打了, 結(jié)果好幾次都 WA. 然后跟HZWER的代碼對比, 發(fā)現(xiàn)他在步驟2中選過的元素在后面再進(jìn)行步驟2時(shí)不去考慮了.
• 資料里怎么沒說…

• 改了這個(gè)地方就對了

• 1直接左移62位是會(huì)報(bào)錯(cuò)的. 但一次一次來就沒事…

• 這個(gè)題到底和高斯消元和線性基的關(guān)系在哪?
  
  • 貪心的那四步其實(shí)就是標(biāo)準(zhǔn)的用高斯消元解異或方程組的步驟. 我后來更新了代碼片.
  • 解得的那些解就是線性基. 用它們直接異或就可以表示出所有原來a數(shù)組可以異或出的結(jié)果.

---

代碼

https://code.csdn.net/snippets/619907

---

• 首頁: http://blog.csdn.net/qq_21110267

總結(jié)

以上是生活随笔為你收集整理的BZOJ-2115-Xor-WC2011的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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