CSP 点亮数字人生(原创代码100分)未使用拓扑排序,全靠感觉

CSP 点亮数字人生 202009 满分ac 100分

代码如下:

解题思路就是:
初始化能运行的部件,不断更新可以运行的部件,运行到最后如果发现还有部件未运行或者不能运行,则说明有环路。

原来的代码:40分

#include"stdio.h"
#include"iostream"
#include"string"
using namespace std;
struct IN{
	int in;
	int num;
	int sp;
};
struct F{
	int fg;	//func
	int k;	//输入个数 
	IN in[5];
	int out;
	int ready;
};
int Q;
int M,N;
int  S;
int Not(int a){
	return 1-a;
}
int  And(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		t=tf.in[i].sp;
	}
	return t;
}
int  Or(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		t=t|f.in[i].sp;
	}
	return t;
}
int  Xor(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		if(t!=f.in[i].sp){
			t=1;
		}
		else{
			t=0;
		}
	}
	return t;
}
int  Nand(F f){
	return 1-And(f);
}
int  Nor(F f){
	return 1-Or(f);
}
int find(char s[5]){
	if(s[0]=='A'){
		return 2;
	}
	else{
		if(s[0]=='O'){
			return 3;
		}
		else{
			if(s[0]=='X'){
				return 4;
			}
			else{
				if(s[1]=='A'){
					return 5;
				}
				else{
					if(s[2]=='T'){
						return 1;
					}
					else return 6;
				}
			}
		}
	}
	return 0;
}
int getnum(char s[10]){
	int i=1,num=0;
	while(s[i]!=0){
		num=num*10+s[i]-'0';
		i++;
	}
	return num;
}
int work(F *f){
	int fla[501];
	for(int i=1;i=N;i++){
		fla[i]=0;
	}
	int flag=1,count2,count1=0,fff=0;
	while(flag){
		count2=count1;
		count1=0;
		flag=0;
		for(int i=1;i=N;i++){
			if(f[i].ready==f[i].kfla[i]==0){
				int fg=f[i].fg;
				switch (fg){
					case 1:f[i].out=Not(f[i].in[0].sp);break;
					case 2:f[i].out=And(f[i]);break;
					case 3:f[i].out=Or(f[i]);break;
					case 4:f[i].out=Xor(f[i]);break;
					case 5:f[i].out=Nand(f[i]);break;
					case 6:f[i].out=Nor(f[i]);break;
					default:break;
				}
				fla[i]=1;
				for(int ii=1;ii=N;ii++){
					for(int iii=0;iiif[ii].k;iii++){
						if(f[ii].in[iii].in==0f[ii].in[iii].num==i){
							f[ii].in[iii].sp=f[i].out;
							f[ii].ready++;
						}
					}
				} 
			}
		}
		for(int i=1;i=N;i++){
			if(fla[i]==0){
				flag=1;
				count1++;
			} 
		} 
		if(count2==count1count1!=0){
			fff=1;
			flag=0;
		}
	} 
	if(fff){
		return 1;
	}
	return 0;
}
int main(){
	int in[500][100];
	int out[500][100];
	int si[100];
	scanf("%d",Q);
	for(int i=0;iQ;i++){
		F f[501];
		scanf("%d%d",M,N);
		for(int j=1;j=N;j++){
			char s[5];
			int k;
			scanf("%s%d",s,k);
			f[j].k=k;
			f[j].fg=find(s);
			for(int l=0;lk;l++){
				char L[10];
				scanf("%s",L);
				if(L[0]=='I'){
					f[j].in[l].in=1;
				}
				else{
					f[j].in[l].in=0;
				}
				f[j].in[l].num=getnum(L);
			}
		}
		scanf("%d",S);
		for(int i1=0;i1S;i1++){
			for(int j=1;j=M;j++){
				scanf("%d",in[i1][j]);
			}
		}
		for(int i1=0;i1S;i1++){
			scanf("%d",si[i1]);
			for(int j=0;jsi[i1];j++){
				scanf("%d",out[i1][j]);
			}
		}
		int w=0;
		for(int i=0;iS;i++){
			for(int ii=1;ii=N;ii++){
				f[ii].ready=0;
			}
			for(int j=1;j=M;j++){
				for(int ii=1;ii=N;ii++){
					for(int jj=0;jjf[ii].k;jj++){
						if(f[ii].in[jj].in==1f[ii].in[jj].num==j){
							f[ii].in[jj].sp=in[i][j];
							f[ii].ready++;
						}
					}
				}
			}
			w=work(f);
			if(w==1){
				printf("LOOP\n");
				break;
			} 
			else{
				for(int j=0;jsi[i];j++){
					printf("%d ",f[out[i][j]].out);
				}
				printf("\n");
			}
		} 
	}
	return 0;
}


/*
2
2 6
NOR 2 O4 I2
AND 2 O4 O6
XOR 2 O5 O1
NOT 1 O6
NAND 2 O2 O2
AND 2 I1 O3
2
0 0
1 0
3 2 3 4
6 1 2 3 4 5 6
3 5
XOR 2 I1 I2
XOR 2 O1 I3
AND 2 O1 I3
AND 2 I1 I2
OR 2 O3 O4
4
0 1 1
1 0 1
1 1 1
0 0 0
2 5 2
2 5 2
2 5 2
2 5 2

*/


