題： bzoj4184 bzoj3168 bzoj4031 bzoj3270 bzoj3601* bzoj3143

bzoj4184

題意：

給出一堆數的插入和刪除順序，詢問每一次操作后，選出某些數異或起來的最大值a1$a_1$^a2$a_2$^a3$a_3$^…^an$a_n$ (數的個數≤500000$/le 500000$)

分析：

有插入和刪除操作不好處理，于是我們嘗試經過一波預處理將其轉化為只有插入~ 顯然一個數的出現時間是一段一段的，離散化后記錄每個數當前的個數便可以知道在哪段區間。 由于我們要求出每一個時間點的答案，便用線段樹結構記錄某個數覆蓋的區間，在最后的dfs時不斷插入到線性基中，到線段樹的葉節點時求出答案。

bzoj3168

題意：

給出一個矩陣A和B，滿足兩矩陣大小相同。求一個字典序最小的1...n$1...n$的排列a$a$滿足將隨意一個—Ai$A_i$換成Bai$B_{a_i}$后矩陣A仍然滿秩。（n≤300$n/le 300$）

分析：

容易想到二分圖，但問題在于如何在O(n3$n^3$)內完成構圖。 考慮一個行向量Bi$B_i$，我們在A中找到最小的行向量集合滿足Bi能夠被這些行向量線性表出，那么顯然Bi僅僅能替換這些行向量

我們能夠設矩陣C$C$滿足C?A=B$C?A=B$，那么C=B?A?1$C=B?A^{?1}$ Ci,j≠0$C_{i,j}≠0$表示Bi$B_i$的線性表出須要Aj$A_j$，因此CT$C^T$就是這個二分圖的鄰接矩陣

如今我們有了一個二分圖，怎樣求字典序最小的完備匹配呢？

我們能夠枚舉每一條邊，然后推斷剩余的圖是否存在一個完備匹配。可是這樣做是O(n4)$O(n^4)$的

我們能夠跑兩遍匈牙利算法，第一遍求出隨意一個完備匹配。第二遍對于每一個點貪心選最小的出邊推斷是否能找到不影響前面點的交錯環

總時間復雜度O(n3)$O(n^3)$

bzoj4031

題意：

給出一個”.”“#”矩陣，”.”與”.”之間能連邊，使得任意兩點之間有且只有一條路徑相連。求方案總數。(n,m≤9)$(n,m/le 9)$

分析：

顯然是矩陣樹定理。給矩陣每一個點標號，若兩相鄰點x，y（編號），x能**向**y連邊就將行列式a[x][x]++,a[x][y]??$a[x][x]++,a[x][y]--$ 最后求一波行列式的值即可。（將行列式左下角的值全用高斯消元消成0，對角線乘積就是答案） 注意：取模高斯消元的奇怪姿勢

bzoj3270

題意：

給出一個無向圖，兩個人分別從s,t$s,t$出發，在第i個點有p[i]$p[i]$的幾率停留，不停留則等幾率地跑到相鄰的點上，詢問兩人同時到同一點的幾率是多少。輸出所以點的幾率。（點數≤20$/le 20$）

分析：

從最終狀態入手，也就是說當兩個人同時到達(x1,x2)$(x_1,x_2)$，顯然這個狀態是從其他狀態轉換過來的，也就是相鄰的點。 其狀態可能為(x1,x2)、(x1,PRe2)、(pre1,x2)、(pre1,pre2)$(x_1,x_2)、(x_1,pre_2)、(pre_1,x_2)、(pre_1,pre_2)$ 這4種狀態轉換到(x1,x2)$(x_1,x_2)$的概率分別為 p[x1]?p[x2]、p[x1]?(1?p[x2]、(1?p[x1])?p[x2]、(1?p[x1])?(1?p[x2])$p[x_1]*p[x_2]、p[x_1]*(1-p[x_2]、(1-p[x_1])*p[x_2]、(1-p[x_1])*(1-p[x_2])$ 于是每一個點都有一條表示它的答案的表達式。也就是說我們有n個點n條表達式（即方程），再用高斯消元亂搞就好了。

bzoj3143（水）

題意：

一個無向連通圖，頂點從1編號到N，邊從1編號到M。 小Z在該圖上進行隨機游走，初始時小Z在1號頂點，每一步小Z以相等的概率隨機選 擇當前頂點的某條邊，沿著這條邊走到下一個頂點，獲得等于這條邊的編號的分數。當小Z 到達N號頂點時游走結束，總分為所有獲得的分數之和。 現在，請你對這M條邊進行編號，使得小Z獲得的總分的期望值最小。

分析：

給m條邊編號，顯然期望經過次數越多的邊編號越小。 設g[i]$g[i]$為第i條邊經過的期望次數。 經過第i條邊必然是從第i條邊的一端(X)到另一端(Y)。 也就是說我們要知道經過每個點的期望次數。

設f[i]$f[i]$為第i個點經過的期望次數。 顯然：f[i]+=f[i?>next]deg[i?>next]$f[i]+=/frac{f[i->next]}{deg[i->next]}$(deg[i]$deg[i]$為第i個點的出度) 于是我們有n個未知數f[]$f[]$與n條不等式f[i]=......$f[i]=......$ 那么高斯消元亂搞就好啦~~~

嗯，求出f[i]$f[i]$以后。現在要求的就是g[]$g[]$了。 顯然：g[i]=f[x]deg[x]+f[y]deg[y]$g[i]=/frac{f[x]}{deg[x]}+/frac{f[y]}{deg[y]}$(x,y為第i條邊的兩端)