阿里巴巴2011程序設(shè)計方案公開賽的解題報告

1、以下是解題報告1001 Coin Game類型:博弈/想法題（簡單）假設(shè)我們有 10 枚硬幣 ,K=2, 第一個玩家拿走一枚之后 , 第二個玩家在圓的對稱點拿走相應(yīng)的 , 保持剩下的兩邊 硬幣相等 , 這樣不管第一個玩家怎么取 , 第二個玩家只要在另一邊一樣的取法就能保證自己是最后一個取硬幣 的.也可以根據(jù)SG定理知道，SG值一樣的兩個游戲為必敗狀態(tài) .推廣到更大的情況也一樣，所以第一個玩家勝利的情況只可能是N為奇數(shù)且K為1,或者K>=N,其他情況均第二個玩家勝 .當(dāng)然你也可以用 sg 定理去推出初始狀態(tài)的必勝必敗情況 , 從而得到規(guī)律 . 不過比較費時間且沒有上述推論直 觀.1002

2、Fruit Ninja類型:幾何（簡單）假設(shè)有一條線穿過一些水果 , 那么我們將這條線平移 , 使之與一水果的一個點相交 , 然后按這個點進行旋轉(zhuǎn) , 又 可以使之與另一水果的一個點相交 . 這次這條線還是穿過這些水果 .所以 , 我們可以枚舉兩兩水果的點做直線 , 然后計算該線穿過水果的個數(shù)數(shù)據(jù)規(guī)模很小，隨意隨便搞.復(fù)雜度05人3*33）.1003 I'll play a trick on you類型:非主流（簡單）呵呵 , 本題的名字就是我會和你開個小玩笑 .第一眼看到這題 , 很容易得到 99-72=27 這樣的結(jié)論 , 并且?=15 的時候,36-21 =15 和28-15=1

3、3 都是成立的 估計會有很多人看到此處就會提交 A-B, 而且范圍里給了 1<=B<=A<= 10100 , 很容易讓人用大數(shù)提交 .但是，最后一個7卻不符合21-13=7的規(guī)律，所以. 提交A-B是AC不了的.其實真相就是 9+9+7+2=27,4+5+2+7=18 而?=12. 6 組數(shù)據(jù)全部說的通只需要把所有數(shù)字加加起來就好了 .其實A和B數(shù)據(jù)范圍這么大已經(jīng)給了很大提示了 ，就禁止大家往很復(fù)雜的方面想，什么素數(shù)啊什么的.作為非主流題 , 如果有人能算出 ?并且和給出和官方不一樣的解釋 , 那就悲劇了 , 所以 Hint 里加了句如果能有 更牛逼的解法但 AC不了，我本人

4、給以小安慰一下1004 Level up類型:數(shù)據(jù)結(jié)構(gòu) -線段樹（中等）題意很簡單 ， 成段更新 ， 成段詢問 ， 但是更新卻和一般的線段樹大不一樣 ， 每個點雖然接收到相同的信息 ， 但是由 于本身不同 ， 最終得到的值也是不同的 . 用一般的延遲操作就搞不定了 .突破點在 K， 范圍很小 ， 只有 10， 可以考慮每次有人升級的時候 ， 就遞歸的找下去 ， 將這個人進行升級操作 . 由于 找到某個人只需要 logn 的復(fù)雜度 ， 每個人最多升 k 次， 所以 n 個人的復(fù)雜度是 O（nklogn）用了兩個輔助數(shù)組 addmaxn 和 MAXmaxkmaxn，add 用于記錄延遲標(biāo)記 ，MA

5、Xk 表示該區(qū)間等級為 k 的最大經(jīng)驗值 . 初始化 add，MAX1 為 0， 其他為 -1， 表示無人在這個等級 . 當(dāng) MAXk 的值大于等于 Needk 時， 就對這個區(qū)間進行升級操作 ， 和線段樹操作一樣遞歸的將這個區(qū)間能升級的人全部升級 .單次操作可能會是 nlogn（ 每個人都升級 ）， 但是平均下來還是只有 nklogn.1005 March類型: 搜索（中等偏簡單 ）理解題意搞清楚優(yōu)先級后 ， 然后簡單的搜過去就好 . 提幾個注意點 :1. 奇數(shù)行和偶數(shù)行的 6 個方向行走坐標(biāo)變化是不一樣的 .2. 就算你當(dāng)前只剩 0.25MPs， 你也可以走任意一格 ， 這樣會你消耗光你這