后续:终于100了
改了两个小地方 一是因为数组设置太小 另一方面在判环更改了一下。

#include"stdio.h"
#include"iostream"
#include"string"
using namespace std;
struct IN{
	int in;
	int num;
	int sp;
};
struct F{
	int fg;	//func
	int k;	//输入个数 
	IN in[5];
	int out;
	int ready;
};
int Q,M,N,S;
int Not(int a){
	return 1-a;
}
int  And(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		t=tf.in[i].sp;
	}
	return t;
}
int  Or(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		t=t|f.in[i].sp;
	}
	return t;
}
int  Xor(F f){
	int t=f.in[0].sp;
	int k=f.k;
	for(int i=1;ik;i++){
		if(t!=f.in[i].sp){
			t=1;
		}
		else{
			t=0;
		}
	}
	return t;
}
int  Nand(F f){
	return 1-And(f);
}
int  Nor(F f){
	return 1-Or(f);
}
int find(char s[5]){
	if(s[0]=='A'){
		return 2;
	}
	else{
		if(s[0]=='O'){
			return 3;
		}
		else{
			if(s[0]=='X'){
				return 4;
			}
			else{
				if(s[1]=='A'){
					return 5;
				}
				else{
					if(s[2]=='T'){
						return 1;
					}
					else return 6;
				}
			}
		}
	}
	return 0;
}
int getnum(char s[10]){
	int i=1,num=0;
	while(s[i]!=0){
		num=num*10+s[i]-'0';
		i++;
	}
	return num;
}
int work(F *f){
	int fla[501];
	for(int i=1;i=N;i++){
		fla[i]=0;
	}
	int flag=1,count2,count1=0,ff=0;
	while(flag){
		flag=0;
		ff=0;
		for(int i=1;i=N;i++){
			if(f[i].ready==f[i].kfla[i]==0){
				ff=1;
				int fg=f[i].fg;
				switch (fg){
					case 1:f[i].out=Not(f[i].in[0].sp);break;
					case 2:f[i].out=And(f[i]);break;
					case 3:f[i].out=Or(f[i]);break;
					case 4:f[i].out=Xor(f[i]);break;
					case 5:f[i].out=Nand(f[i]);break;
					case 6:f[i].out=Nor(f[i]);break;
					default:break;
				}
				fla[i]=1;
				for(int ii=1;ii=N;ii++){
					for(int iii=0;iiif[ii].k;iii++){
						if(f[ii].in[iii].in==0f[ii].in[iii].num==i){
							f[ii].in[iii].sp=f[i].out;
							f[ii].ready++;
						}
					}
				} 
			}
		}
		for(int i=1;i=N;i++){
			if(fla[i]==0){
				flag=1;break;
			} 
		} 
		if(ff==0){
			break;
		}
	} 
	if(ff==0){
		return 1;
	}
	else return 0;
}
int main(){
	int in[10000][100];
	int out[500][100];
	int si[10000];
	scanf("%d",Q);
	for(int i=0;iQ;i++){
		F f[501];
		scanf("%d%d",M,N);
		for(int j=1;j=N;j++){
			char s[5];
			int k;
			scanf("%s%d",s,k);
			f[j].k=k;
			f[j].fg=find(s);
			for(int l=0;lk;l++){
				char L[10];
				scanf("%s",L);
				if(L[0]=='I'){
					f[j].in[l].in=1;
				}
				else{
					f[j].in[l].in=0;
				}
				f[j].in[l].num=getnum(L);
			}
		}
		scanf("%d",S);
		for(int i1=0;i1S;i1++){
			for(int j=1;j=M;j++){
				scanf("%d",in[i1][j]);
			}
		}
		for(int i1=0;i1S;i1++){
			scanf("%d",si[i1]);
			for(int j=0;jsi[i1];j++){
				scanf("%d",out[i1][j]);
			}
		}
		int w=0;
		for(int i=0;iS;i++){
			for(int ii=1;ii=N;ii++){
				f[ii].ready=0;
			}
			for(int j=1;j=M;j++){
				for(int ii=1;ii=N;ii++){
					for(int jj=0;jjf[ii].k;jj++){
						if(f[ii].in[jj].in==1f[ii].in[jj].num==j){
							f[ii].in[jj].sp=in[i][j];
							f[ii].ready++;
						}
					}
				}
			}
			w=work(f);
			if(w==1){
				printf("LOOP\n");
				break;
			} 
			else{
				for(int j=0;jsi[i];j++){
					printf("%d ",f[out[i][j]].out);
				}
				printf("\n");
			}
		} 
	}
	return 0;
}


/*
2
2 6
NOR 2 O4 I2
AND 2 O4 O6
XOR 2 O5 O1
NOT 1 O6
NAND 2 O2 O2
AND 2 I1 O3
2
0 0
1 0
3 2 3 4
6 1 2 3 4 5 6
3 5
XOR 2 I1 I2
XOR 2 O1 I3
AND 2 O1 I3
AND 2 I1 I2
OR 2 O3 O4
4
0 1 1
1 0 1
1 1 1
0 0 0
2 5 2
2 5 2
2 5 2
2 5 2

*/
最新回复(0)
/jishu_2FiQu4PZrN983OCwBJ92yGU5y3ZruIWx0e16Hd9_2BgJTQ_3D4794941
8 简首页