原文?https://www.facebook.com/notes/facebook-hacker-cup/2013-round-1-solutions/606859202663318

---

第一題 紙牌游戲 （20分）

John喜歡與同伴們玩一種紙牌游戲。游戲的規則如下：總共有N張牌，每個人手里拿著K張牌。每張牌上有個數字。每個人手里那副牌的強度取決于其中最大的那張牌的數字。手中牌強度最大的那個人獲勝。在揭示所有玩家的牌之前，每個人都可以打賭自己可以獲勝。

John需要你的幫助來幫助他贏得賭局。他決定當他手中牌的強度高于平均牌的強度時，他就打賭自己能獲勝。因此，Joh需要計算所有人手中牌的平均強度（就是說這N張牌的集合中所有大小為K的子集的平均強度）。John自己能做除法運算，所以他需要你幫他計算其他人手中牌的強度總和。

你的任務是：

給你一個數組N，里面最多有10,000個不同的整數。給你一個整數K，K在1到N之間。我們知道，從N個數的全集里可以找到若干個大小為K的子集，把每個子集中最大的那個數求總和。最后，把總和整除1,000,000,007取余數。?

?

---

官方答案：

這是本輪比賽中最簡單的題目，60%的參賽者都成功解決了此題。給出一個有N個不同整數的數組A，我們需要打印出 所有大小為K的子集中最大值的求和。最后的結果需要被1000000007整除取余數，你應該知道，1000000007是一個素數。

首先，我們給整個數組排序，這樣?A[1]?<?A[2]?<?...?<?A[n]。

現在，我們需要知道，對于其中任意的整數?A[i]?，它能夠在大小為K的子集中充當最大數的情況的總數，當然前提條件是?i?>=k?（因為如果 i<k，那么 A[i] 不可能是任何子集中最大的數）。好了，假設 A[i]?是一個子集中最大的數，這就意味著我們?要在?A[i]?之前的數中選取?k-1?個數。我們可以使用二項式系數公式求出?在?i-1?個數中選取?k-1?個數的方法的總數。我們把這個二項式系數記作?bin[i-1][k-1]?。

不難看出，題目要求的最終總和就是?sum?( A[i] * bin[i-1][k-1] ) ?sum里面i的下標范圍是 k?<= i?<=?n。

?

所以，現在我們需要計算所有二項式因數?bin [k - 1][k - 1], ..., bin [n - 1][k - 1] ?計算的方法有很多種，最簡單的辦法就是使用遞推公式。

bin [0][0] = 1;for (n = 1; n < MAXN; n++) {bin [n][0] = 1;bin [n][n] = 1;for (k = 1; k < n; k++) {bin [n][k] = bin [n - 1][k] + bin [n - 1][k - 1];if (bin [n][k] >= MOD) {bin [n][k] -= MOD;}}}qsort (a, n, sizeof(long), compare);sol = 0;for (int i = k - 1; i < n; i++) {sol += ((long long) (a [i] % MOD)) * bin [i][k - 1];sol = sol % MOD;}

注意，我們沒有在計算二項式因子的時候使用%取余數運算符，因為直接作減法運算要快很多。?程序總的復雜度是?排序需要花費?O (n log n)，?計算?二項式因子需要花費?O (n^2)。

另外一種計算二項式因子的算法是使用?遞推式?bin [n + 1][k] = ((n + 1) / (n + 1 - k)) * bin [n][k] ?同時使用?Big?Integer?類型做除法。?盡管這樣做也許會運行慢一點，但是這些二項式因子取余數后的結果可以事先計算一次并保存在外部文件的大表中。

還有，之前我們說過，1000000007是一個素數，你可以考慮使用?擴展歐幾里得算法?（百科鏈接），將除法運算換成對倒數的乘法，這樣可以將算法最終優化到 ?O(n log n)

參賽者最常見的錯誤出在邊界數據上，即當k=1或者k=n的時候。另外的錯誤包括，忘記定義二項式遞推的基礎條件?bin[0][0]?=?1，以及乘以兩個大數的時候忘記使用?64位整數類型來保存。

?

?

第二題 ?信息安全 (35分)

現在有一個新的消息加密系統，它的工作方式如下：

對于服務器端和客戶端之間的通信依賴于一段字符串K，K由M段組成，每段的長度是L，K中字符的取值范圍只可能是小寫字母{a, b, c, d, e, f}。另外，服務器端有個鑰匙K1，客戶端有個鑰匙K2：

? ? ? k1?=?f(k) ?其中，f是一個函數，它在k中隨機地選擇字符并把原始字符替換成？字符。?？字符意味著那個位置可能是取值范圍里的任意字母。

? ? ? k2?=?f(g(k)) ?其中，g是一個函數，它把K中的M段做隨機全排列。而f的定義跟上一段中定義相同。

你的任務是，知道K1和K2，要求解出K。?如果K有若干種可能，則字母序最小的解。?如果K無解，則輸出“IMPOSSIBLE”。

?

?

---

官方答案：

為了解決本題，我們需要分兩步走：

