# APCS 20230604 題解
## 前言
如果你能看到這篇題解，說明我有大學念了才有這個鹹時間。
## [路徑偵測](https://zerojudge.tw/ShowProblem?problemid=k731)
### 想法
把向上右下左各標為 0 1 2 3，相減為 0 方向不變，相減為 1 右轉，相減為 2 迴轉，相減為 3 左轉。
### 時間複雜度
$O(N)$
### code

#include <bits/stdc++.h>
using namespace std;
int T(int f, int pf){
    return (f - pf + 4) % 4;
}
signed main(){
    int n, l = 0, r = 0, b = 0, px, py, pf, x = 0, y  = 0, f;
    cin >> n;
    for(int i = 1; i <= n; i++){
        px = x, py = y, pf = f;
        cin >> x >> y;
        if(y - py > 0) f = 0;
        else if(x - px > 0) f = 1;
        else if(y - py < 0) f = 2;
        else if(x - px < 0) f = 3;
        if(i == 1) continue;
        if(T(f, pf) == 1) r++;
        else if(T(f, pf) == 2) b++;
        else if(T(f, pf) == 3) l++;
    }
    cout << l << " " << r << " " << b << "\n";
    return 0;
}

## [特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)
### 想法
對每個點枚舉其他所有點看是否在距離內再加上去點權看是否符合條件。
### 時間複雜度
$O(N^2M^2)$
### code

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, m;
array<array<int, 54>, 54> A;
vector<pair<int, int>> ans;
int sum(int x, int y, int d){
    int s = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(abs(i - x) + abs(j - y) <= d) s += A[i][j];
        }
    }
    return s;
}
signed main(){
    int k = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> A[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(sum(i, j, A[i][j]) % 10 == A[i][j]){
                k++;
                ans.pb({i, j});
            }
        }
    }
    cout << k << "\n";
    for(auto [i, j] : ans) cout << i << " " << j << "\n";
    return 0;
}

### 想法
對每個點向外BFS直到距離用盡，將路過的所有點權加總看是否符合條件。
### 時間複雜度
$O(NM)$
### code

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct ooo{
    int x, y, d;
};
int n, m;
array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
array<array<int, 54>, 54> A, vis;
vector<pair<int, int>> ans, V;
void clear(){
    for(auto [i, j] : V) vis[i][j] = 0;
	V.clear();
}
int sum(int x, int y, int d){
    int s = 0;
    queue<ooo> Q;
    Q.push({x, y, 0});
    while(!Q.empty()){
        auto [i, j, k] = Q.front();
        Q.pop();
        if(k > d || i < 0 || j < 0 || i >= n || j >= m || vis[i][j]) continue;
        vis[i][j] = 1, s += A[i][j], V.pb({i, j});
        for(int f = 0; f < 4; f++) Q.push({i + dx[f], j + dy[f], k + 1});
    }
    return s;
}
signed main(){
    int k = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> A[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            clear();
            if(sum(i, j, A[i][j]) % 10 == A[i][j]){
                k++;
                ans.pb({i, j});
            }
        }
    }
    cout << k << "\n";
    for(auto [i, j] : ans) cout << i << " " << j << "\n";
    return 0;
}

## [磁軌移動序列](https://zerojudge.tw/ShowProblem?problemid=k733)
### 想法
先打所有 L 對應的 E 標出來。接著從頭開始看，有 T 就算距離，遇到 L 時將 L 到對應 E 的序列往下遞迴，回傳時再乘上次數。
### 時間複雜度
$O(字串長度)$
### code

#include <bits/stdc++.h>
#define int long long
using namespace std;
string M;
array<int, 100004> E;
stack<int> S;
pair<int, int> read(int p){
    int s = 0;
    while(M[p] >= '0' && M[p] <= '9'){
        s *= 10, s += M[p] - '0';
        p++;
    }
    return {s, p};
}
int next(int p){
    while(M[p] != 'T') p++;
    return read(p + 1).first;
}
pair<int, int> run(int l, int r, int now){
    int sum = 0, nxt;
    for(int i = l; i <= r; i++){
        if(M[i] == 'L'){
            nxt = next(i + 1);
            auto [cnt, p] = read(i + 1);
            auto [s, pos] = run(p, E[i] - 1, nxt);
            sum += cnt * s + (cnt - 1) * abs(pos - nxt) + abs(nxt - now);
            i = E[i], now = pos;
        }else{
            auto [nxt, p] = read(i + 1);
            sum += abs(nxt - now), i = p - 1, now = nxt;
        }
    }
    return {sum, now};
}
signed main(){
    int l;
    cin >> M;
    for(int i = 0; i < M.size(); i++){
        if(M[i] == 'L') S.push(i);
        else if(M[i] == 'E'){
            l = S.top(), S.pop();
            E[l] = i;
        }
    }
    cout << run(0, M.size() - 1, 10).first << "\n";
    return 0;
}

## [開啟寶盒](https://zerojudge.tw/ShowProblem?problemid=k734)
### 想法
先把寶箱需要哪些鑰匙轉換成鑰匙可以開啟哪些寶箱，再來拿到一個鑰匙就可以把它能開的寶箱所需鑰匙數 - 1，所需鑰匙數歸零之時即寶箱開啟之日。
### 時間複雜度
$O(K(N + M))$
要加輸入輸出優化才不會被卡
### code

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 100004> K, vis;
array<vector<int>, 100004> O, G;
queue<int> Q;
int open(){
    int cnt = 0, key;
    while(!Q.empty()){
        key = Q.front();
        Q.pop();
        for(int c : O[key]){
            K[c]--;
            if(K[c] == 0){
                cnt++;
                for(int k : G[c]){
                    if(!vis[k]) vis[k] = 1, Q.push(k);
                }
            }
        }
    }
    return cnt;
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, m, k, t, x;
    cin >> n >> m >> k >> t;
    for(int i = 0; i < t; i++){
        cin >> x;
        vis[x] = 1;
        Q.push(x);
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            cin >> x;
            K[i]++;
            O[x].pb(i);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            cin >> x;
            G[i].pb(x);
        }
    }
    cout << open() << "\n";
    return 0;
}