CSP 202009-3 点亮数字人生练习笔记

写的真累啊！

2021.12.26~12.27 练习CSP 202009-3 点亮数字人生（希望你真的可以点亮我的人生T…T）

解题思路：本题可以抽象为一个有向图，通过拓扑排序判断图中是否存在环路，若存在环路，则输出

“LOOP”

，若不存在环路，利用拓扑排序的结果计算每个器件的输出。

1. 拓扑排序思想：

(1）定义一个队列q，将所有入度为0的结点加入队列。

(2）取出队首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点入度

-1

，如果某个顶点的入度减为0，则将其加入队列。

(3）反复进行(2)操作，直到队列为空。如果队列为空时，曾经入过队列的结点数目正好为

（图中结点总个数），说明拓扑排序成功，图为有向无环图；否则，拓扑排序失败，图中含有环。

基本的拓扑排序代码如下：

int n;//图中点的数目
vector<int> G[MAX_NUM];//邻接表
int indegree[MAX_NUM];//每个点的入度
int toposort()
{
    int num=0;
    queue<int> q;
    for(int i=0;i<n;i++)
    {
        if(indegree[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];//u的后继结点
            indegree[v]--;
            if(indegree[v]==0)
                q.push(v);
        }
        num++;
    }
    if(num==n)
        return 1;//无环
    else
        return 0;//有环
}

2. 门器件的数据结构：

struct DOOR
{
    string FUNC;
    int k;
    vector<int> I;//连接该门的输入信号编号
    vector<int> O;//连接该门的上一个门器件编号
    int outcome;//该门的输出结果
}door[505];

3.怎样记录每个器件的输入？

（包括连接到该器件的输入信号和上一个器件的输出结果）

在这里定义每一个器件的输入为

string

类型，使用

substr()

函数切割字符串，获取输入的第一个字符，判断它是

'I'

还是

'O'

：

string L;
cin>>L;
string I_O_type=L.substr(0,1);//是I还是O

再次利用

substr()

函数获取输入字符串中

I/O

后的数字，即输入信号的编号或连接到该器件的上一个器件的编号。使用

atoi(string.c_str())

方法将获取的数字字符由

string

类型转换为

int

类型。

string L_left=L.substr(1);
int num=atoi(L_left.c_str());

判断器件的输入是

'I'

类型还是

'O'

类型，根据类型的不如，分别使用

push_back()

方式将输入信号编号或连接该门的上一个门器件编号添加到门器件结构中。如果是

'O'

类型，还需要将该门器件编号与连接该门的上一个门器件编号存储到邻接表中。

//num是输入信号的编号或连接到该器件的上一个器件的编号
if(I_O_type=="I")
     door[i].I.push_back(num);
else if(I_O_type=="O")
{
     //tmp是i门的输入门
     G[num].push_back(当前门器件编号);
     door[i].O.push_back(num);
}

本题实现代码：

#include<bits/stdc++.h>
using namespace std;
int Q;
int M,N;
int S;
vector<int> G[505];//邻接表存储图
//门器件的结构
struct DOOR
{
    string FUNC;
    int k;
    vector<int> I;//连接该门的输入信号编号
    vector<int> O;//连接该门的上一个门器件编号
    int outcome;//该门的输出结果
}door[505];
vector<vector<int> >in;//输入描述
vector<vector<int> >out;//输出描述
vector<int> sort_res;//拓扑排序的结果

//判断图是否存在环路
int toposort()
{
    int num=0;//记录加入拓扑序列的顶点数
    queue<int> q;
    int indegree[505];//每个门的入度
    for(int i=1;i<=N;i++)
    {
        indegree[i]=door[i].O.size();
        if(indegree[i]==0)
        {
            q.push(i);
            sort_res.push_back(i);
        }
    }
    while(!q.empty())
    {
        int u=q.front();//队首顶点
        q.pop();//取出队首顶点
        //cout<<"门序号："<<u<<endl;
        //删去所有从队首元素出发的边，并令这些边达到的顶点入度-1
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];//u的后继节点
            //cout<<"后继门序号："<<v<<" ";
            indegree[v]--;
            if(indegree[v]==0)
            {
                q.push(v);
                sort_res.push_back(v);//将节点添加到拓扑排序序列中
            }
        }
        num++;
    }
    if(num==N)
        return 1;
    else
        return 0;
}

int fun(int in_num)
{
    vector<int>::iterator it;
    //直接调用拓扑排序序列
    for(it = sort_res.begin(); it != sort_res.end(); it++)
    {
        int u=*it;
        int res;
        //计算的都是入度为0的门，即它的输入门的结果已知
        //输入门到该门的边已经被删除
        string func=door[u].FUNC;
        if(func=="NOT")
        {
            if(door[u].I.size()==1)
            {
                int tmp=door[u].I[0]-1;
                res=!in[in_num][tmp];
            }
            else if(door[u].O.size()==1)
            {
                int tmp=door[u].O[0];
                res=!door[tmp].outcome;
            }
        }
        else if(func=="AND" || func=="NAND")
        {
            res=1;
            for(int i=0;i<door[u].I.size();i++)
            {
                int tmp=door[u].I[i]-1;//该门连接到的输入信号的编号-1
                res&=in[in_num][tmp];
            }
            for(int i=0;i<door[u].O.size();i++)
            {
                int tmp=door[u].O[i];//该门的输入门的编号
                res&=door[tmp].outcome;
            }
            if(func=="NAND")
            {
                res=!res;
            }
        }
        else  if(func=="OR" || func=="NOR")
        {
            res=0;
            for(int i=0;i<door[u].I.size();i++)
            {
                int tmp=door[u].I[i]-1;//该门连接到的输入信号的编号-1
                res|=in[in_num][tmp];
            }
            for(int i=0;i<door[u].O.size();i++)
            {
                int tmp=door[u].O[i];//该门的输入门的编号
                res|=door[tmp].outcome;
            }
            if(func=="NOR")
            {
                res=!res;
            }
        }
        else if(func=="XOR")
        {
            res=0;
            for(int i=0;i<door[u].I.size();i++)
            {
                int tmp=door[u].I[i]-1;//该门连接到的输入信号的编号-1
                res^=in[in_num][tmp];
            }
            for(int i=0;i<door[u].O.size();i++)
            {
                int tmp=door[u].O[i];//该门的输入门的编号
                res^=door[tmp].outcome;
            }
        }
        door[u].outcome=res;
    }
}
int main()
{
    cin>>Q;
    while(Q--)
    {
        cin>>M>>N;
        for(int i=1;i<=N;i++)
        {
            cin>>door[i].FUNC>>door[i].k;
            /*向每一个门器件的输入描述中添加信息之前，
              将上一次问题中输入到门器件的信息清空！！！
            */
            door[i].I.clear();
            door[i].O.clear();
            for(int j=0;j<door[i].k;j++)
            {
                string L;
                cin>>L;
                string I_O_type=L.substr(0,1);//是I还是O
                string L_left=L.substr(1);
                int tmp=atoi(L_left.c_str());
                if(I_O_type=="I")
                    door[i].I.push_back(tmp);
                else if(I_O_type=="O")
                {
                    //tmp是i门的输入门
                    G[tmp].push_back(i);
                    door[i].O.push_back(tmp);
                }
            }
        }
        cin>>S;
        for(int i=0;i<S;i++)
        {
             vector<int> tmp_in;
             for(int j=0;j<M;j++)
             {
                  int tmp;
                  cin>>tmp;
                  tmp_in.push_back(tmp);
             }
             in.push_back(tmp_in);
             tmp_in.clear();
         }
         for(int i=0;i<S;i++)
         {
              vector<int> tmp_out;
              int s;
              cin>>s;
              for(int j=0;j<s;j++)
              {
                    int tmp;
                    cin>>tmp;
                    tmp_out.push_back(tmp);
              }
              out.push_back(tmp_out);
              tmp_out.clear();
          }
          if(toposort()==0)//有环路
          {
              cout<<"LOOP"<<endl;
          }
          else//无环路
          {
              for(int i=0;i<S;i++)
              {
                  fun(i);//计算每一次输入时不同门器件的结果
                  for(int j=0;j<out[i].size();j++)
                  {
                      int tmp=out[i][j];
                      cout<<door[tmp].outcome<<" ";
                  }
                  cout<<endl;
              }
          }
          /*至此一次问题久已经计算完了，马上要进行下一个问题的计算，
            在下一次计算开始之前，需要将本次计算过程中使用过的数组
            全部清空！！！
          */
          for(int i=1;i<=N;i++)
          {
            G[i].clear();//邻接表清空！
          }
          in.clear();//输入描述清空！
          out.clear();//输出描述清空！
          sort_res.clear();//拓扑排序序列清空！
    }
    return 0;
}

本题实现过程记录：

CSP 202009-3 点亮数字人生练习笔记

1. 第一次10分，错误原因：

所以说这种长一点的代码，复制粘贴的时候一定要小心！！！粘贴过来的内容一定要记得该改的都得改了！！！这个10分怎么错的呢？写

if(func=="OR" || func=="NOR")

情况的时候，

if

括号里的内容我是从

if(func=="AND" || func=="NAND")

情况里复制粘贴过来的（反正也都差不多嘛我想着，只用把或的

'|='

换成与的

'&='

就好了）然而，我大错特错了，大姐，要改就改完好吧，改了

或

和

与

，您把

或非

和

与非

也改改啊！！！！！！！然而我把

if(func=="AND" || func=="NAND")

情况里的

if(func=="NAND")

也复制到了

if(func=="OR" || func=="NOR")

里 (°ー°〃)，于是就出现了下面的情况：

if(func=="OR" || func=="NOR")
{
     balabala一堆~~~
    if(func=="NAND")
    {
         ？if(func=="OR" || func=="NOR")里面冒出个if(func=="NAND")
         人才说的可不就是你吗？……
    }
}

交上去出来10分之后，回去代码里找错发现错在这里，我直接= _ =||，这都搞错，大姐，你不拿10分谁拿10分？？？！！！

2. 第二次20分，错误原因：

把上一个愚蠢的错改完，再次提交，好家伙,20分， (°ー°〃)，错在哪里呢？找不出来，崩溃崩溃崩溃崩溃……，崩溃完了，调试代码，然后就千辛万苦的发现了：为什么是20分呢，因为前两种情况只有一个问题，当出现多个问题时

(Q>1)

，我就拿不到分了，后面80分错哪了呢？我首先想到的时邻接表没有更新，于是我在每一个问题完成后，把邻接表清空，再次运行调试，还是出错，(°ー°〃)，但愚蠢的我只想到了清空邻接表，以为清空了就没事了，所有清空邻接表后代码还是错我就又很烦，不知道哪错了，（啊喂！你想到了清空邻接表你怎么不想想清空别的数组呢？！），然而我就是没想到，又回到拓扑排序一点点调试输出，终于发现了：

in

数组和

out

数组没清空，那就清空吧，再运行，又错，继续改！哪错了？= _ =|| 门器件结构里的

数组和

数组没清空。OK，清空完了，提交题目，100分……累啊……

总结：刷题不够，解题思维不系统不规范，继续努力 ……(°ー°〃)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int m,n;

struct Node
{
    int id;
    vector<int> in;
    vector<int> out;
    string type;
    int outcome;
}node[510];

vector<int> input[10010];
vector<int> output[10010];
vector<int> g[510];
int indegree[510];
vector<int> travel;

bool topo()
{
    int num=0;
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(indegree[i]==0)
        {
            q.push(i);
            travel.push_back(i);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            indegree[v]--;
            if(indegree[v]==0)
            {
                q.push(v);
                travel.push_back(v);
            }
        }
        num++;
    }
    if(num==n) return true;
    return false;
}

