关于第四个数据点的提示(未思考勿进)
查看原帖
关于第四个数据点的提示(未思考勿进)
172516
empty_zhm楼主2022/5/29 00:13

这份是我在第 44 个测试点出问题的代码:

#include<bits/stdc++.h>
#define LL long long
#define N 2000010
using namespace std;
struct edge
{
	int v,nxt;
	edge(){v=nxt=0;}
}E[N];
int head[N],Esiz,In[N];
void addedge(int u,int v)
{
	Esiz++;
	E[Esiz].v=v;
	E[Esiz].nxt=head[u];
	head[u]=Esiz;
}
int End[N],T[N][26];
int Tsiz,Cnt;
int Insert(string S)
{
	int rt=0,l=S.size();
	for(int i=0;i<l;i++)
	{
		int x=S[i]-'a';
		if(!T[rt][x]) T[rt][x]=++Tsiz;
		rt=T[rt][x];
	}
	if(End[rt]) return End[rt];
	return End[rt]=++Cnt;
}
int vis[N];
int dfs(int u)
{
	int rtn=1;
	vis[u]=1;
	for(int i=head[u];i;i=E[i].nxt)
	{
		int v=E[i].v;
		if(vis[v]) continue;
		rtn+=dfs(v);
	}
	return rtn;
}
int main()
{
	string A,B;
	while(cin >> A >> B)
	{
		int a=Insert(A),b=Insert(B);
		addedge(a,b);
		addedge(b,a);
		In[a]++;
		In[b]++;
	}
	if(dfs(1)!=Cnt)
	{
		puts("Impossible");
		return 0;
	}
	int Sum=0;
	for(int i=1;i<=Cnt;i++)
		Sum+=In[i]&1;
	if((Sum==0)||(Sum==2)) puts("Possible");
	else puts("Impossible");
	return 0;
}

而事实上,dfs 执行的连通块大小计数理论上是没问题的。然后我就调了半天,没发现任何问题,而玄学的是把判断条件改成:

if(dfs(1)<Cnt)
}
	puts("Impossible");
	return 0;
}

时,AC了。

然后我觉得十分不对劲,为什么连通块计数会出问题,最后我意识到了问题:可能没有木棍。也就是说我自认为一定存在的编号为 11 的点其实是不存在的。所以连通块计数自然而然就为 11 而大于原本的 00 ,然后就WA了。

最后,其实只需要特判 Cnt==0 的情况就好了。浪费了我蛮多时间的还。这里写出来让大伙注意一下()

2022/5/29 00:13
加载中...