构造不出来,但是能判断,求调
查看原帖
构造不出来,但是能判断,求调
285617
黑影洞人楼主2023/8/11 22:58
#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 1919810
using namespace std; 
int n,head[N],to[N],nxt[N],tot;
int pos[N],rt;
string s[N];
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	to[++tot]=u^1;
	nxt[tot]=head[v^1];
	head[v^1]=tot;
} 
int ch[N][2],cnt;
void insert(string &s,int z){
	if(!rt)rt=++cnt;
	int x=rt,lst;
	for(int i=0;i<s.length();i++){
		int &y=ch[x][s[i]-'0'];
		if(!y){
			y=++cnt;
			add(x<<1|1,cnt<<1|1);
		}lst=x,x=y;
	}
	cnt++;
	add(x<<1|1,cnt<<1|1);
	add(z,cnt<<1|1);
	add(x<<1|1,z^1);
	ch[lst][s[s.length()-1]-'0']=cnt;
} 
bool cmp(int a,int b){return s[a].length()<s[b].length();}
int dfn[N],low[N],st[N],top,tmp,col,co[N];
void tarjan(int x){
	dfn[x]=low[x]=++tmp;
	st[++top]=x;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(!co[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		++col;
		while(st[top]!=x)co[st[top--]]=col;
		co[st[top--]]=col;
	}
}
signed main(){
	scanf("%d",&n);
	cnt=n;
	for(int i=1;i<=n;i++)cin>>s[i],pos[i]=i;
	sort(pos+1,pos+n+1,cmp);
	for(int k=1;k<=n;k++){
		int i=pos[k],flg=0;
		for(int j=0;j<s[i].length();j++){
			if(s[i][j]=='?'){
				s[i][j]='0';insert(s[i],k<<1);
				s[i][j]='1';insert(s[i],k<<1|1);
				s[i][j]='?'; 
				flg=1;
				break;
			}
		}
		if(!flg){
			insert(s[i],k<<1);
			add(k<<1|1,k<<1);
		}
	}
	for(int i=2;i<=(cnt<<1|1);i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=cnt;i++)if(co[i<<1]==co[i<<1|1])return puts("NO"),0;
	puts("YES");
	for(int i=1;i<=n;i++){
		for(int j=0;j<s[i].length();j++){
			if(s[i][j]=='?'){
				printf("%d %d\n",co[i<<1],co[i<<1|1]);
				if(co[i<<1]>co[i<<1|1])s[i][j]='1';
				else s[i][j]='0';
				break;
			}
		}
		cout<<s[i]<<endl;
	}
	return 0;
}



2023/8/11 22:58
加载中...