国家集训队作业陈高远1

题目——单词争霸101学高、Sprague-Grundy题目——单词争霸101学高、Sprague-Grundy目一.题目3二.预备31.定32.SG函3的4三.题目41.题目分42.建53.动一.题目3二.预备31.定32.SG函3的4三.题目41.题目分42.建53.动态64.输出8四.关于91.出题9点3.数据分4.估计五.附加.题目重述操作规则：给定N个字符串，每个的长度不大于maxLen，组成集合D。两身)删除操作规则：给定N个字符串，每个的长度不大于maxLen，组成集合D。两身)删除，玩家要选择D中的一个字符串，将D中它的所有前缀(包含它胜负条件：如果轮到一个玩家，此时D串集合为A。将A中所有字符串按某顺序排列，连接成一个字符串，要求输出其中字典序最小的answerString。前缀:设字符串sn，ns1、s2、……、sn。字符串p的长度为m，这m个字符按顺序分别是p1、p2、……、pm。称psm≤ni≤m，si=pi双局面:双mex运算:对于所有元素均为自然数的集合S，mex(S)返回最小的没有在xor:对于整数a、b，定义axorb整数第i1abi对于一个局面SG(S)S_nextiSGSG(S_nexti)值组成的集合为K。那么，SG(S)=mex(K)。特别地，没有后继局面的局面SSGSG(S)=0，因为此时KSG0SG0，即它是必败局面。 的和2.SPRAGUE-GRUNDY函数1.定义二.预备知识的局面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”}对应了下面一棵1.题目分析三.题目解法SGSG0，SGA要由集合A：answerString不妨在S父亲：它的最长的前缀（不包含它自身），这个字典集合D不妨令结点iD[i]，SGSG0，SGA要由集合A：answerString不妨在S父亲：它的最长的前缀（不包含它自身），这个字典集合D不妨令结点iD[i]，0的father[i]朴素解法……O(N对于每个串，枚举集合DO(maxLen)的时间。2.建树设串s上面的那个串为u，s的父亲是f，其长度为n如果f不是u又因为f是s的前缀,所有f、s及其中间的所有串的前n这样，f也是u设串s上面的那个串为u，s的父亲是f，其长度为n如果f不是u又因为f是s的前缀,所有f、s及其中间的所有串的前n这样，f也是ufather[father[i-1]]maxLenfatherO(maxLen)。D[j]D[iD[i]D[i-1]comLenD[i-1]对于串s，设它和它上面的串u的最长公共前缀长度为comLenu大于comLenfsf这显然是对的，因为f是u的子串，它和smin(comLen,f的长度)，如果f的长度大于comLen，f位将与sSGiSG[i]SGdp[i][j]iSGjSGxor3.动态规划dp[i][j]SGSGSGO(N)的:如果一个局面S的SG(Sn，而它的后继局面有m个,SG0、1、……dp[i][j]SGSGSGO(N)的:如果一个局面S的SG(Sn，而它的后继局面有m个,SG0、1、……n-1这n它的后继局面个数却不足n。dfsi子sinowval,SGxorSGnowvalxor所有儿子的SG证明以iSG值xorSG≤这些树的结点数目总和<以i这样，对于每个结点，dp[i][j]jivectorO(NmaxLen)。。换一种计算方式：考虑对于任意结点，它的计数被+1当且仅当选择dfs，dp[它的儿子][j]来计算。设结点inson[1]、son[2]、……、son[n]O(NmaxLen)。。换一种计算方式：考虑对于任意结点，它的计数被+1当且仅当选择dfs，dp[它的儿子][j]来计算。设结点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)对于串a、b，aba+b<b+a。说“ba”优于“b”，因为“bab”<“bba”answerstring，s[1]、s[2]、……、s[n]连接而成s[i]+s[i+1]s[i+1]+s[i](i<n)。因为如果不是这样，O(NlogNmaxLen)。4.输出解不妨设Gs1、s2的操作之后的局面分别是G1、G2这样，因为这两个操作均为必胜策略，所以G1、不妨设Gs1、s2的操作之后的局面分别是G1、G2这样，因为这两个操作均为必胜策略，所以G1、G2但是G1。这是在我学习SG函数之后自己想到的一个题目，因为它正好可以利用“游给定nNOIp1998NOIp（虽然那个算法很简单），因为本题的特殊性，答O(NmaxLen)的算法。对于复杂度而言，该题的算法不可能更优了，因为输入OIFJ1.出题思路四.关于本题论的相关内容：sgxor树结构,dfs。EasySGSG304.估计分数部分/数123456789建动态规部分／算建