ZeroJudge - m933. 邏輯電路

來源: APCS 2024/01 第三題

這題的解法有很多種，像是拓樸排序 BFS… 這邊就來講一下另一種解法: DFS+DP
雖然不是最快的寫法但也值得大家學習，好處是寫法比較直覺，也比較好debug(? 好像也沒有XD

思路

直接從圖上應該就能看出他的遞迴關係式，於是我們從輸出端一直往回找直到找到根結點再慢慢推回去，推回去的過程中我們把這些節點都存起來，下次遇到時就可以直接拿來用 (有一點 Top-Down DP的感覺)

過程

1. 前置處理/變數宣告/資料讀取
   可以觀察到輸入節點跟邏輯閘的類型不會衝突所以我們可以把他們放在同個陣列。
   再來就是存圖了，我們用鄰接串列的方式使得
   $m{p}_i=p_1..p_2$。
   $p$ 為
   $i$ 的子節點
   然後是檢查該點是否遍歷過的 vis 跟儲存資料的 dp，由於我們還要檢查電路的延遲所以資料型態是雙欄位的 pair。

程式碼如下:

#include <bits/stdc++.h>
using namespace std;

int p, q, r, m;
vector<int> el; // 儲存輸入節點的狀態與邏輯閘類型
vector<bool> vis;
vector<vector<int>> mp;
vector<pair<int, int>> dp;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> p >> q >> r >> m;

    el.assign(p+q+1, 0);
    mp.assign(p+q+r+1, {});
    vis.assign(p+q+r+1, 0);
    dp.resize(p+q+r+1);

    for (int i = 1; i <= p+q; i++)
        cin >> el[i];

    int a, b;
    while (m--){
        cin >> a >> b;
        mp[b].push_back(a);
    }

2. dfs 函式
   首先要設立我們的終止條件
   由於我們最後會遍歷到輸入節點，所以終止條件就是當節點為輸入節點時。
   再來就是操作的部分，如下
   如果當前的節點為輸出節點的話我們就往下遍歷一個節點。
   如果當前的節點屬於邏輯閘時我們就根據相對應的節點數和類型進行操作。
   最後還要記得紀錄邏輯閘數，輸入節點為
   $0$ 推回來的時候就逐步加
   $1$

程式碼如下:

// 狀態, 邏輯閘數 (delay)
pair<int, int> dfs(int idx){
    if (idx <= p){ // 判斷是否為輸入節點
        vis[idx] = 1; 
        return dp[idx] = {el[idx], 0};
    }
        
    if (idx > p+q && idx <= p+q+r) // 判斷是否為輸出節點
        return dfs(mp[idx][0]); // 輸入節點不可能找過所以直接下去搜就好
    
    if (vis[idx]) 
        return dp[idx]; // 如果找過了就直接回傳

    vis[idx] = 1;
    auto x = dfs(mp[idx][0]); // 搜尋第一個子節點

    if (el[idx] == 4) //Not 只有一個輸入所以要先判斷
        return dp[idx] = {!x.first, x.second+1};

    auto y = dfs(mp[idx][1]); // 如果不是 Not 閘的話就再找一個輸入

    if (el[idx] == 1)
        return dp[idx] = {(x.first && y.first), max(x.second, y.second)+1};

    if (el[idx] == 2)
        return dp[idx] = {(x.first || y.first), max(x.second, y.second)+1};

    if (el[idx] == 3)
        return dp[idx] = {(x.first ^ y.first), max(x.second, y.second)+1}; // x.first ^ y.first 等價於 (!x.first && y.first) || (x.first && !y.first)
}

3. 輸出資料
   對每個輸出節點做DFS並將結果存起來，順便檢查最大的延遲數 (邏輯閘)
   之後按照題目要求輸出即可。

程式碼如下:

int delay = INT_MIN;
vector<int> ans;
for (int i = p+q+1; i <= p+q+r; i++){
    auto d = dfs(i);
    ans.push_back(d.first);
    delay = max(delay, d.second);
}

cout << delay << '\n';
for (auto i: ans)
    cout << i << ' ';

完整程式碼

#include <bits/stdc++.h>
using namespace std;

int p, q, r, m;
vector<int> el;
vector<bool> vis;
vector<vector<int>> mp;
vector<pair<int, int>> dp;

pair<int, int> dfs(int idx){
    if (idx <= p){
        vis[idx] = 1;
        return dp[idx] = {el[idx], 0};
    }
        
    if (idx > p+q && idx <= p+q+r)
        return dfs(mp[idx][0]);
    
    if (vis[idx])
        return dp[idx];

    vis[idx] = 1;
    auto x = dfs(mp[idx][0]);

    if (el[idx] == 4)
        return dp[idx] = {!x.first, x.second+1};

    auto y = dfs(mp[idx][1]);

    if (el[idx] == 1)
        return dp[idx] = {(x.first && y.first), max(x.second, y.second)+1};

    if (el[idx] == 2)
        return dp[idx] = {(x.first || y.first), max(x.second, y.second)+1};

    if (el[idx] == 3)
        return dp[idx] = {(x.first ^ y.first), max(x.second, y.second)+1};
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> p >> q >> r >> m;

    el.assign(p+q+1, 0);
    mp.assign(p+q+r+1, {});
    vis.assign(p+q+r+1, 0);
    dp.resize(p+q+r+1);

    for (int i = 1; i <= p+q; i++)
        cin >> el[i];

    int a, b;
    while (m--){
        cin >> a >> b;
        mp[b].push_back(a);
    }

    int delay = INT_MIN;
    vector<int> ans;
    for (int i = p+q+1; i <= p+q+r; i++){
        auto d = dfs(i);
        ans.push_back(d.first);
        delay = max(delay, d.second);
    }

    cout << delay << '\n';
    for (auto i: ans)
        cout << i << ' ';
}

如果內容有誤還麻煩敲我 ><