集訓(xùn)隊作業(yè)陳高遠(yuǎn)演示

1、原創(chuàng)題目講解WordCraft北京101中學(xué) 陳高遠(yuǎn)WordCraft是一個雙人游戲。游戲的唯一參數(shù)是一個字符串集D。雙方輪流進(jìn)行。輪到某玩家，他必須進(jìn)行操作：選擇D中的一個串s，將D中所有s的前綴（包含s）刪除。不能操作就輸了！題目回顧2該游戲一定會結(jié)束，因為每次操作D中的字符串?dāng)?shù)至少減1。當(dāng)輪到玩家，此時D是空集，那他就輸了。關(guān)鍵點3如何解決？最基本的方法：博弈樹？可行嗎？例子：“a”，“abc”，“b”狀態(tài)過多：O(2N)分析4為何狀態(tài)過多？因為沒有充分利用題目條件！題目中的關(guān)鍵字：“前綴”。這讓我們想到了樹結(jié)構(gòu)。例:“a”，“aa”，“ac”，“acg”，“acm”分析5這樣，每次操作

2、就變成：選擇某一結(jié)點，刪除該結(jié)點到根的路徑上的所有節(jié)點。比如，上例中，可以進(jìn)行的所有操作之后的局面：分析6這樣，一個局面可以看作是若干個樹組成。注意到所有操作只對其中的一棵樹進(jìn)行，與其他樹無關(guān)。這讓我們聯(lián)想到游戲的和。我們要利用SG函數(shù)來求解。分析7分析：如果我們能夠求出任何局面的SG值，那么我們就能知道初始的局面先手是否有必勝策略。以及，先手第一步應(yīng)當(dāng)如何走。例子： SG = 1 xor 3 xor 2 = 0 所以，必敗！分析8所以，本題可分為如下部分求解：一、建樹二、求解SG值三、輸出解分析9需要建的是什么樹？每個結(jié)點的父親是它的（除了它自己外）最長的前綴。最基本算法：O(N2maxLe

3、n)：對于每個結(jié)點，遍歷集合D，找到這樣的父親。怎么優(yōu)化？利用字典序建樹10每個字符串的父親如何找？不妨令D0 = “” ：void Find_Father(int i)int j =i-1;while(Dj不是Di的前綴)j = fatherj;fatheri = j; 建樹11復(fù)雜度是多少？j = fatherj 最多進(jìn)行 maxLen 次。每次判斷前綴關(guān)系要O(maxLen)一共是O(NmaxLen2)優(yōu)化？判斷前綴關(guān)系的優(yōu)化：計算Di與Di-1的公共前綴長度comLen即可。之后，Dj是Di的前綴當(dāng)且僅當(dāng)Dj.length() Len這樣，復(fù)雜度是O(NmaxLen)建樹12從底向上依

4、次求解。在求解某結(jié)點i時：枚舉所有可能的操作 O(N)計算操走后的局面的SG值 O(N)需要預(yù)處理：每個結(jié)點的所有兒子的SG值NIM和。(xor)所以，總復(fù)雜度是O(N3)?枚舉所有操作時進(jìn)行一次DFS，遍歷時順帶計算出SG值。時間復(fù)雜度O(N2)求解SG值13注意到這樣的事實：一個結(jié)點i為根的子樹，一次操作后局面的SG值不可能大于該子樹的結(jié)點數(shù)目。重新計算復(fù)雜度：(NmaxLen)求解SG值14事實上，還有一種對于每個結(jié)點不再進(jìn)行一次DFS的解法。因為從一個結(jié)點DFS，這個過程其實在從它的兒子進(jìn)行DFS時完成了。時間關(guān)系先不講了，論文里有詳細(xì)介紹。復(fù)雜度仍然是O(NmaxLen)求解SG值1

5、5顯然，我們進(jìn)行一次DFS就可以把所有的第一步可以取的字符串列舉出?，F(xiàn)在的問題是：給定n個字符串，請你按某順序?qū)⑺械拇B接起來，輸出字典序最小的。比如：串“ab”，“b”，我們可以連接得到 “abb”和“bab”，我們?nèi)∏罢?。這道題是我很久以前想到的。后來我發(fā)現(xiàn)，這道題是NOIp1998提高組第二題！輸出解16解法就是排序，不是按照字典序排，而是：對于兩串，比較誰排在前面的時候這兩個串連接起來的字典序更小。int cmp(const void *a,const void *b)string A = *(string*)a , B = *(string*)b;if( A+B B+A)retur

6、n -1;elsereturn 1;輸出解17請大家自己證明正確性。特別地，如果這些串中沒有一個是另外一個的子串，這個比較等價于比較字典序。所以，按字典序輸出即可。我們并不需要再排序了，因為DFS時的遍歷順序就是字典序，前提是建樹時按順序來。時間復(fù)雜度：O(NmaxLen)輸出解18至此，三部分都被我們解決了！而給出的最優(yōu)解的時間復(fù)雜度都是O(NmaxLen)。這不可能更優(yōu)，因為輸入輸出的復(fù)雜度和這一樣。在時間復(fù)雜度方面，完美解決啦 解決！19最初的題目是我學(xué)完SG函數(shù)的時候想到的：給定一棵二叉樹，初始時，所有結(jié)點是白的，雙方輪流操作，每次選一個白結(jié)點，將該結(jié)點到根的路徑上的所有結(jié)點涂黑。如果

7、一個人無法操作，他就輸了。出題思路20之后，想到字符串的前綴關(guān)系就是一棵樹，于是，題目描述就變成現(xiàn)在的樣子了。最后，我又想到了那道我出的、NOIp的題目于是在輸出解的時候加上了它。題目的模型就全部完成。題目描述用了OI界知名的FJ的奶牛故事。至此，題面就全都完成了。出題思路21考查點較為豐富：字符串前綴與樹模型的聯(lián)系組合游戲論的相關(guān)知識SG函數(shù)、游戲的和xor運算樹結(jié)構(gòu),dfs動態(tài)規(guī)劃思想猜想及證明的能力時間、空間復(fù)雜度的計算其他考查點22對于每一部分上面（或者說，論文中）介紹了種方法，每種方法的時間復(fù)雜度如下：數(shù)據(jù)分析部分算法EasyNormalHard建樹O(N2maxLen)O(NmaxLen2)O(NmaxLen)動態(tài)規(guī)劃O(N3)O(N2)O(NmaxLen)輸出解O(N!NmaxLen)O(NlogNmaxLen)O(NmaxLen)23根據(jù)給定數(shù)據(jù)規(guī)模，下表顯示了要保證能通過每一個數(shù)據(jù)點在三部分需要選擇的算法：最深色表示要選最優(yōu)的算法，次深色代表至少要選次優(yōu)算法，淺色代表種算法中任何一種均可。數(shù)據(jù)分析24沒學(xué)過SG函數(shù)：不好做，估計只有的分?jǐn)?shù)