CCF小白刷题之路---202009-3 点亮数字人生（C/C++ 100分）

1.题目描述

2.解题思路 2.1 分析题目的样例输入1

1---------------解决问题的数目，此处为一个问题
3 5-------------电路输入与器件数目，此处为3个input和5个器件
XOR 2 I1 I2-----第一个器件XOR，两个输入I1和I2，该器件输出为O1
XOR 2 O1 I3-----第二个器件XOR，两个输入O1和I3，该器件输出为O2
AND 2 O1 I3-----第三个器件AND，两个输入O1和I3，该器件输出为O3
AND 2 I1 I2-----第四个器件AND，两个输入I1和I2，该器件输出为O4
OR 2 O3 O4------第五个器件OR，两个输入O3和O4，该器件输出为O5
4---------------独立子问题个数，此处为四个子问题
0 1 1-----------第一个子问题，I1=0，I2=1，I3=1
1 0 1-----------第二个子问题，I1=1，I2=0，I3=1
1 1 1-----------第三个子问题，I1=1，I2=1，I3=1
0 0 0-----------第四个子问题，I1=0，I2=0，I3=0
2 5 2-----------第一个子问题输出两个结果，O5和O2
2 5 2-----------第二个子问题输出两个结果，O5和O2
2 5 2-----------第三个子问题输出两个结果，O5和O2
2 5 2-----------第四个子问题输出两个结果，O5和O2

2.2基本解题思想

(1)首先要对输入分析得足够透彻，以便在编写代码的时候能用合适的数据结构去进行存储，以及后续可以构建电路图和求解问题。

(2)本题的第一个难点，如何去构建电路图，我的想法是用一个层级的思想，以及给每一个器件一个标识符，标识该器件目前有没有构建，避免后续由于某个器件的输出是另一个器件的输入，但是这个器件还没有构建的情况出现。

(3)层级是为了区分电路图中各器件之间的前后关系，如果输入端是I开头的，则这个输入端层级为0，如果这个输入端是O开头的，则这个输入端层级为O对应的器件层级+1，然后多个输入端的层级取最大值即为该器件的层级，下面举个例子让大家来理解是如何定义层级的。

设层级F(x),x为第几个器件
1：XOR 2 I1 I2---第一个器件，两个输入都为I开头，则F(1)=0
2：XOR 2 O1 I3---第二个器件，两个输入为O和I，则F(2)=max(F(1)+1,0)=1
3：AND 2 O1 I3---第三个器件，两个输入为O和I，则F(3)=max(F(1)+1,0)=1
4：AND 2 I1 I2---第四个器件，两个输入都为I开头，则F(4)=0
5：OR 2 O3 O4----第五个器件，两个输入都为O开头，则F(5)=max(F(3)+1,F(4)+1)=2
所以在电路图中，会优先执1和4，再执行2和3，最后执行5

(5)本题的第二个难点，如何判断出现环路，这里可以借助层级来判断，每执行一个器件，我们就计算一次各器件的层级，并与前一个状态进行相比，正常情况下每个状态的层级应该是不同的，如果两个状态的每个器件的层级都相同，就说明这个电路图中有环路。

(6)本题的易错点，在于输入的I和O，大家要注意，题目中的I和O后面是一位数，并不代表样例就是这样，也会有I11、O12之类的，这个易错点要注意一下。

本题也可以用拓扑排序解决，详见->拓扑排序

3.代码实现

#include
#include
#include
#include
#include
#include
using namespace std;
//结构体---逻辑器件
struct device
{
    int id; //序号
    int level; //层级
    int output; //该器件输出
    string type; //器件类型
    bool ct; //是否构造好该器件
    vector input; //器件输入
    vector id_flag;//标识
    vector input_s;//输入字符串
    //初始化
    device()
    {
        level = -1;
        ct = false;
    }
    //每个器件的运算
    compute()
    {
        int result = input[0];
        if(type=="NOT") result=!input[0];
		else if(type=="AND")
        {
            for(int i=1;idce[j].type>>in_size; //器件类型及其输入的个数
            for(int k=0;k>i_o;
                dce[j].id_flag.push_back(0);
                dce[j].input_s.push_back(i_o);
            }
        }
        //存储输入的第二部分---测试器件
        int test_num;
        cin>>test_num;
        int test_input[test_num][in_num];
        for(int i=0;itest_input[i][j];
            }
        }
        vector test_output[test_num]; //题目要的器件输出
        for(int i=0;i>test_output_num;
            for(int j=0;j>op_num_id;
                test_output[i].push_back(op_num_id);
            }
        }
        //开始构建电路
        bool loop = 0; //判断是否成环
        int run_num = 0; //记录已经搭建好的器件数量
        int pre_level[d_num];
        while(1)
        {
            run_num = 0;
            for(int i=0;i