【bzoj3608】单词争霸

2015.06.18 10:09 Thu | 38次阅读 | 旧日oi | 固定链接 | 源码

题目大意:按字典序给出一些字符串,两个人从这些串里轮流取,一个串被取到后这个串的前缀都不能再取,求是否有先手必胜的策略,串<=100000,串长<=100.
题解:
这题是个国家集训队作业,好神啊,我自己只想到了一半,另一半想简单了……
首先我们可以把给定的串建成一颗森林,每个节点的父亲节点为这个点的前缀,这颗树怎么建呢?
因为是按字典序排列,那么每个串的父亲一定在它前面。 进一步地,它一定是它上面那个串的前缀(包括他本身) :
设串 s 上面的那个串为 u, s 的父亲是 f,其长度为 n。
如果 f 不是 u,那么,按字典序有: f<u<s
又因为 f 是 s 的前缀,所有 f、 s 及其中间的所有串的前 n 位均相同。
这样, f 也是 u 的前缀。 所以,对于 D[i],检查 D[i-1]是否为它的前缀,如果不是,检查 father[i-1], 如果仍然不是,检查 father[father[i-1]]。显然,这样的检查次数不超过 maxLen 次,因为每次取 father 长度必然严格减少。但是, 每次检查需要 O(maxLen)。
我们并不需要每次都检查串 D[j]是否是串 D[i]的子串。 事实上,我们只用求解 D[i]与 D[i-1]的公共前缀长度 comLen。 之后依次寻 找 D[i-1]的父亲,直到该串的长度不大于 comLen:
对于串 s,设它和它上面的串 u 的最长公共前缀长度为 comLen。
对于 u 的子串 f,我们要证明 f 也是 s 的子串,当且仅当 f 的长度不
大于 comLen。
这显然是对的,因为 f 是 u 的子串,它和 s 的公共前缀长度为
min(comLen,f 的长度),如果 f 的长度大于 comLen, f 在第 comLen+1
位将与 s 不同。
然后是求sg函数的过程,每次选择一个点相当于删除从这个点到根的路径,然后树又分成了一些森林,可以用一个树形DP解决。
我们令 dp[i][j]表示以 i 为根的子树所对应局面的后继局面 中,是否有某一局面的 SG 值恰好为 j。显然叶节点有sg[u]=1,dp[u][0]=1;
对于每个结点对应的局面,他的所有后继局面的 SG 值一定小于以该结点为 根的子树的结点数目。这可以按如下方式递归地证明:
证明以 i 为根的子树满足条件:
如果该子树的结点数是 1,它的后继局面的 SG 值只有 0,满足条件。
否则:对于任意操作,都将形成若干棵剩余的树,先证明这些树满
足条件。
之后, 有:
这些树的 SG 值 xor 和≤这些 SG 值之和
≤这些树的结点数目总和<以 i 为根的子树的结点数目。
证毕。 这样,对于每个结点, dp[i][j]中 j 最大仅需要以 i 为根的数的结点树数的 大小。 一个简单的方法是可以用 vector 存。 这样,对于整个问题,算法的时间、空间复杂度为 O(所有结点以它为根的树 的结点数目之和)。可以证明,它是 O(NmaxLen)。
设结点 i 有 n 个儿子,分别是 son[1]、 son[2]、„„、 son[n]。 用 allson 表示 SG[son[1]] xor SG[son[2]] xor „„ xor SG[son[n]]。 可能的后继局面有两种: 1.选取的是 i,这样,后继局面的 SG 是 allson。 2.选取的是 son[j]为根的子树的某个子结点,那么该后继局面的 SG 一 定是: k xor allson xor SGson[j]。然后转移方程如下
for(int t,v,i=0;i<son[u].size();i++)
{
v=son[u][i];t=s^sg[v];
for(int j=0;j<=siz[v];j++)
if(dp[v][j]) dp[u][t^j]=1;
}
求解出sg函数值后,如果每个森林根节点的sg函数值异或和为0的话,那么就无解了。
否则我们可以再dfs一遍,求出选择哪个点后异或和变成0了,于是就可以选择。因为是按字典序加的边,所以遍历的时候也是按字典序,最后直接输出就行了。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100005
int n,mx,cnt;
string word[N],ans[N];
vector<int> son[N];
int fa[N],siz[N],sg[N];
vector<bool> dp[N];
void tree_dp(int u)
{
    int s=0;siz[u]=1;
    for(int v,i=0;i<son[u].size();i++)
    {
        v=son[u][i];
        tree_dp(v);s^=sg[v];siz[u]+=siz[v];
    }
    vector<bool> tmp(siz[u]+1,0);dp[u]=tmp;
    dp[u][s]=1;
    for(int t,v,i=0;i<son[u].size();i++)
    {
        v=son[u][i];t=s^sg[v];
        for(int j=0;j<=siz[v];j++) 
        if(dp[v][j]) dp[u][t^j]=1;
    }
    for(int i=0;i<=siz[u];i++)
    if(!dp[u][i]) {sg[u]=i;break;}
}
void dfs(int u,int d)
{
    for(int i=0;i<son[u].size();i++) d^=sg[son[u][i]];
    if(!d) ans[++cnt]=word[u];
    for(int i=0;i<son[u].size();i++) dfs(son[u][i],d^sg[son[u][i]]);
}
int main()
{
    cin>>n>>mx;word[0]="";
    for(int i=1;i<=n;i++) cin>>word[i];
    for(int i=1;i<=n;i++)
    {
        int same=0,f=i-1;
        for(same=0;same<min(word[i].length(),word[f].length())
            &&word[i][same]==word[f][same];same++);
        while(word[f].length()>same) f=fa[f];
        fa[i]=f;son[f].push_back(i);
    }
    tree_dp(0);int tmp=0;
    for(int i=0;i<son[0].size();i++) tmp^=sg[son[0][i]];
    if(!tmp)
    {
        puts("Can't win at all!!");
        return 0;
    }
    dfs(0,0);
    for(int now=0,i=1;i<=cnt;i++) 
    for(int j=0;j<ans[i].length();j++)
    {
        cout<<ans[i][j];
        now++;if(now%50==0) puts("");
    }
}```