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

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

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

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

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

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

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

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

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