Problem
Solution
可能是因为快要省选了，所以最近更博的频率好像高了点_(:зゝ∠)_
每个字符串最多有两个状态，然后要满足一些依赖关系，考虑2sat。可以先把字符串的结束节点在Trie树上建出来，这样它的前缀就是它的祖先，它作为前缀的就是它子树内的节点。利用Trie树的结构，建一棵向下的一棵向上的树优化连边，这样边数就减少到了 (O(n)) 的级别。
然而我高高兴兴写完之后连样例都过不去，调一调发现当两个字符串在同一个结束节点时也应该相互连边。为了避免边数退化，就把这些重复节点搞成链表的形式，复杂度就对了。但这样可能产生一个问题，因为链表是单向的，后来的一些点可能无法连向原来子树中的点，因此我们把所有字符串按长度排序，保证挂链表时结束节点的子树为空即可。
时间复杂度 (O(n))，但是带了 (6) 的常数。
Code
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
typedef long long ll;
const int maxn=3000010;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
x=0;int f=0;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
if(f) x=-x;
}
struct data{int v,nxt;}edge[maxn<<1];
int n,p,tot,dfc,top,scc,head[maxn],len[maxn],rk[maxn],ch[maxn][2];
int dfn[maxn],low[maxn],stk[maxn],in[maxn],bel[maxn];
char str[500010];
string s[500010];
int A(int x){return x<<1;}
int B(int x){return x<<1|1;}
int cmp(const int &x,const int &y){return len[x]<len[y];}
void insert(int u,int v)
{
edge[++p]=(data){v,head[u]};head[u]=p;
u^=1;v^=1;
edge[++p]=(data){u,head[v]};head[v]=p;
}
void ins(int id,int x)
{
int rt=n+1,lst;
for(int i=0;i<len[id];i++)
{
if(!ch[rt][s[id][i]-'0'])
{
ch[rt][s[id][i]-'0']=++tot;
insert(B(rt),B(tot));
}
lst=rt;rt=ch[rt][s[id][i]-'0'];
}
++tot;
insert(B(rt),B(tot));
insert(x,B(tot));
insert(x,A(rt));
ch[lst][0]==rt?ch[lst][0]=tot:ch[lst][1]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++dfc;stk[++top]=x;in[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
if(!dfn[edge[i].v]){tarjan(edge[i].v);getmin(low[x],low[edge[i].v]);}
else if(in[edge[i].v]) getmin(low[x],dfn[edge[i].v]);
}
if(dfn[x]==low[x])
{
int tmp;++scc;
do{
tmp=stk[top--];
in[tmp]=0;
bel[tmp]=scc;
}while(tmp^x);
}
}
void input()
{
read(n);tot=n+1;
for(int i=1;i<=n;i++)
{
scanf("%s",str);
s[i]=str;rk[i]=i;
len[i]=s[i].length();
}
sort(rk+1,rk+n+1,cmp);
for(int i=1;i<=n;i++)
{
int j=rk[i],pos=-1;
for(int r=0;r<len[j];r++)
if(s[j][r]=='?')
{
pos=j;
s[j][r]='0';ins(j,A(j));
s[j][r]='1';ins(j,B(j));
s[j][r]='?';
break;
}
if(pos==-1)
{
ins(j,A(j));
insert(B(j),A(j));
}
}
}
int main()
{
input();
for(int i=2,lim=B(tot);i<=lim;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=tot;i++) if(bel[A(i)]==bel[B(i)]){puts("NO");return 0;}
puts("YES");
for(int i=1;i<=n;i++)
{
for(int j=0;j<len[i];j++)
if(s[i][j]=='?')
{
s[i][j]=(bel[A(i)]<bel[B(i)]?'0':'1');
break;
}
cout<<s[i]<<endl;
}
return 0;
}