# APCS 2024 一月份題解
簡評：APCS 終於不像以前一樣毒瘤了，至少實作不出毒瘤遞迴題。
相對來說一定會出一題圖論 + DP，平常實作練習和演算法的觀念就很重要。
事後補題上去 APCS 盡量都是一次 AC，對應到 APCS 是後測，加油！

## [P1 遊戲選角](https://zerojudge.tw/ShowProblem?problemid=m931)
### Subtask 1: $n = 3$
老哏了，n = 3 的情況下不需要迴圈，列舉每一種狀況判斷。

程式能力需求：`I/O` `變數` `條件式`

### Subtask 2: 無其他限制
n 不是固定的，因此我們需要迴圈讀入每個角色的攻擊以及防禦力。
使用幾個變數記錄已經讀入角色的：最大的能力值、次大的能力值、最大的攻擊防禦、次大的攻擊防禦。輸入時計算這個角色的能力值，並考慮這個值對當前的幾個變數造成的影響，分為以下的請況處理：
1. 當前的能力值 >= 最大的能力值
2. 最大的能力值 > 當前的能力值 >= 次大的能力值

對於第一種情況，你會發現我們不只要更新最大的能力值（及相關數值），也要將次大的能力值設成原本最大的能力值。
對於第二種情況，我們僅僅需要更新第二大的能力值。
於是，在迴圈跑完後，我們就有了全部角色的次大攻擊、防禦力，將它輸出就好了。

程式能力需求：`I/O` `變數` `迴圈` `條件式`

#### 參考題解

#include <iostream>
using std::cin;
using std::cout;

int main() {
    int n;
    cin >> n;
    int atk, def, max = -1, max2 = -1, max_atk, max_def, max2_atk, max2_def;
    for (int i = 0; i < n; i++) {
        cin >> atk >> def;

        int cur_ability = atk * atk + def * def;
        if (cur_ability >= max) {
            max2 = max;
            max2_atk = max_atk;
            max2_def = max_def;

            max = cur_ability;
            max_atk = atk;
            max_def = def;
        }
        else if (cur_ability >= max2) {
            max2 = cur_ability;
            max2_atk = atk;
            max2_def = def;
        }
    }

    cout << max2_atk << " " << max2_def;
}

## [P2 蜜蜂觀察](https://zerojudge.tw/ShowProblem?problemid=m932)

### Subtask 1: $m = 2$
因為只有兩層，你可以用一個變數記錄當前你在上層還是下層，之後就可以將移動分類，判斷一下邊界然後就可以決定移動到上層或下層了...不過我很好奇會不會有人只過這個 Subtask 就是。

### Subtask 2: 無其他限制
它看起來就一臉可以變成長方形棋盤樣子的，對吧？
所以，我們變形一下：

 5 0     5 0
4 X 1 => 4 X 1
 3 2       3 2

於是，我們就可以將測資直接當成長方形棋盤來看了。
這樣我們要怎麼在棋盤上表示六個方向也很顯然了：

0: {0, -1}
1: {1, 0}
2: {1, 1}
3: {0, 1}
4: {-1, 0}
5: {-1, -1}

其中向右為正，向下為正。
於是，我們用一個座標表示當前位置，每輸入一個移動方向，就判斷是否到達邊界，如果沒有就走過去並輸出該格的字母。

接著我們看看如何統計字母。
因為要統計「不重複」的字母數，第一個直覺可能會想到使用 set。我個人認為用 set 很快、很方便，但是怕社內有人對 set 的操作不熟，我寫一個我預設的解法。
我們知道 C++ 中的字元都依照 ASCII 碼對應到一個整數，因此我們可以利用這個整數來當作陣列的索引值：開一個大小為 128（或256，看你開心）的 bool 陣列，預設為 0，如果有用到某個字母就將對應的格子設為 1，最後跑過整個陣列，統計 1 出現的次數。
舉個例子，字串 "aabbcc"，其中 'a' = 97, 'b' = 98, 'c' = 99
bool 陣列應該會儲存：

index  0  1  2  3  4 ... 97 98 99 ...
 data  0  0  0  0  0 ...  1  1  1 ...

這樣整個陣列應該只會出現三次 1，對應到分別出現過 'a', 'b', 'c' 三種字母。

實作特別需要注意的幾點：
1. 由左下角開始
2. m, n 的順序
3. 邊界條件

程式能力需求：`I/O` `變數` `迴圈` `條件式` `陣列` `模擬`

#### 參考題解

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::string;
using std::vector;

const int dx[] = {0, 1, 1, 0, -1, -1};
const int dy[] = {-1, 0, 1, 1, 0, -1};

