CCF CSP 点亮数字人生(记忆化搜索+拓扑排序判环)

题目背景

土豪大学的计算机系开了一门数字逻辑电路课，第一个实验叫做“点亮数字人生”，要用最基础的逻辑元件组装出实际可用的电路。时间已经是深夜了，尽管实验箱上密密麻麻的连线已经拆装了好几遍，小君同学却依旧没能让她的电路正常工作。你能帮助她模拟出电路的功能，成功点亮她的数字人生吗？

问题描述

本题中，你需要实现一个简单的数字逻辑电路模拟器。如果你已经有了此方面的基础，可以直接跳过本节。在阅读时，也可以参照前两个样例的图示和解释，这有助于你更好地理解数字逻辑电路的工作原理。

数字逻辑电路是用来传输数字信号（也就是二进制信号）的电路。一般来说，数字逻辑电路可以分为两大类，即组合逻辑（combinational logic）电路和时序逻辑（sequential logic）电路。在本题中，我们仅关注组合逻辑电路。这种电路仅由逻辑门（logical gate）构成。一个逻辑门可以理解为一个多输入单输出的函数，输入端连接至少一个信号，而后经过一定的逻辑运算输出一个信号。常见的逻辑门包括与（AND）、或（OR）、非（NOT）、异或（XOR）等，均与编程语言中的按位运算是对应的。

将一系列的逻辑门连接起来，就能构成具有特定功能的电路。它的功能可能很简单（如一位二进制加法只需要一个异或门），也可能极其复杂（如除法）。无论复杂程度，这类电路的特点是：它不维持任何的状态，任何时刻输出只与输入有关，随输入变化。真实世界中的逻辑器件由于物理规律的限制，存在信号传播延时。为了简单起见，本题中我们模拟的组合逻辑电路不考虑延时：一旦输入变化，输出立刻跟着变化。

考虑到组合逻辑电路的这一特性，设计时不能允许组合环路（combinational loop）的存在，即某逻辑门的输入经过了一系列器件之后又被连接到了自己的输入端。真实世界中，这种做法将导致电路变得不稳定，甚至损坏元器件。因此，你也需要探测可能的环路。需要注意，环路的存在性与逻辑门的具体功能没有任何关系；只要连接关系上存在环路，电路就无法正常工作。

输入格式

输入数据包括若干个独立的问题，第一行一个整数$Q$，满足 $1$$\le$$Q$ $\le$$Q_{max}$。接下来依次是这 个问题的输入，你需要对每个问题进行处理，并且按照顺序输出对应的答案。

每一个问题的输入在逻辑上可分为两部分。第一部分定义了整个电路的结构，第二部分定义了输入和输出的要求。实际上两部分之间没有分隔，顺序读入即可。

第一部分

第一行是两个空格分隔的整数$M,N$，分别表示了整个电路的输入和器件的数量，满足 $1\le N\le N_{max}$并且$0\le M\le k_{max}N$ 。其中 $k_{max}$和 $N_{max}$都是与测试点编号有关的参数。

接下来 行，每行描述一个器件，编号从 1 开始递增，格式如下：

FUNC k L_1 L_2 ... L_k

其中 FUNC 代表具体的逻辑功能， 表示输入的数量，后面跟着该器件的 个输入端描述 ，格式是以下二者之一：

Im：表示第 m 个输入信号连接到此输入端，保证$1$$\le$$m$$\le$$M$ On：表示第 n 个器件的输出连接到此输入端，保证$1$$\le$$n$$\le$$N$ 所有可能的 FUNC 和允许的输入端数量如下表所述：

所有的器件均只有一个输出，但这个输出信号可以被用作多个器件的输入。

第二部分

第一行是一个整数$S$，表示此电路需要运行$S$次。每次运行，都会给定一组输入，并检查部分器件的输出是否正确。 满足$1\le S\le S_{max}$，其中 $S_{max}$是一个与测试点编号有关的参数。

接下来的 行为输入描述，每一行的格式如下：

I_1 I_2 … I_M

每行有 $M$个可能为 0 或 1 的数字，表示各个输入信号（按编号排列）的状态。

