邏輯電路 題解｜APCS 2024 年 1 月中高級 第 3 題

前置知識

這題的核心推導（一個元件要等它的輸入都算好才能算）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

簡潔題意

\(p\) 個輸入端口（編號 \(1 \sim p\)，值 \(0\) 或 \(1\)）、\(q\) 個邏輯閘（編號 \(p + 1 \sim p + q\)；AND、OR、XOR 各接兩條輸入線，NOT 接一條）、\(r\) 個輸出端口（編號 \(p + q + 1 \sim p + q + r\)，各接一條輸入線），\(m\) 條有方向的連接線 \(a \to b\)。電路沒有迴路。求每個輸出端口的值，以及最大延遲：所有「輸入端口到輸出端口」的路徑中，經過邏輯閘數量的最大值（\(p, r \le 10^3\)，\(q \le 5 \times 10^4\)，每個端口或閘的輸出最多接 \(20\) 條線，最大延遲不超過 \(100\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(40\) 分）：\(p + q + r \le 10^3\)。
  • 子題組 2（\(60\) 分）：無額外限制。

每個元件的值與延遲：輸入都算好了才能算

一個邏輯閘的值由它的輸入決定，所以要先算好它的輸入；輸入可能是端口（值直接給），也可能是另一個閘（又要先算它的輸入）。延遲也一樣：到某個閘的最長路徑，就是「它每個輸入的延遲取最大，再加一」（經過它自己）；輸出端口不是閘，延遲照抄它那條輸入線來源的延遲、不加一；輸入端口延遲 \(0\)（圖 1）。

圖 1：範例 1 的電路分成輸入端口、第一層閘、第二層閘、輸出端口，每個元件標值與延遲，最大延遲 2

所以整題只有一個問題：用什麼順序算，才能保證算到一個元件時它的輸入都已經算好。題目沒說編號小的一定在前面——範例 2 就有 \(7 \to 6\) 這條線，閘 \(7\) 得先算。

讀入時每條線 \(a \to b\) 記兩件事：in[b] 裡多一個 \(a\)（算 \(b\) 時要用到的輸入），out[a] 裡多一個 \(b\)（\(a\) 算好要通知誰）。閘的運算用 if 寫就好：AND 是「兩個都是 \(1\)」、OR 是「至少一個是 \(1\)」、XOR 是「兩個不一樣」、NOT 是 \(1 - a\)——NOT 只有一條輸入線，in[u][1] 不存在，別去讀它。

先拿下 40 分：反覆找「輸入都算好」的元件

最直接的做法：一輪一輪來，每一輪從頭掃所有還沒算的閘和輸出端口，找到第一個「所有輸入都算好了」的就算它、結束這一輪。電路沒有迴路，所以只要還有東西沒算，就一定找得到一個可以算的，每一輪至少算完一個。

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

const int MAX_V = 52000;
int p, q, r, m;
int val[MAX_V + 1], typ[MAX_V + 1], delay[MAX_V + 1];
bool done[MAX_V + 1];            // 這個元件的值算好了沒
vector<int> in[MAX_V + 1];       // in[b] = 接進 b 的所有元件

void compute(int u) {            // u 的輸入都算好了，算出 u 的值與延遲
    int a = val[in[u][0]];
    if (u <= p + q) {                                // 邏輯閘
        if (typ[u] == 1) val[u] = (a == 1 && val[in[u][1]] == 1);
        else if (typ[u] == 2) val[u] = (a == 1 || val[in[u][1]] == 1);
        else if (typ[u] == 3) val[u] = (a != val[in[u][1]]);
        else val[u] = 1 - a;                         // NOT 只有一個輸入
        delay[u] = 0;
        for (int x : in[u]) delay[u] = max(delay[u], delay[x]);
        delay[u]++;                                  // 經過這個閘，多一層
    } else {                                         // 輸出端口：照抄，不算延遲
        val[u] = a;
        delay[u] = delay[in[u][0]];
    }
    done[u] = true;
}

int main() {
    cin >> p >> q >> r >> m;
    int total = p + q + r;
    for (int i = 1; i <= p; i++) {
        cin >> val[i];
        done[i] = true;                              // 輸入端口的值是給定的
    }
    for (int i = p + 1; i <= p + q; i++) cin >> typ[i];
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        in[b].push_back(a);
    }
    for (int round = 0; round < q + r; round++) {    // 每一輪找一個「輸入都算好了」的元件
        for (int u = p + 1; u <= total; u++) {
            if (done[u]) continue;
            bool ready = true;
            for (int x : in[u]) {
                if (!done[x]) ready = false;
            }
            if (ready) {
                compute(u);
                break;
            }
        }
    }
    int answer = 0;
    for (int u = p + q + 1; u <= total; u++) answer = max(answer, delay[u]);
    cout << answer << endl;
    for (int u = p + q + 1; u <= total; u++) {
        cout << val[u];
        if (u < total) cout << " ";
    }
    cout << endl;
    return 0;
}