int main() {
    vector<string> hive;
    int m, n, k;
    cin >> m >> n >> k;
    hive.resize(m);

    for (int i = 0; i < m; i++)
        cin >> hive[i];

    int x = 0, y = m - 1;           // 預設在左下角
    int dirc;                       // 方向
    string path(k, ' ');            // 路徑
    vector<bool> alphabet(128, 0);  // 字母表，統計字母用幾次

    for (int i = 0; i < k; i++) {
        cin >> dirc;
        int ax = x + dx[dirc], ay = y + dy[dirc];       // 移動完後應該會在哪
        if (!(ax < 0 || ay < 0 || ax >= n || ay >= m))  // 如果沒有超出範圍
            x = ax, y = ay;                             // 移動
        path[i] = hive[y][x];                           // 將路徑記錄到結果
        alphabet[hive[y][x]] = 1;                       // 將該格路徑的字母記錄下來
    }

    cout << path << "\n";

    int cnt = 0;
    for (int i = 0; i < 128; i++)
        if (alphabet[i]) cnt++;

    cout << cnt;
}

## [P3 邏輯電路](https://zerojudge.tw/ShowProblem?problemid=m933)
### Subtask 1: $p + q + r \leq 10 ^ 3$
p, q, r 很小，暴力做也會過
用個迴圈模擬每次訊號傳遞一格，跑過 k 次以後如果輸出全滿了就結束。
複雜度 $O(mk)$？或許吧。

程式能力需求：`模擬` `暴力`

### Subtask 2: 無其他限制
看看那個圖，看看那個輸入方式，很顯然這是一題圖論題。
並且，對應到電流的方向，這題的圖是有向圖。
於是，我們將輸入端、邏輯閘、輸出端視為點，中間的電路視為邊，依照電流方向建圖。
接著我們有兩種想法：

首先，你可能會注意到電流有一種整體的方向性，也就是由輸入端流向輸出端。因此，如果想依照輸入輸出順序處理那些邏輯閘，你可以考慮將整張圖拓撲排序。拓撲排序以後就好辦了，從輩分大的一路處理到輩分小的，可以保證在處理後面的閘時前面的輸入已經確定了。

這題如果用拓撲排序做可以建反圖（邊的方向是反的），然後因為 DFS 的離開順序就是拓撲排序的順序，所以直接在 DFS 離開的時候更新就可以了。
為什麼呢？我們希望從輩分大更新到輩分小，但同時我們希望保有 DFS 易於操作的特性。對於 DFS 做法來說，是從輩分較小的會先被處理到（先離開），如果我們建反圖輩分大小會反過來，這樣就是從輩分大做到輩分小了。
實作時，我們在每個閘裡記錄它的結果以及它的延遲，這樣回到上一個節點時就可以利用附近的節點資料更新它本身的資料。複雜度 $O(p + q + r + m)$

程式能力需求：`圖論` `拓撲排序 / DFS`
#### 參考題解 by 拓撲排序

#include <functional>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int OUTPUT = 0, AND = 1, OR = 2, XOR = 3, NOT = 4, INPUT = 5;

bool operate(bool A, bool B, int type) {
    if (type == AND) return A && B;
    if (type == OR) return A || B;
    if (type == XOR) return A != B;
    if (type == NOT) return !A;
    return A;
}

struct gate {
    bool current;
    int type = 0;
    int time = 0;
    int inputA = -1, inputB = -1;  // 接向此閘的兩個輸入端
    bool visited = false;
};

vector<gate> graph;

void dfs(int cur) {
    if (graph[cur].type == INPUT) return;

    int A = graph[cur].inputA, B = graph[cur].inputB;
    for (int nxt : {A, B})  // : 運算子代表第一輪 nxt = A, 第二輪 nxt = B
        if (!graph[nxt].visited && nxt != -1)
            graph[nxt].visited = true, dfs(nxt);

    graph[cur].time = max(graph[A].time + 1, graph[B].time + 1);
    graph[cur].current = operate(graph[A].current, graph[B].current, graph[cur].type);
}

int main() {
    int p, q, r, m;
    cin >> p >> q >> r >> m;

    graph.resize(p + q + r);

    for (int i = 0; i < p; i++) {
        graph[i].type = INPUT;
        cin >> graph[i].current;
    }

    for (int i = p; i < p + q; i++) {
        cin >> graph[i].type;
        if (graph[i].type == NOT) graph[i].inputB = 0;
    }

    int begin, end;
    for (int i = 0; i < m; i++) {
        cin >> begin >> end;
        begin--, end--;
        if (graph[end].inputA == -1) graph[end].inputA = begin;
        else graph[end].inputB = begin;
    }

    for (int i = p + q; i < p + q + r; i++)
        graph[i].inputB = 0, dfs(i);

    int max_time = 0;
    for (int i = p + q; i < p + q + r; i++)
        max_time = max(graph[i].time - 1, max_time);
    cout << max_time << "\n";

    for (int i = p + q; i < p + q + r; i++)
        cout << graph[i].current << " ";
}

另一種想法是 DFS，同時也是我預設的題解。對於 AND, OR, XOR 這種的閘，我們不讓它在第一次連到時就流通，等待第二次電流經過再使電流通過這個閘再使結果繼續流通。然而問題是：這樣電流保證會連通全部的圖嗎？
答案是肯定的，因為輸入保證它必定可以從輸入向輸出流，而在下一個點不能走前，對於當前探索到的點們它就是普通的 DFS，而普通的 DFS 就保證了每個點、每條邊會被走到這條性質。而當新的點開拓以後，可以視為新的圖處理。

