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裝置模型（中）之上層容器