集訓隊作業(yè)xor最大XOR和路徑解題報告

1、NOI Wer C2011最大 XOR 和路徑解題江蘇省常州高級中學April 14, 201111題目大意給出一個 N 個點，M 條邊的帶權(quán)無向圖 G，權(quán)值是一個 64負整數(shù)。求出一條從 1 號頂點到 N 號頂點的路徑（不一定是簡單路徑），使得這條路徑上的邊權(quán)的異或值最大。2算法一：動態(tài)規(guī)劃用 f unum 表示從 1 號點到達 u 這個節(jié)點，且當前 xor 和是 num 是否可行。利用 bfs 進行擴展，每次從 u 點向外擴展到 v，更新所有的 f vnum cost。最后就是最大的滿足f N k = true 的 k。時間復雜度： O(maxV alue (M + N )空間復雜度： O

2、(maxV alue N )3算法二：異或方程首先發(fā)現(xiàn)，由于是異或操作，那么每條邊對于最后異或和的貢獻只在于經(jīng)過它次數(shù)的奇偶性，因為 x x = 0。分析從 1 到 N 的路徑的性質(zhì)，會發(fā)現(xiàn)從 1 到 N 的路徑，一定是由下面三種路徑(1). 1 到 N 的簡單路徑 (2). a 到 b 的簡單路徑 (3). 一些環(huán)的：會發(fā)現(xiàn)，任意畫一條從 1 到 N 的路徑，且把路徑上經(jīng)過奇數(shù)次的邊保留一條，經(jīng)過偶數(shù)次的邊去掉。這條路徑必然可以滿足由一條 (1) 和若干個 (3) 組成。發(fā)現(xiàn)了這條性質(zhì)之后，問題就變成了這樣：找一條從 1 到 N 的簡單路徑和若干不與路徑相交且互相不相交的環(huán)。這個問題看起來的

3、確比原題要簡單了許多。然后一個圖的數(shù)量是指數(shù)級別的，仍然不能帶來好的效率。考慮先做出找個圖的一個生成樹。首先用去了 N 1 條邊。接下來剩下了 M N +1條邊，每條邊和樹上的一條路徑了一個環(huán)。得到了類似的 M N + 1 個環(huán)。然而環(huán)有指數(shù)級別，并沒有得到所有的環(huán)。稱上面得到的環(huán)為基礎(chǔ)環(huán)。發(fā)現(xiàn)任何一個環(huán)都可以由一些基礎(chǔ)環(huán)相加得到。這里所謂的相加是指相同邊保留(mod 2) 條邊。這樣，所有環(huán)都可以通過基礎(chǔ)環(huán)“線性表示”。于是，現(xiàn)在只要考慮基礎(chǔ)環(huán)就可以了。不再是“找一條從 1 到 N 的簡單路徑和若干不與路徑相交且互相不相交的環(huán)”，現(xiàn)在而是“從 1 到 N 的簡單路徑和一些基礎(chǔ)環(huán)中找出一些，使

4、得 xor 和最大”。于是，先隨機一個生成樹，然后把 1 到 N 的簡單路徑和基礎(chǔ)環(huán)求出來。然后從最開始考慮。就是x valuei。枚舉是否可以為 1，如果這一位不能是 1，那么就取 0。什么ii情況下不可能？當且僅當 valuei 全是 0。否則一定可能。2已經(jīng)求到了第 i 位，現(xiàn)在假設(shè)第 i-1 位可以是 1。x假設(shè) valueji = digitj。顯j,ii然這是一個異或方程組，判斷。只要判斷這個方程組是否有解即可。每次加入一個方程，再進行時間復雜度： O(log maxV alue3M )空間復雜度： O(log maxV alueM )4算法二的優(yōu)化：異或方程組每次加入一個方程，就

5、全部進行一次消元的復雜度太高了，且出現(xiàn)了太多冗余。其實需要每次加入一個方程之后，就和之前的方程消一次元，這樣就大大減少了冗余。只時間復雜度： O(log maxV alue3M )空間復雜度： O(log maxV alueM )5代碼#include #include #include #include #include #include using namespatd; n,m;vectorpair g51111;long long dist51111;bool matrix70111111,buf111111;main() ios:sync_with_stdio(false); cin

6、n m;for(i=0;i u v c;-u;-v;gu.push_back(make_pair(v,c); gv.push_back(make_pair(u,c);memset(dist,-1,sizeof(dist);3dist0 = 0; queue q; q.push(0); while(q.size()0)u = q.front();q.pop();for(i=0;igu.size();i+)v = gui.;if(distv=-1)distv = distu gui.second; q.push(v);vector val; val.push_back(distn-1); for(

7、i=0;in;i+)for(j=0;jgi.size();j+) u = i;v = gij.;long long t = distudistvgij.second; if(t)val.push_back(t);sort(val.begin(),val.end(); val.erase(unique(val.begin(),val.end(),val.end();for(i=0;ival.size();i+)for(j=0;j63;j+)if(vali&(1LLj)matrix62-ji = 1;long long ans = 0; m = val.size();for(i=0;i63;i+)for(j=0;jm;j+)bufj = matrixij;bufm = 1;for(k=0;ki;k+)for(j=0;jm;j+) if(matrixkj)if(bufj)4for(h=0;h=m;h+)bufh = matrixkh;break;bool flag = 0;for(j=0;jm;j+) if(bufj)flag = 1;if(!flag&bufm) flag = 0;elseflag = 1;if(flag)ans += 1LL (62-i);matrixim = fl