1.?第一個問題是： 找出是否存在一個可行解。我們需要找出?k1中的某段?和?k2中的某段?之間的關系。函數F?把隨機字符替換成問號字符，?函數G?把M段做隨機全排列。因此，k1中的某段在k2中也出現了，但是可能是按照不同的排列順序。另外，由于函數F?的影響，k1的那段與k2的那段之間?可能有區別。?所以，為了找出是否存在一個可行解，我們需要檢查k1的某段是否在k2中出現了，或者相反的情況。?但是對于?k1中的一段，在k2中可能有若干段都能與之對應（要考慮問號字符）。例如：

m = 2
k1 = "aaab"
k2 = "a???"

k1中的"aa"這段可能對應與k2中的“a?”或者"??"。這樣k1中的這一段在k2中就存在兩個候選匹配段。

要解決這個問題，我們可以使用 最大二分圖匹配 算法（英文維基鏈接）。該算法歸納如下：所有的頂點被分在兩個集合，一個集合U1代表k1中的所有段，另一個集合U2代表k2中的所有段。每個定點代表一段。定點間的關系可描述為：k2中的第j段是否是?k1中的第i段?候選匹配段。

最終，如果我們找到了一種圖最大匹配，那么表示我們找到了一個解。現在沒我們需要按照字典序輸出最小解。

2. ?第二個問題是：如果題目存在解，則需要找到字母序最小的解。這是對于參賽者來說更難解的一部分。一個簡單的辦法是：從左往右遍歷k1中所有的問號字符，把第一個問號字符換成’a‘，驗證此時是否存在一個解，如果存在解，就前往下一個問號字符，以此類推；如果不存在解，則換成'b'，再接著試。

?

該算法最壞情況下的時間復雜度是 |候選字符的集合| * |k1| * O(最大二分圖匹配)，?因為候選字符的取值只可能是{a, b, c, d, e, f}，所以 |候選字符的集合|?=?6

?

本題的代碼可以參見Dmytro的解題代碼（她排名第三）?https://fbcdn-dragon-a.akamaihd.net/cfs-ak-ash3/676632/98/332530593518613_-/tmp-/QMb6Q7

?

第三題 ?顯示器上的壞點 (45分)

一塊顯示器，寬W像素，高H像素。上面有N個壞點。第i個壞點的位置是?(x[i], Y[i])。注意，(0, 0)是左上角，(W-1, H-1)是右下角。每個壞點的位置的計算公式如下。另外，壞點有可能會重疊（落在相同的像素點上），所以總共最多有N個不同位置的壞點。?

? ? x[0] = X
? ? y[0] = Y
? ? x[i] = (x[i - 1] * a + y[i - 1] * b + 1) % W (for 0 < i < N)
? ? y[i] = (x[i - 1] * c + y[i - 1] * d + 1) % H (for 0 < i < N)

現在我們要在這個顯示器上顯示一張寬度為P像素，高度為Q像素的圖像。圖像顯示的范圍里不能有壞點。這叫做“完美顯示”該圖像。

你的任務是，已知W，H，P，Q，和壞點位置公式里的參數。要求在這塊顯示器上能“完美顯示”該圖像的位置的個數。注意，圖像不能旋轉（P只能對應X，Q只能對應Y）。

通俗地說一遍，一個W*H大小的白紙，上面有一些黑點。現在要在這白紙上圈出一個P*Q的矩形，矩形里不能有黑點。問有多少種圈法？

?

---

官方答案：

為了解決此題，我們創建一種新的數據結構來支持兩種運算：更新（插入/刪除）一個壞點?和?查詢在長度為P的范圍內有多少個連續的子區間。我們可以在線段樹的基礎上加以改進。

線段樹是一種二叉搜索樹，與區間樹相似，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉子結點。

對于線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。

因此線段樹是平衡二叉樹，最后的子節點數目為N，即整個線段區間的長度。

使用線段樹可以快速的查找某一個節點在若干條線段中出現的次數，時間復雜度為O(logN)。

參考閱讀：

《淺談線段樹在信息學競賽中的應用》?http://bbs.whu.edu.cn/wForum/boardcon.php?bid=160&id=1105529224&ftype=3&ap=269

這個改進的線段樹（區間從 0 到 W-1）可以支持兩種運算，復雜度分別為?O(logN) 和 O(1)。?代碼如下：

struct node {int left, right; // left and right boundary of the interval int leftmost_dead_pixel, rightmost_dead_pixel, count; } nd[N];int F(int left, int right) {// given the position of the left and the right dead pixel// count the different position of a continuous interval with length Preturn max(right - left - P, 0); }// O(logN) void update(int k, int dead_pixel_x) {update(leftchild, dead_pixel_x);update(rightchild, dead_pixel_x);nd[k].count = leftchild.count + rightchild.count;nd[k].count += F(leftchild.rightmost_dead_pixel, rightchild.leftmost_dead_pixel);nd[k].count -= F(leftchild.rightmost_dead_pixel, leftchild.right);nd[k].count -= F(rightchild.leftmost_dead_pixel, rightchild.left); }// O(1) void query() {return root.count; }

先把壞點按照Y軸上的位置排序，然后從左往右插入壞點，并不斷線段區間里面count數。 程序的復雜度是 O(N log N)，其中N是壞點的個數。

?

轉載于:https://www.cnblogs.com/newyorker/archive/2013/02/07/2892514.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[译] Facebook杯2013年编程挑战赛——第一轮题目及答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。