社区讨论

请求NOIPT2代码错误

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lp45da25
此快照首次捕获于
2023/11/18 22:31
2 年前
此快照最后确认于
2023/11/19 09:15
2 年前
查看原帖
如下,这是我的代码(疑问点我用注释标注出来了)
CPPWANGZHAOLAN19829799068
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=1145141919810ll;
int a[N],n,m;
int head[N],tot;
struct edge{
	int next,to,d;
}e[N<<1];
void add(int from,int to,int d){
	e[++tot].next=head[from];head[from]=tot;e[tot].to=to;e[tot].d=d;
}
bool v1[N],v2[N],v3[N];
int v4[N];//v1,v2,v3,v4分别是为了算出图上有无U,图上有几个点,图上有无TF,图上可否黑白染色
bool dfs1(int x){
	v1[x]=1;bool ret=0;if(a[x]==0)ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v1[y])continue;if(dfs1(y))ret=1;}return ret;
}
int dfs2(int x){
	v2[x]=1;int ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v2[y])continue;ret+=dfs2(y);}return ret;
}
bool dfs3(int x){
	v3[x]=1;bool ret=0;if(a[x]==1||a[x]==2)ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v3[y])continue;if(dfs3(y))ret=1;}return ret;
}
bool dfs4(int x,int c){
	v4[x]=c;bool ret=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(e[i].d==1){
			if(v4[y]==0)dfs4(y,c);
			else if(v4[y]!=c)ret=0;
		}
		else{
			if(v4[y]==0)dfs4(y,3-c);
			else if(v4[y]==c)ret=0;
		}
	}
	return ret;
}
//int t,c;
signed main(){
	int t,c;//如果将这句话放到全局变量里洛谷上就可以AC了,反之就不行,求大佬指点。
   cin>>c>>t;
	while(t--){
		int ans=0;
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++){
			v1[i]=0;
			v2[i]=0;
			v3[i]=0;
			v4[i]=0;
			e[i].d=0;
			e[i].next=0;
			e[i].to=0;
			e[i+n].d=0;
			e[i+n].next=0;
			e[i+n].to=0;
		}
		for(int i=1;i<=n;i++)a[i]=i;
		while(m--){
			char x;scanf("%s",&x);//经检测,如果t在局部变量里,到这里t会直接归零,请求这是为啥
			if(x=='-'){int l,r;scanf("%lld%lld",&l,&r);a[l]=-a[r];}
			if(x=='+'){int l,r;scanf("%lld%lld",&l,&r);a[l]=a[r];}
			if(x=='U'){int l;scanf("%lld",&l);a[l]=0;}
			if(x=='T'){int l;scanf("%lld",&l);a[l]=n+1;}
			if(x=='F'){int l;scanf("%lld",&l);a[l]=-n-1;}
		}
		tot=0;for(int i=1;i<=n;i++)head[i]=0;
		for(int i=1;i<=n;i++){
			if(abs(a[i])<=n&&a[i]!=0){
				if(a[i]==i);else if(-a[i]==i)a[i]=0;else {add(i,abs(a[i]),abs(a[i])/a[i]);add(abs(a[i]),i,abs(a[i])/a[i]);a[i]=n+114;}
			}
			if(a[i]==-n-1)a[i]=1;
			if(a[i]==n+1)a[i]=2;
		}
		for(int i=1;i<=n;i++){
			if(!v1[i]){
				int num=dfs2(i);
				if(dfs1(i)){
					ans+=num;
				}
				else if((!dfs3(i))&&(!dfs4(i,1))){
					ans+=num;
				}
			}
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...