全WA求调,错误很离谱
查看原帖
全WA求调,错误很离谱
643818
I_AK_CTS楼主2025/6/27 10:10

我的错误居然是输出的时候字符串长度不对。说是 expected length 4 on line 4,but found word length 3。

也不是无解有解错了,求调

#include<bits/stdc++.h>
using namespace std;
const int T=5e6+10,N=1e6+5,D=3e6+5;
int n,m,flag,rt,cnt,ID[N>>1],tr[N][26],dfn[D],low[D],ti,sk[D],top,in[D],scc[D];
vector<int> G[D],V[N];
map<string,int> idx;
string s[N>>1];
void ins(string t,int id)
{
	int len=t.size(),cur=rt;
	for(int i=0;i<len;i++)
	{
		int x=t[i]-'0';
		if(!tr[cur][x])
			tr[cur][x]=++cnt;
		cur=tr[cur][x];
	}
	V[cur].push_back(id);
}
void build1(int u)
{
	for(int i=0;i<2;i++)
	{
		int v=tr[u][i];
		if(!v) continue;
		G[v].push_back(u);
		G[u+N].push_back(v+N);
		build1(v);
	}
}
void build2(int u,int lst)
{
	for(int x:V[u])
	{
		if(lst) G[x].push_back(lst);
		G[u].push_back(x^1);
		G[x].push_back(u+N);
		if(lst) G[lst+N].push_back(x^1);
	}
	for(int i=0;i<V[u].size();i++)
		for(int j=i+1;j<V[u].size();j++)
		{
			int i1=V[u][i],i2=V[u][j];
			G[i1].push_back(i2^1);
			G[i2].push_back(i1^1);
		}
	for(int i=0;i<2;i++)
	{
		int v=tr[u][i];
		if(!v) continue;
		build2(v,u);
	}
}
void tj(int u)
{
	dfn[u]=low[u]=++ti,sk[++top]=u,in[u]=1;
	for(int v:G[u])
	{
		if(!dfn[v]) tj(v),low[u]=min(low[u],low[v]);
		else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		while(true)
		{
			int x=sk[top--];
			in[x]=0,scc[x]=cnt;
			if(x==u) break;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n,rt=cnt=2*n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i],m=s[i].size(),flag=0;
		if(++idx[s[i]]==3){cout<<"NO";return 0;}
		for(int j=0;j<m;j++)
			if(s[i][j]=='?'){flag=1,ID[i]=j;break;}
		if(flag)
		{
			s[i][ID[i]]='0',ins(s[i],2*(i-1));
			s[i][ID[i]]='1',ins(s[i],2*i-1),s[i][ID[i]]='?';
		}
		else
		{
			ins(s[i],2*(i-1)),ins(s[i],2*i-1);
			if(s[i][0]=='0') G[2*i-1].push_back(2*i-2);
			else G[i*2-2].push_back(i*2-1); 
		}
	}
	build1(rt),build2(rt,0),cnt=0;
	for(int i=0;i<2*n;i++)
		if(!dfn[i]) tj(i);
	for(int i=0;i<n*2;i+=2)
		if(scc[i]==scc[i^1])
		{
			cout<<"NO";
			return 0;
		}
	cout<<"YES\n";
	for(int i=0;i<n*2;i+=2)
	{
		if(scc[i]<scc[i^1])
		{
			s[i/2+1][ID[i/2+1]]='0';
			for(int j=0;j<s[i/2+1].size();j++)
				cout<<s[i/2+1][j];
			cout<<"\n"[i==2*n-2];
		}
		else
		{
			s[i/2+1][ID[i/2+1]]='1';
			for(int j=0;j<s[i/2+1].size();j++)
				cout<<s[i/2+1][j];
			cout<<"\n"[i==2*n-2];
		}
	}
	return 0;
}
2025/6/27 10:10
加载中...