。

时间已经是深夜了#xff0c;尽管实验箱上密密麻麻的连线已经拆装了好几遍#xff0c;小君同学却依旧没能让她的电路正…题目背景

土豪大学的计算机系开了一门数字逻辑电路课第一个实验叫做“点亮数字人生”要用最基础的逻辑元件组装出实际可用的电路。

时间已经是深夜了尽管实验箱上密密麻麻的连线已经拆装了好几遍小君同学却依旧没能让她的电路正常工作。

你能帮助她模拟出电路的功能成功点亮她的数字人生吗

问题描述

本题中你需要实现一个简单的数字逻辑电路模拟器。

如果你已经有了此方面的基础可以直接跳过本节。

在阅读时也可以参照前两个样例的图示和解释这有助于你更好地理解数字逻辑电路的工作原理。

数字逻辑电路是用来传输数字信号也就是二进制信号的电路。

一般来说数字逻辑电路可以分为两大类即组合逻辑combinational

logic电路。

在本题中我们仅关注组合逻辑电路。

这种电路仅由逻辑门logical

gate构成。

一个逻辑门可以理解为一个多输入单输出的函数输入端连接至少一个信号而后经过一定的逻辑运算输出一个信号。

常见的逻辑门包括与AND、或OR、非NOT、异或XOR等均与编程语言中的按位运算是对应的。

将一系列的逻辑门连接起来就能构成具有特定功能的电路。

它的功能可能很简单如一位二进制加法只需要一个异或门也可能极其复杂如除法。

无论复杂程度这类电路的特点是它不维持任何的状态任何时刻输出只与输入有关随输入变化。

真实世界中的逻辑器件由于物理规律的限制存在信号传播延时。

为了简单起见本题中我们模拟的组合逻辑电路不考虑延时一旦输入变化输出立刻跟着变化。

考虑到组合逻辑电路的这一特性设计时不能允许组合环路combinational

loop的存在即某逻辑门的输入经过了一系列器件之后又被连接到了自己的输入端。

真实世界中这种做法将导致电路变得不稳定甚至损坏元器件。

因此你也需要探测可能的环路。

需要注意环路的存在性与逻辑门的具体功能没有任何关系只要连接关系上存在环路电路就无法正常工作。

输入格式

个问题的输入你需要对每个问题进行处理并且按照顺序输出对应的答案。

每一个问题的输入在逻辑上可分为两部分。

第一部分定义了整个电路的结构第二部分定义了输入和输出的要求。

实际上两部分之间没有分隔顺序读入即可。

第一部分

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

第二部分

之间的数字表示在对应的输入下组合逻辑完成计算后需要输出结果的器件编号。

输出格式

本样例只有一个问题它定义的组合逻辑电路结构如下图所示。

其功能是一位全加器即将三个信号相加得到一个两位二进制数。

要求的器件

p3.jpg

这是一个带组合环路的电路因此无法正常工作。

特别地其中最短的环路有以下三条

评测用例规模与约定

BufferedInputStream(System.in));static

int

IOException{st.nextToken();return

(int)st.nval;}static

IOException{st.nextToken();return

st.sval;}static

init(){//初始化Arrays.fill(head,0);Arrays.fill(nops,null);Arrays.fill(ne,0);Arrays.fill(to,0);Arrays.fill(du,0);cnt1;}static

void

v){to[cnt]v;ne[cnt]head[u];head[u]cnt;}public

static

{init();mnextInt();nnextInt();for

(int

uInteger.valueOf(in.substring(1));du[i1];//起始输入点if(tI){add(un,i1);}//其他器件else{add(u,i1);}}Nop

nop

{sign.add(nextInt());}inputs.add(sign);}for

(int

{q.add(nextInt());}ques.add(q);}if(isLoop()false){System.out.println(LOOP);continue;}for

(int

{query(inputs.get(i1),ques.get(i1));}}}static

void

{nops[in].outputinput.get(i-1);}topo();ArrayListInteger

res

{res.add(nops[que].getOut());}for

(int

);}System.out.println();}static

boolean

rudu[];rududu.clone();QueueInteger

qnew

q.poll();//出队visnum;//访问点1for(int

yto[i];rudu[y]--;if(rudu[y]0){q.offer(y);}}}return

visnummn;}static

rudu[];rududu.clone();QueueInteger

qnew

yto[i];rudu[y]--;nops[y].input.add(nops[x].getOut());if(rudu[y]0){q.offer(y);}}}}

class

Nop{//NOT/AND/OR/XOR/NAND/NOR/SUPER(指输入信号节点超级节点)String

type;ListInteger

getOut(){//计算输出端结果if(output!-1)

return

output;if(type.equals(NOT)){return

output;}else