國(guó)家集訓(xùn)隊(duì)作業(yè)陳高遠(yuǎn)1

題目——單詞爭(zhēng)霸101學(xué)高、Sprague-Grundy題目——單詞爭(zhēng)霸101學(xué)高、Sprague-Grundy目一.題目3二.預(yù)備31.定32.SG函3的4三.題目41.題目分42.建53.動(dòng)一.題目3二.預(yù)備31.定32.SG函3的4三.題目41.題目分42.建53.動(dòng)態(tài)64.輸出8四.關(guān)于91.出題9點(diǎn)3.數(shù)據(jù)分4.估計(jì)五.附加.題目重述操作規(guī)則：給定N個(gè)字符串，每個(gè)的長(zhǎng)度不大于maxLen，組成集合D。兩身)刪除操作規(guī)則：給定N個(gè)字符串，每個(gè)的長(zhǎng)度不大于maxLen，組成集合D。兩身)刪除，玩家要選擇D中的一個(gè)字符串，將D中它的所有前綴(包含它勝負(fù)條件：如果輪到一個(gè)玩家，此時(shí)D串集合為A。將A中所有字符串按某順序排列，連接成一個(gè)字符串，要求輸出其中字典序最小的answerString。前綴:設(shè)字符串sn，ns1、s2、……、sn。字符串p的長(zhǎng)度為m，這m個(gè)字符按順序分別是p1、p2、……、pm。稱psm≤ni≤m，si=pi雙局面:雙mex運(yùn)算:對(duì)于所有元素均為自然數(shù)的集合S，mex(S)返回最小的沒有在xor:對(duì)于整數(shù)a、b，定義axorb整數(shù)第i1abi對(duì)于一個(gè)局面SG(S)S_nextiSGSG(S_nexti)值組成的集合為K。那么，SG(S)=mex(K)。特別地，沒有后繼局面的局面SSGSG(S)=0，因?yàn)榇藭r(shí)KSG0SG0，即它是必?cái)【置妗?的和2.SPRAGUE-GRUNDY函數(shù)1.定義二.預(yù)備知識(shí)的局面G1、G2、……、Gn的和GSprague-GrudndyGSGSG(G)xor……SGSGSGSG(G)。的局面G1、G2、……、Gn的和GSprague-GrudndyGSGSG(G)xor……SGSGSGSG(G)。，字典集合D要知道DSG求出所有DSG便確定了集合A。注意到每一次操作是：選擇DDDD例如，集合D{“a”,”aa”,”ac”,”acg”,”acm”}對(duì)應(yīng)了下面一棵1.題目分析三.題目解法SGSG0，SGA要由集合A：answerString不妨在S父親：它的最長(zhǎng)的前綴（不包含它自身），這個(gè)字典集合D不妨令結(jié)點(diǎn)iD[i]，SGSG0，SGA要由集合A：answerString不妨在S父親：它的最長(zhǎng)的前綴（不包含它自身），這個(gè)字典集合D不妨令結(jié)點(diǎn)iD[i]，0的father[i]樸素解法……O(N對(duì)于每個(gè)串，枚舉集合DO(maxLen)的時(shí)間。2.建樹設(shè)串s上面的那個(gè)串為u，s的父親是f，其長(zhǎng)度為n如果f不是u又因?yàn)閒是s的前綴,所有f、s及其中間的所有串的前n這樣，f也是u設(shè)串s上面的那個(gè)串為u，s的父親是f，其長(zhǎng)度為n如果f不是u又因?yàn)閒是s的前綴,所有f、s及其中間的所有串的前n這樣，f也是ufather[father[i-1]]maxLenfatherO(maxLen)。D[j]D[iD[i]D[i-1]comLenD[i-1]對(duì)于串s，設(shè)它和它上面的串u的最長(zhǎng)公共前綴長(zhǎng)度為comLenu大于comLenfsf這顯然是對(duì)的，因?yàn)閒是u的子串，它和smin(comLen,f的長(zhǎng)度)，如果f的長(zhǎng)度大于comLen，f位將與sSGiSG[i]SGdp[i][j]iSGjSGxor3.動(dòng)態(tài)規(guī)劃dp[i][j]SGSGSGO(N)的:如果一個(gè)局面S的SG(Sn，而它的后繼局面有m個(gè),SG0、1、……dp[i][j]SGSGSGO(N)的:如果一個(gè)局面S的SG(Sn，而它的后繼局面有m個(gè),SG0、1、……n-1這n它的后繼局面?zhèn)€數(shù)卻不足n。dfsi子sinowval,SGxorSGnowvalxor所有兒子的SG證明以iSG值xorSG≤這些樹的結(jié)點(diǎn)數(shù)目總和<以i這樣，對(duì)于每個(gè)結(jié)點(diǎn)，dp[i][j]jivectorO(NmaxLen)。。換一種計(jì)算方式：考慮對(duì)于任意結(jié)點(diǎn)，它的計(jì)數(shù)被+1當(dāng)且僅當(dāng)選擇dfs，dp[它的兒子][j]來(lái)計(jì)算。設(shè)結(jié)點(diǎn)inson[1]、son[2]、……、son[n]O(NmaxLen)。。換一種計(jì)算方式：考慮對(duì)于任意結(jié)點(diǎn)，它的計(jì)數(shù)被+1當(dāng)且僅當(dāng)選擇dfs，dp[它的兒子][j]來(lái)計(jì)算。設(shè)結(jié)點(diǎn)inson[1]、son[2]、……、son[n]allsonSG[son[1]]xorSG[son[2]]xorSG[son[n]]i，SGallsonkxorallsonxorSG[son[j]](dp[son[j]][k]=NmaxLenO(NmaxLen)對(duì)于串a(chǎn)、b，aba+b<b+a。說“ba”優(yōu)于“b”，因?yàn)椤癰ab”<“bba”answerstring，s[1]、s[2]、……、s[n]連接而成s[i]+s[i+1]s[i+1]+s[i](i<n)。因?yàn)槿绻皇沁@樣，O(NlogNmaxLen)。4.輸出解不妨設(shè)Gs1、s2的操作之后的局面分別是G1、G2這樣，因?yàn)檫@兩個(gè)操作均為必勝策略，所以G1、不妨設(shè)Gs1、s2的操作之后的局面分別是G1、G2這樣，因?yàn)檫@兩個(gè)操作均為必勝策略，所以G1、G2但是G1。這是在我學(xué)習(xí)SG函數(shù)之后自己想到的一個(gè)題目，因?yàn)樗每梢岳谩坝谓o定nNOIp1998NOIp（雖然那個(gè)算法很簡(jiǎn)單），因?yàn)楸绢}的特殊性，答O(NmaxLen)的算法。對(duì)于復(fù)雜度而言，該題的算法不可能更優(yōu)了，因?yàn)檩斎隣IFJ1.出題思路四.關(guān)于本題論的相關(guān)內(nèi)容：sgxor樹結(jié)構(gòu),dfs。EasySGSG304.估計(jì)分?jǐn)?shù)部分/數(shù)123456789建動(dòng)態(tài)規(guī)部分／算建