\(q + r\) 輪、每輪最多掃 \(q + r\) 個元件，\(O((q + r)^2)\)：\(p + q + r \le 1000\) 時不到 \(10^6\)，子題組 1 的 \(40\) 分穩穩到手。\(q = 5 \times 10^4\) 時是 \(2.5 \times 10^9\)，編號故意倒著給的測資本站實測 \(3.6\) 秒，超過時限。

從 40 分到 100 分：拓撲排序

慢在每一輪都重頭掃。換個角度：幫每個元件記「還有幾個輸入沒算好」（waiting[u]，讀邊時每條線 \(a \to b\) 讓 waiting[b] 加一）。輸入端口不用等任何人，先全部進佇列；每算好一個元件 \(u\)，就通知 out[u] 裡的每個 \(v\) 「你又少等一個」，waiting[v] 歸零的那一刻把 \(v\) 推進佇列。從佇列拿出來的元件保證輸入都算好了，直接算。這就是拓撲排序：每個元件恰好進出佇列一次、每條線恰好被通知一次。

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

const int MAX_V = 52000;
int p, q, r, m;
int val[MAX_V + 1], typ[MAX_V + 1], delay[MAX_V + 1];
int waiting[MAX_V + 1];          // 還有幾個輸入沒算好
vector<int> in[MAX_V + 1];       // in[b] = 接進 b 的所有元件
vector<int> out[MAX_V + 1];      // out[a] = a 的輸出接到哪些元件

void compute(int u) {            // u 的輸入都算好了，算出 u 的值與延遲
    int a = val[in[u][0]];
    if (u <= p + q) {                                // 邏輯閘
        if (typ[u] == 1) val[u] = (a == 1 && val[in[u][1]] == 1);
        else if (typ[u] == 2) val[u] = (a == 1 || val[in[u][1]] == 1);
        else if (typ[u] == 3) val[u] = (a != val[in[u][1]]);
        else val[u] = 1 - a;                         // NOT 只有一個輸入
        delay[u] = 0;
        for (int x : in[u]) delay[u] = max(delay[u], delay[x]);
        delay[u]++;                                  // 經過這個閘，多一層
    } else {                                         // 輸出端口：照抄，不算延遲
        val[u] = a;
        delay[u] = delay[in[u][0]];
    }
}

int main() {
    cin >> p >> q >> r >> m;
    int total = p + q + r;
    for (int i = 1; i <= p; i++) cin >> val[i];
    for (int i = p + 1; i <= p + q; i++) cin >> typ[i];
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        in[b].push_back(a);
        out[a].push_back(b);
        waiting[b]++;
    }
    queue<int> ready;                                // 輸入都算好、可以處理的元件
    for (int i = 1; i <= p; i++) ready.push(i);      // 輸入端口不用等任何人
    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        if (u > p) compute(u);
        for (int v : out[u]) {                       // 通知下游：你又少等一個輸入
            waiting[v]--;
            if (waiting[v] == 0) ready.push(v);
        }
    }
    int answer = 0;
    for (int u = p + q + 1; u <= total; u++) answer = max(answer, delay[u]);
    cout << answer << endl;
    for (int u = p + q + 1; u <= total; u++) {
        cout << val[u];
        if (u < total) cout << " ";
    }
    cout << endl;
    return 0;
}

\(O(p + q + r + m)\)，\(m\) 最多約 \(2q + r\)，一瞬間。compute() 和 \(40\) 分版一模一樣（只少了 done[u] = true），換掉的只有「決定順序」的那一段。

測過再交：範例的閘都「編號小的在前面」

兩個範例的延遲都來自兩輸入的閘，而且輸出端口都接在閘後面。沒蓋到的：輸出端口直接接輸入端口（延遲 \(0\)）、NOT 閘也算一層延遲、閘的編號順序和計算順序相反、三種兩輸入閘各自的真值，以及最大的 \(q\) 配上故意倒著編號（驗速度）。