接下来的 $S$行为输出描述，每一行的格式如下：

s_i O_1 O_2 … O_s 第一个整数 $1\le si\le N$表示需要输出的信号数量。后面共有 $s_i$个在 $1$到 $N$之间的数字，表示在对应的输入下，组合逻辑完成计算后，需要输出结果的器件编号。

注意 $O$序列不一定是递增的，即要求输出的器件可能以任意顺序出现。

输出格式

对于输入中的 $Q$个问题，你需要按照输入顺序输出每一个问题的答案：

如果你检测到电路中存在组合环路，则请输出一行，内容是 LOOP，无需输出其他任何内容。

如果电路可以正常工作，则请输出$S$行，每一行包含$s_i$个用空格分隔的数字（可能为 0 或 1），依次表示“输出描述”中要求的各个器件的运算结果。

样例输入1

1 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

样例输出1

1 0 1 0 1 1 0 0

#include<bits/stdc++.h> using namespace std; const int N=1e4+5; struct Node{ int opt; vector<int>In; vector<int>Out; }Dev[505]; int Input[N][505],Ind[505],ans[505]; vector<int>e[505]; int getNum(int pos,char *str){ int num=0; int len=strlen(str); while(pos<len){ num=num*10+str[pos]-'0'; ++pos; } return num; } int Operation(vector<int>q,int opt){ if(opt==0) return !q[0]; else{ int cnt=q.size(); int r=q[0]; if(opt==1){ for(int i=1;i<cnt;++i) r&=q[i]; return r; } else if(opt==2){ for(int i=1;i<cnt;++i) r|=q[i]; return r; } else if(opt==3){ for(int i=1;i<cnt;++i) r^=q[i]; return r; } else if(opt==4){ for(int i=1;i<cnt;++i) r&=q[i]; return !r; } for(int i=1;i<cnt;++i) r|=q[i]; return !r; } } int dfs(int s,int u){ if(ans[u]!=-1) return ans[u]; int cnt=Dev[u].In.size(); vector<int>t; for(int i=0;i<cnt;++i){ t.push_back(Input[s][Dev[u].In[i]]); } cnt=Dev[u].Out.size(); for(int i=0;i<cnt;++i){ t.push_back(dfs(s,Dev[u].Out[i])); } return ans[u]=Operation(t,Dev[u].opt); } bool topolog(int n){ queue<int>Q; for(int i=1;i<=n;++i){ if(!Ind[i]) Q.push(i); } int cnt=0; while(!Q.empty()){ int u=Q.front(); Q.pop(); ++cnt; int cnt=e[u].size(); for(int i=0;i<cnt;++i){ int v=e[u][i]; if(!(--Ind[v])) Q.push(v); } } return cnt==n; } int main(){ map<string,int>Mp; Mp["NOT"]=0;Mp["AND"]=1;Mp["OR"]=2;Mp["XOR"]=3;Mp["NAND"]=4;Mp["NOR"]=5; char str[10]; int Q;scanf("%d",&Q); while(Q--){ int m,n;scanf("%d%d",&m,&n); //电路和器件数量 for(int i=1;i<=n;++i){ e[i].clear(); Ind[i]=0; Dev[i].In.clear(); Dev[i].Out.clear(); } for(int i=1;i<=n;++i){ //每个器件 scanf("%s",str); Dev[i].opt=Mp[str]; int k;scanf("%d",&k); for(int j=0;j<k;++j){ scanf("%s",str); int num=getNum(1,str); if(str[0]=='I') Dev[i].In.push_back(num); else{ e[num].push_back(i); Ind[i]++; Dev[i].Out.push_back(num); } } } int S;scanf("%d",&S); for(int i=0;i<S;++i){ for(int j=1;j<=m;++j) scanf("%d",&Input[i][j]); } bool fg=topolog(n); if(!fg) puts("LOOP"); for(int i=0;i<S;++i){ int s,num;scanf("%d",&s); memset(ans,-1,sizeof(ans)); for(int j=0;j<s;++j){ scanf("%d",&num); if(fg) printf("%d%c",dfs(i,num),j==s-1?'\n':' '); } } } return 0; }