6、回合剩下的 MPs3. 敵人優(yōu)先級最高 . 在 ZOCs 間走消耗所有 MPs4. 然后是路5. 然后是河流6. 最后才考慮前進格子的地形7. 為了避免不必要的錯誤 ， 數(shù)據(jù)已經(jīng)保證了這邊有河流 ， 對應(yīng)的那格也有河流1006 SanguoSHA類型:模擬+狀態(tài)DP（難）如果沒玩過三國殺的話這題簡直做這題就是天方夜譚了 ， 就像國外那種巨長模擬題一樣 ， 規(guī)則巨復(fù)雜 ， 不過我給 沒玩過三國殺的人看過題目 ， 還是能看明白的 ， 就是累了點 .1-3 主要是介紹三國殺的一般規(guī)則 , 玩過的童鞋掃一遍就 ok 了,4 和 5 才是題目重點 , 標(biāo)記規(guī)則和攻擊規(guī)則 , 需 要仔細閱讀dp 的狀態(tài)是

7、round:80state_nj:5state_all:3A6;round 表示回合數(shù) ,8 個人 *10 論state_nj: 表示內(nèi)奸狀態(tài) ,0: 未知身份 ,1: 被認(rèn)為忠臣 ,2: 被認(rèn)為反賊 ,3: 被認(rèn)為內(nèi)奸 ,4: 死State_all: 表示除主公內(nèi)奸的其他角色狀態(tài) ,0 未知身份 ,1 身份被標(biāo)記 ,2 死亡（ 由于大家都按常規(guī)出牌 , 反賊和忠誠不會被標(biāo)記成其他角色 ）然后就是安步就班的模擬下去 .建議寫個函數(shù) , 標(biāo)注 a 攻擊 b 之后狀態(tài)的變化情況 , 然后無論誰攻擊誰都調(diào)用這個函數(shù)就簡單方便很多這種模擬題還是多分成小塊來寫的好 , 容易差錯標(biāo)稱寫了 16 個函數(shù)10

8、07 Street Fighter類型 :dancing links（ 中等 ）很直觀的最小支配集問題 , 用 dancing links 的重復(fù)覆蓋很好解決 .但是由于每個角色只能選一次 , 即一個角色只能選一個模式 . 所以這又是精確覆蓋 .一共有sigma（Mi）+N列,sigma（Mi）列在搜索時需要重復(fù)覆蓋，另外的N列表示角色的選擇，需要精確覆蓋.最后只要判斷覆蓋了 sigma（Mi） 列就 ok 了.需要再模板上改好一些內(nèi)容 , 任何一小點都很容易導(dǎo)致死循環(huán) .1008 Tower Defence類型:插頭DP（難）題目要求放 W使得路線最長，我們反過來理解，就可以找一條最長的路（

9、邊不重合）,然后在這路的邊上放滿 W就 ok 了.（ 或者其他所有的格子都放 W）為了保證這條路徑邊不重合 ， 我們不僅需要記錄輪廓線上方的插頭狀態(tài) ， 還需要記錄上方的路的狀態(tài) . 比如 : 如 果當(dāng)前格上方有路 ， 但是上方?jīng)]有插頭 ， 這樣這格就不能建任何路了 ， 因為在這格建的路不能和上方的路連起來 必然導(dǎo)致邊的重合 .由于S和T都不固定，需要有獨立插頭，括號表示法的話會比較難寫.建議用最小表示法來標(biāo)記插頭1009 Board Game Dice 類型:數(shù)學(xué)(簡單) 就是等比公式化簡一下 . 高中數(shù)學(xué) . 概率學(xué)的好的童鞋應(yīng)該一眼就能看出答案 最后的答案是 Mx*x/N.1010 World of Warcraft類型:NP(無解)我錯了 ， 大家原諒 T_T以下是原來錯誤的方法出題的時候很怕這題被按結(jié)束時間優(yōu)先的方式貪心過去 ，但是貪心沒辦法處理開始時間和結(jié)束 時間都相同的指令的安排 ，我特地造了幾組數(shù)據(jù)卡這種貪心 .不知道實際比賽中有木有大神能 用更犀利的貪心貪過去 .正解是網(wǎng)絡(luò)流 ，建一個包含源匯六層的模型 .第一層 : 源點 (1)第二層 :指令 (100)第三層 : 快捷鍵按時間拆點 (104*100)第四層 : 按鍵按時間拆點 (