實際上如何實作？首先，對於一個邏輯閘，我們記錄它當前的狀態：目前被幾道電流激活、是哪一種邏輯運算、連到哪些閘、當前邏輯閘的延遲等。接著我們定義這個探索的過程（就是底下的 DFS 函式），當在 cur 這個點時，我們嘗試探索附近所有的點，如果有滿足電流數的閘，我們就探索那個閘，並且將當前電流的結果、延遲用來更新下一個閘的數據。
剩下有一些實作小細節要注意的部分我相信可以直接靠範測試出來，畢竟範測給滿好的。
複雜度同樣 $O(p + q + r + m)$

程式能力需求：`圖論` `DFS` `模擬`

#### 參考題解 by DFS

#include <functional>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::vector;

const int OUTPUT = 0, AND = 1, OR = 2, XOR = 3, NOT = 4, INPUT = 5;
const bool P = 1, N = 0;
const int need_input[] = {0, 2, 2, 2, 1};  // 需要的輸入數量

struct gate {
    int type = 0;
    int input_cnt = 0;  // 目前已經滿足幾個輸入
    int current;        // 目前接受到的電流
    vector<int> output;
    int time = 0;
};

bool operate(bool A, bool B, int type) {
    if (type == AND) return A && B;
    if (type == OR) return A || B;
    if (type == XOR) return A != B;
    if (type == NOT) return !A;
    return A;
}

vector<gate> graph;

void dfs(int cur, bool ele) {  // ele 是流進來的電流
    if (graph[cur].type == OUTPUT) {
        graph[cur].current = ele;
        graph[cur].time--;  // 輸出閘不算在時間內
        return;
    }

    bool output_result = operate(ele, graph[cur].current, graph[cur].type);

    for (int i = 0; i < graph[cur].output.size(); i++) {
        int nxt = graph[cur].output[i];
        graph[nxt].input_cnt++;
        if (graph[nxt].input_cnt >= need_input[graph[nxt].type]) {
            graph[nxt].time = max(graph[cur].time + 1, graph[nxt].time);
            dfs(nxt, output_result);
        }
        else {
            graph[nxt].time = graph[cur].time + 1;
            graph[nxt].current = output_result;
        }
    }
}

int main() {
    int p, q, r, m;
    cin >> p >> q >> r >> m;

    graph.resize(p + q + r);
    int begin, end;

    for (int i = 0; i < p; i++) {
        cin >> graph[i].current;
        graph[i].type = INPUT;
    }

    for (int i = p; i < p + q; i++)
        cin >> graph[i].type;

    for (int i = 0; i < m; i++) {
        cin >> begin >> end;
        begin--, end--;
        graph[begin].output.push_back(end);
    }

    for (int i = 0; i < p; i++)
        dfs(i, graph[i].current);

    int max_time = 0;
    for (int i = p + q; i < p + q + r; i++)
        max_time = max(max_time, graph[i].time);
    cout << max_time << "\n";

    for (int i = p + q; i < p + q + r; i++)
        cout << graph[i].current << " ";
}

## [P4 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934)

### Subtask 1: $n \leq 13$
這個範圍看起來是枚舉，問題是要枚舉什麼東西。
要枚舉什麼留給你們自己想，我懶（望向只剩七天的段考和顯示 12:30 的時鐘）。

### Subtask 2: 無其他限制
歡迎回到 P4 比 P3 簡單系列（咦）
這題是滿裸的區間 DP 問題，如果你忘記什麼是區間 DP 我幫你複習下：
枚舉區間，由區間小枚舉到區間大，可以透過枚舉左界再依照區間大小推算右界得到。
接著我們希望能把這個問題分割。對於一個區間 $[l,\ r)$，我們可以枚舉它的分隔線 $x$ ，這個區間拆成 $[l,\ x)$, $[x,\ r)$，接著我們就有了轉移式：

$dp_{[l,\ r]} = min(dp_{[l,\ x)} + dp_{[x, r)} + cost)$

這邊的 cost 指兩個區間合併時消耗的成本，也就是 $[l,\ x)$, $[x,\ r)$ 的區間和的差的絕對值。

而區間和可以利用前綴和 $O(1)$ 求得，因此整個過程的複雜度 $O(n^3)$

由於這題要用到前綴和，1-base 比較好寫，因此下面的 code 採用左閉右閉，1-base，實作時要特別注意邊界條件。

程式能力需求：`DP` `區間 DP`

#### 參考題解

#include <functional>
#include <iostream>
#include <vector>

using std::abs;
using std::cin;
using std::cout;
using std::min;
using std::vector;

int main() {
    int n;
    cin >> n;
    vector<int> data(n + 1);
    vector<int> prefix(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> data[i];
        prefix[i] = prefix[i - 1] + data[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, (int)2e9));  // dp[l][r] 表示合併 [l, r] 所需的最小成本
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            for (int x = l; x < r; x++) {
                int cost = abs((prefix[r] - prefix[x]) - (prefix[x] - prefix[l - 1]));
                dp[l][r] = min(dp[l][x] + dp[x + 1][r] + cost, dp[l][r]);
            }
        }
    }
    cout << dp[1][n];
}