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<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<sstream>
#include<map>
using namespace std;
//结构体---逻辑器件
struct device
{
    int id; //序号
    int level; //层级
    int output; //该器件输出
    string type; //器件类型
    bool ct; //是否构造好该器件
    vector<int> input; //器件输入
    vector<int> id_flag;//标识
    vector<string> 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;i<input.size();i++)
            {
                result &= input[i];
            }
        }
        else if(type=="OR")
        {
            for(int i=1;i<input.size();i++)
            {
                result |= input[i];
            }
        }
        else if(type=="XOR")
        {
            for(int i=1;i<input.size();i++)
            {
                result ^= input[i];
            }
        }
        else if(type=="NAND")
        {
            for(int i=1;i<input.size();i++)
            {
                result &= input[i];
            }
            result = !result;
        }
        else
        {
            for(int i=1;i<input.size();i++)
            {
                result |= input[i];
            }
            result = !result;
        }
        output = result;
    }
};
//string to int
int str_to_int(string s)
{
    int result;
    string str = s.substr(1); //截取I/O后面的数字字符串
    stringstream ss;
    ss << str;
    ss >> result;
    return result;
}
//sort函数的cmp，定义器件层级由小到大排列
bool cmp(device d1,device d2)
{
    return d1.level < d2.level;
}

int main()
{
    int qt_num; //问题数量
    cin>>qt_num;
    for(int i=0;i<qt_num;i++)
    {
        //存储输入的第一部分---器件构造
        int in_num,d_num; //输入数量、输出/器件数量
        cin>>in_num>>d_num;
        device dce[d_num];
        for(int j=0;j<d_num;j++)
        {
            int in_size;
            dce[j].id = j + 1;
            cin>>dce[j].type>>in_size; //器件类型及其输入的个数
            for(int k=0;k<in_size;k++)
            {
                string i_o;
                cin>>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;i<test_num;i++)
        {
            for(int j=0;j<in_num;j++)
            {
                cin>>test_input[i][j];
            }
        }
        vector<int> test_output[test_num]; //题目要的器件输出
        for(int i=0;i<test_num;i++)
        {
            int test_output_num;
            cin>>test_output_num;
            for(int j=0;j<test_output_num;j++)
            {
                int op_num_id;
                cin>>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<d_num;i++)
            {
                pre_level[i] = dce[i].level;
            }
            for(int i=0;i<d_num;i++)
            {
                if(!dce[i].ct)//未被建造
                {
                    run_num++;
                    for(int j=0;j<dce[i].input_s.size();j++)
                    {
                        int run_level;
                        if(!dce[i].id_flag[j])//未访问I/O
                        {
                            if(dce[i].input_s[j][0]=='I')
                            {
                                run_level = 0;//输入端为0级
                                dce[i].id_flag[j] = 1;
                            }
                            else if(dce[i].input_s[j][0]=='O')
                            {//O必须之前建造过才能进行访问
                                if(dce[str_to_int(dce[i].input_s[j])-1].ct)
                                {
                                    dce[i].id_flag[j] = 1;
                                    run_level = dce[str_to_int(dce[i].input_s[j])-1].level + 1;
                                }
                            }
                            if(run_level > dce[i].level)//level大进行层级更新
                            {
                                dce[i].level = run_level;
                            }
                        }
                    }
                    for(int j=0;j<dce[i].id_flag.size();j++)
                    {
                        //查找有无未访问I/O
                        if(!dce[i].id_flag[j]) break;
                        //标识该器件已被建造
                        if(j==dce[i].id_flag.size()-1) dce[i].ct = true;
                    }
                }
            }
            //判断电路是否成环
            if(run_num==0) break;
            int same_num = 0;
            for(int i=0;i<d_num;i++)
            {
                if(pre_level[i]==dce[i].level) same_num++;//每执行一次各器件层级应该会发生变化，
            }                                             //没有变化说明电路存在环
            if(same_num==d_num)
            {
                loop = true;
                break;
            }
        }
        //开始进行测试
        if(loop) cout<<"LOOP"<<endl;
        else
        {
            sort(dce,dce+d_num,cmp);//按层级大小排序
            for(int i=0;i<test_num;i++)
            {
                map<int,int> opt;
                for(int j=0;j<d_num;j++)
                {
                    for(int k=0;k<dce[j].input_s.size();k++)
                    {
                        if(dce[j].input_s[k][0]=='I')//去test_input里面找对应的输入
                            dce[j].input.push_back(test_input[i][str_to_int(dce[j].input_s[k])-1]);
                        else if(dce[j].input_s[k][0]=='O')//去output里面找对应的输出
                            dce[j].input.push_back(opt[str_to_int(dce[j].input_s[k])]);
                    }
                    //开始计算
                    dce[j].compute();
                    opt[dce[j].id] = dce[j].output;
                }
                for(int j=0;j<test_output[i].size();j++)
                {
                    cout<<opt[test_output[i][j]]<<" ";
                }
                cout<<endl;
                //释放资源
                opt.clear();
                for(int j=0;j<d_num;j++)
                {
                    dce[j].input.clear();
                }
            }
        }
    }
    return 0;
}