题解：AT_arc219_a [ARC219A] Similarity

· · 题解

前置芝士：trie 树

声明：以下称字符串 A 的第 i 个字符为 A_i。

题意概述：

给定 n 个长度为 m 的 01 字符串 S_1,S_2,\dots,S_n，构造一个长度为 m 的 01 字符串 T，满足 \forall i\in\left[1,n\right],\exist x\in\left[1,m\right]\land S_{i,x}=T_x。如果存在 T，第一行输出 Yes，第二行输出 T；否则，输出一行 No。1\le n\le 2\times 10^4,1\le m\le 100,S_i\ne S_j\left(i\ne j\right)。

正难则反，考虑对于一个 01 字符串 S_i，怎样构造是对其不合法的。不难发现，当且仅当构造 S 的反串时不合法。

:::info[01 字符串的反串]

定义一个长度为 m 的 01 字符串 S 的反串为 T，当且仅当 T 为 01 字符串，\lvert S\rvert=\lvert T\rvert 且 \forall i\in\left[1,m\right],S_i\ne T_i。通俗地说，将 S 的每一位取反（1 变 0，0 变 1），得到的新字符串 T 为原字符串 S 的反串。

:::

因此，设 T_i 为 S_i 的反串，只要最终构造出的 T 满足 \forall i\in \left[1,n\right],T\ne T_i，那么 T 就是合法的。

这不就是赤裸裸的 trie 树上跑 dfs，找到不存在的节点吗？

考虑把每个 T_i 扔到 trie 树里，然后从根节点（也就是 0 号节点）开始 dfs，设当前搜索到了第 k 位，位于节点 p。

如果把 trie 树跑满了还是没有找到答案，那就是没有答案了。

为什么找到空节点一定是对的呢？因为假设当前的 p 没有 0 儿子，那么 T 的这一位为 0，无论其他位如何，T 都必然不会与任何 T_i 相同，也就是合法的。没有 1 儿子同理。

现在分析复杂度。

最坏情况下，trie 树每层放满节点且不能超过 n 个节点，因此总节点数最多达到 \sum\limits_{i=0}^m\min\left(2^i,n\right)\le m\times n，故空间复杂度可视为 O\left(n\times m\right)。

读入和构建 trie 树的时间复杂度都是 O\left(n\times m\right)，dfs 遍历 trie 树的时间复杂度最坏达到总节点数，因此总时间复杂度为 O\left(n\times m\right)。

既然足以通过本题，那么代码如下：

const int N=20005,M=105;
int n,m;
char s[M],ans[M];
int tot,son[N*M][2];  //记得将空间开够 
inline void add()
{
    int pos=0;
    for(int i=1,num=0;i<=m;i++)
    {
        num=(s[i]-'0');
        if(!son[pos][num]) son[pos][num]=++tot;
        pos=son[pos][num];
    }
}
int dfs(int p,int k)
{
    if(k==m+1) return -1;
    if(!son[p][0])
    {
        ans[k]='0';
        return k;
    }
    if(!son[p][1])
    {
        ans[k]='1';
        return k;
    }
    ans[k]='0';
    int end_k=dfs(son[p][0],k+1);
    if(end_k!=-1) return end_k;
    else
    {
        ans[k]='1';
        end_k=dfs(son[p][1],k+1);
        return end_k;
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            if(s[j]=='0') s[j]='1';
            else s[j]='0';
        add();
    }
    int end_k=dfs(0,1);
    if(end_k==-1) puts("No");
    else
    {
        for(int i=end_k+1;i<=m;i++) ans[i]='0';
        puts("Yes"),printf("%s\n",ans+1);
    }
    return 0;
}