輸入 正確輸出 這一筆在測什麼
1 1 2 3／1／4／1 2／1 3／2 4 1／1 0 輸出端口 \(3\) 直接接輸入端口：延遲 \(0\)；經過 NOT 的輸出端口 \(4\) 延遲 \(1\)
2 2 1 5／1 0／1 2／1 4／2 4／4 3／1 3／3 5 2／1 閘 \(3\) 的輸入來自編號比它大的閘 \(4\)：照編號順序算會先算 \(3\)，用到還沒算的 \(4\)
1 5 1 6／1／4 4 4 4 4／1 2／2 3／3 4／4 5／5 6／6 7 5／0 五個 NOT 串成一排：延遲 \(5\)，值翻五次是 \(0\)
2 3 3 9／1 1／3 1 2／1 3／2 3／1 4／2 4／1 5／2 5／3 6／4 7／5 8 1／0 1 1 兩個 \(1\) 進 XOR 是 \(0\)、進 AND 是 \(1\)、進 OR 是 \(1\)
用程式造：\(p = 1000\)、\(q = 50000\)、\(r = 1000\)，\(500\) 條各 \(100\) 個閘的鏈，閘的編號從輸出那一端往回編 100（第二行 \(1000\) 個值，略） 最大延遲 \(100\)；每一輪重頭掃的 \(40\) 分版要掃 \(2.5 \times 10^9\) 次，超時

五筆都親眼看過正確，這題就穩了。

另一種做法：遞迴＋記憶化

「要算 \(u\)，先把它的輸入都算出來」直接寫成遞迴也行：compute(u) 先對 in[u] 裡每個元件呼叫 compute，再算自己；算過的用 done[] 記住，第二次被問到直接回傳。對每個輸出端口呼叫一次就全算完了，每個元件只真正算一次，一樣是 \(O(p + q + r + m)\)。遞迴深度最多是最長路徑的長度，題目保證最大延遲不超過 \(100\)，所以很安全。

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

const int MAX_V = 52000;
int p, q, r, m;
int val[MAX_V + 1], typ[MAX_V + 1], delay[MAX_V + 1];
bool done[MAX_V + 1];
vector<int> in[MAX_V + 1];

void compute(int u) {            // 要知道 u 的值，先把它的輸入都算出來
    if (done[u]) return;         // 算過的直接用，別重算
    for (int x : in[u]) compute(x);
    int a = val[in[u][0]];
    if (u <= p + q) {
        if (typ[u] == 1) val[u] = (a == 1 && val[in[u][1]] == 1);
        else if (typ[u] == 2) val[u] = (a == 1 || val[in[u][1]] == 1);
        else if (typ[u] == 3) val[u] = (a != val[in[u][1]]);
        else val[u] = 1 - a;
        delay[u] = 0;
        for (int x : in[u]) delay[u] = max(delay[u], delay[x]);
        delay[u]++;
    } else {
        val[u] = a;
        delay[u] = delay[in[u][0]];
    }
    done[u] = true;
}

int main() {
    cin >> p >> q >> r >> m;
    int total = p + q + r;
    for (int i = 1; i <= p; i++) {
        cin >> val[i];
        done[i] = true;
    }
    for (int i = p + 1; i <= p + q; i++) cin >> typ[i];
    for (int k = 0; k < m; k++) {
        int a, b;
        cin >> a >> b;
        in[b].push_back(a);
    }
    int answer = 0;
    for (int u = p + q + 1; u <= total; u++) {
        compute(u);
        answer = max(answer, delay[u]);
    }
    cout << answer << endl;
    for (int u = p + q + 1; u <= total; u++) {
        cout << val[u];
        if (u < total) cout << " ";
    }
    cout << endl;
    return 0;
}

兩種做法都是滿分。遞迴版不用 out[] 和 waiting[]，程式更短；佇列版不吃遞迴深度，圖很深的題目（這題保證不深）也不用擔心。

常犯錯誤
  • 輸出端口的延遲也加一：範例 1 印 3、範例 2 印 4——題目說端口不計入。
  • 照編號順序算閘：兩個範例都過（範例 2 的 \(7 \to 6\) 剛好沒影響答案），計分測資掛 \(14\) 筆；自測表第 2 列印 1／0。
  • NOT 閘不算延遲：兩個範例都過，計分測資掛 \(12\) 筆；自測表第 3 列印 0／0。
  • 延遲取輸入的最小值而不是最大值：範例 2 印 2。
  • 邊的方向反了（把 \(a \to b\) 記成 \(b \to a\)）：兩個範例都印 0、所有輸出都是 0。
  • 每一輪重頭掃的 \(40\) 分版硬交：\(q = 5 \times 10^4\) 的測資本站實測 \(3.6\) 秒，超時。