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;
}
总结:自己是菜,不能硬肛题目,该看题解看题解。