SP认证2020_9_3_点亮数字人生

学习

Posted by simplex on April 8, 2021

CSP认证20209_3点亮数字人生

一般拓扑排序,横向对比前后的大模拟,这种题目真是太棒了!

有点后悔没有参加那一次考试,报名了,还是因为自己的懦弱没有去考。

// author: M@
#define m_
//#define _DEBUG_
#include<iostream>
#include<cstdio>
#include<string.h>
#include<iomanip>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<list>
#include<set>
#include<string>
#include<cmath>
//#define clr(a)   memset((a),0,sizeof (a))
//#define li idx<<1
//#define ri idx<<1|1

using namespace std;
typedef unsigned int ui;
typedef long long LL;
typedef pair<int,int> pii;
//const int INF=0x3f3f3f3f;
const int INF = 1e9 + 7;
const LL LINF=1e18;
const double DINF=1e9;
const double EPS=1e-9;

const int maxn= 5e2+ 5;
const int maxm = 5 * maxn;
const int mod = 1000000007;
int n, m, Q, S; 
char str[][10]{"NOT", "AND", "OR", "XOR", "NAND", "NOR"};
class door{
	public :
		vector<int>in;
		int out;
		int op;
}O[maxn + maxm];
int  op[maxn], cnt;
int adj[maxn];
int to[maxn][maxn];
int query[10005][maxm];
int * I;


void apply(door & d){
	switch(d.op){
		case 0:{
			d.out = !(d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			break;
		}
		case 1:{
			d.out = (d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			for(int i = 1; i < d.in.size(); i++){
				d.out &= (d.in[i] < 0 ? I[-d.in[i]] : O[d.in[i]].out);
			}
			break;
		}
		case 2:{
			d.out = (d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			for(int i = 1; i < d.in.size(); i++){
				d.out |= (d.in[i] < 0 ? I[-d.in[i]] : O[d.in[i]].out);
			}
			break;
		}
		case 3:{
			d.out = (d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			for(int i = 1; i < d.in.size(); i++){
				d.out ^= (d.in[i] < 0 ? I[-d.in[i]] : O[d.in[i]].out);
			}
			break;
		}
		case 4:{
			d.out = (d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			for(int i = 1; i < d.in.size(); i++){
				d.out &= (d.in[i] < 0 ? I[-d.in[i]] : O[d.in[i]].out);
			}
			d.out = !d.out;
			break;
		}		
		case 5:{
			d.out = (d.in[0] < 0 ? I[-d.in[0]] : O[d.in[0]].out);
			for(int i = 1; i < d.in.size(); i++){
				d.out |= (d.in[i] < 0 ? I[-d.in[i]] : O[d.in[i]].out);
			}
			d.out = !d.out;
			break;
		}
	}
}



void ini(){
	cnt = 0;
	for(int i = 1; i <= n; i++){
		O[i].in.clear();
		adj[i] = 0;
		for(int j = 1; j <= n; j++){
			to[i][j] = 0;
		}
		
	}
}

void read_in(int idx){
	int k;
	scanf("%d", &k);
	for(int i = 1; i <= k; i++){
		getchar();
		char tc = getchar();
		int j;
		scanf("%d", &j);
		if(tc == 'O'){
			O[idx].in.push_back(j);
			adj[idx] += 1;
			to[j][idx] = 1;
		}
		else O[idx].in.push_back(-j);
	}

	
}

void tuopu(){
	queue<int>que;
	for(int i = 1; i <= n; i++){
		if(!adj[i])que.push(i);
	}
	while(!que.empty()){
		int idx = que.front();
		que.pop();
		op[++cnt] = idx;
		for(int i = 1; i <= n; i++){
			if(to[idx][i]){
				if(--adj[i] == 0)que.push(i);
			}
		}
	}
}


int main()
{
#ifdef m_
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
#endif
	scanf("%d", &Q);
	while(Q--){
		scanf("%d%d", &m, &n);
		ini();
		char temp[10];
		for(int i = 1; i <= n; i++){
			scanf("%s", temp);
			int j = 0;
			for(;;j++)if(!strcmp(temp, str[j]))break;
			O[i].op = j;
			read_in(i);
		}
		tuopu();
		scanf("%d", &S);
		if(cnt != n){
			puts("LOOP");
			S = S * 2 + 1;
			string buf;
			while(S--)
			getline(cin, buf);
			continue;
		}
		for(int i = 1; i <= S; i++){
			for(int j = 1; j <= m ; j++){
				scanf("%d", &query[i][j]);
			}
		}
		for(int i = 1; i <= S; i++){
			I = query[i];
//			printf(" %d %d %d\n", query[i][1], query[i][2], query[i][3]);
			for(int j = 1; j <= cnt; j++)apply(O[op[j]]);
			int ss;scanf("%d", &ss);
			while(ss--){
				int temp;scanf("%d", &temp);
				printf("%d ", O[temp].out);
			}puts("");
		}
	}
	
#ifdef m_
    fclose(stdin);
//    fclose(stdout);
#endif
    return 0;
}

总结:自己是菜,不能硬肛题目,该看题解看题解。