程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ Monthly, June 2014 解題報告

ZOJ Monthly, June 2014 解題報告

編輯：C++入門知識

A.Another Recurrence Sequence
B.Gears
題目大意：有n個齒輪，一開始各自為一組，之後進行m次操作，包括以下4種類型： 1.合並兩組齒輪，合並的兩個應該反向旋轉 2.把某個齒輪從所在組刪除，自為一組，但不影響同組其它齒輪的狀態與關系 3.詢問兩個齒輪是同向、反向或無關系(即不在同一組) 4.詢問某個齒輪所在組的齒輪總數
分析：典型的並查集操作，但是注意兩點： 1.由於操作3要詢問兩個齒輪的相對狀態，因此對並查集中每個元素應當保存它的狀態信息。狀態是相對的，只需要保存每個元素相對於父元素的狀態，在查詢所屬集合時順便更新狀態信息。如用depth[i]表示齒輪i相對於父齒輪的深度，那麼兩個齒輪屬於同一組且深度奇偶性相同時同向旋轉。更新depth數組也行簡單，i對j的深度 = i對k的深度 + k對j的深度。 2.操作2涉及刪除某個元素。另外開一個數組id，用id[i]表示元素i實際所在的位置，當刪除元素i時，令id[i] = new id，同時fa[id[i]] = id[i]，即id[i]自為一組。這樣一來，之後涉及到元素i的操作都用id[i]代替，而原來的i元素依然存在，只不過它只起到占位的作用，以維持原集合的相對關系。相當於id[i]表示元素i的指針。

C.Consecutive Blocks
題目大意：給定一個整數序列，要求刪除最多k個數後，新序列中連續相等的子序列長度最大，輸出該最大長度。
分析：除了F題搞笑外這個就是最簡單的題了。記錄每個數出現的位置(由於數字可能很大，先把數字映射到1..k)，然後計算以每個位置結束時的最大長度即可。
D.An Easy Game
題目大意：給定兩個0-1序列s1, s2，操作t次，每次改變m個位置，求把s1改變為s2的方法總數。
分析：明顯的DP，注意s1和s2哪些位置相同並不重要，重要的是有幾個位置不同。改變的時候也一樣，改變哪些位置並不重要，重要的是改變之後有幾個位置不同。所以用dp[i][j]表示i次操作之後有j個位置不同的方法數，答案就是dp[t][0]。對於dp[i - 1][j]，經過一次操作之後假設把k個位置從不同變為相同，剩下m - k個位置從相同變為不同，那麼 dp[i][j + m - k - k] += dp[i - 1][j] * C(j, k) * C(n - j, m - k) 其中C(j, k)表示組合數，即從j個不同的位置選出k個改變。循環k即可。

E.Romantic Value
題目大意：給定一個無向圖，要求刪除一些邊使點p和點q不連通，首先是使花費最少，若有多組解則使刪除的邊最少。
分析：典型的最小割，最大流即可。只需要把每邊的花費c改為c = c * (|E| + 1) + 1即可使刪除的邊最少，其中|E|為邊數。為方便把|E|換為一個較大的數也可以。

F.First Digit
分析：搞笑題，就不解釋了。
G.Greedy Driver
H.Grouping
題目大意：給定一個有向圖，要求把點分為k個集合，使得每個集合中的任意兩點a, b滿足a, b互相不可到達。
分析：求出強連通分量後縮點，得到有向無環圖，dfs該圖求出各點深度(深度加權，權值為強連通分量大小)，深度最大值即答案，因為這一條路徑上任意兩點都可從深度小的一點到達深度大的一點，所以必定屬於不同集合；又可以把其它路徑(長度為len)上的各點依次歸到集合1..len。

I.Left 4 Dead
J.Sister's Noise