void fun(vector<int> v)
{
    for(int i=0;i<travel.size();i++)
    {
        int cur=travel[i];
        if(node[cur].type=="NOT")
        {
            if(node[cur].in.size()==1)
            {
                int tmp=node[cur].in[0];
                node[cur].outcome=1-v[tmp];
            }
            else if(node[cur].out.size()==1)
            {
                int tmp=node[cur].out[0];
                node[cur].outcome=1-node[tmp].outcome;
            }
        }
        else if(node[cur].type=="AND" || node[cur].type=="NAND")
        {
            int res=1;
            for(int j=0;j<node[cur].in.size();j++)
            {
                int tmp=node[cur].in[j];
                res&=v[tmp];
            }
            for(int j=0;j<node[cur].out.size();j++)
            {
                int tmp=node[cur].out[j];
                res&=node[tmp].outcome;
            }
            node[cur].outcome=res;
            if(node[cur].type=="NAND") node[cur].outcome=1-node[cur].outcome;
        }
        else if(node[cur].type=="OR" || node[cur].type=="NOR")
        {
            int res=0;
            for(int j=0;j<node[cur].in.size();j++)
            {
                int tmp=node[cur].in[j];
                res|=v[tmp];
            }
            for(int j=0;j<node[cur].out.size();j++)
            {
                int tmp=node[cur].out[j];
                res|=node[tmp].outcome;
            }
            node[cur].outcome=res;
            if(node[cur].type=="NOR") node[cur].outcome=1-node[cur].outcome;
        }
        else if(node[cur].type=="XOR")
        {
            int res=0;
            for(int j=0;j<node[cur].in.size();j++)
            {
                int tmp=node[cur].in[j];
                res^=v[tmp];
            }
            for(int j=0;j<node[cur].out.size();j++)
            {
                int tmp=node[cur].out[j];
                res^=node[tmp].outcome;
            }
            node[cur].outcome=res;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int Q; cin>>Q;
    while(Q--)
    {
        travel.clear();
        memset(indegree,0,sizeof(indegree));
        for(int i=0;i<10010;i++) input[i].clear();
        for(int i=0;i<10010;i++) output[i].clear();
        for(int i=0;i<510;i++) g[i].clear();
        for(int i=0;i<510;i++)
        {
            node[i].id=0;
            node[i].type="";
            node[i].in.clear();
            node[i].out.clear();
            node[i].outcome=-1;
        }
        cin>>m>>n;
        for(int i=1;i<=n;i++)
        {
            string func; cin>>func;
            int k; cin>>k;
            node[i].id=i;
            node[i].type=func;
            string IO;
            while(k--)
            {
                cin>>IO;
                string t=IO.substr(1);
                int num=atoi(t.c_str());
                if(IO[0]=='I')
                {
                    node[i].in.push_back(num);
                }
                else if(IO[0]=='O')
                {
                    node[i].out.push_back(num);
                    g[num].push_back(i);
                    indegree[i]++;
                }
            }
        }
        int s; cin>>s;
        for(int i=0;i<s;i++)
        {
            input[i].push_back(-1);
            for(int j=1;j<=m;j++)
            {
                int tmp; cin>>tmp;
                input[i].push_back(tmp);
            }
        }
        //输出
        for(int i=0;i<s;i++)
        {
            int si; cin>>si;
            while(si--)
            {
                int tmp; cin>>tmp;
                output[i].push_back(tmp);
            }
        }
        bool flag=topo();
        if(flag==false)   cout<<"LOOP"<<endl;
        else
        {
            for(int i=0;i<s;i++)
            {
                fun(input[i]);
                for(int j=0;j<output[i].size();j++)
                {
                    int tmp=output[i][j];
                    cout<<node[tmp].outcome<<" ";
                }
                cout<<endl;
            }
        }

    }
    return 0;
}

CSP 202009-3 点亮数字人生练习笔记

继续阅读

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

【数据结构】医院选址

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器