p1. 成績指標

題目連結

我們定義分數 為 集合，分數 為 集合
我們將其排序並從 找出最小值 找出最大值
如果 沒有元素，代表沒有最小的及格成績，即為 wrost case
如果 沒有元素，代表沒有最大的不及格成績，即為 best case

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

vector<int> m;

int main(){
    int n, minX = INT_MAX, maxY = INT_MIN;
    cin >> n;
    
    m.resize(n);
    for (auto &e: m){
        cin >> e;
        if (e >= 60)
            minX = min(minX, e);
        
        else 
            maxY = max(maxY, e);
    }

    sort(m.begin(), m.end());
    
    for (auto i: m)
        cout << i << ' ';

    cout << '\n';
    if (minX == INT_MAX)
        cout << maxY << '\n' << "worst case";

    else if (maxY == INT_MIN)
        cout << "best case" << '\n' << minX;
    
    else
        cout << maxY << '\n' << minX << '\n';
}

p2. 矩陣轉換

題目連結
定義 矩陣 為行數 為列數

1
2
3
4
//值 座標(i, j)
1(0, 0), 1(0, 1) 
1(1, 0), 3(1, 1)
2(2, 0), 1(2, 1)

翻轉後

1
2
3
2(0, 0), 1(0, 1)
1(1, 0), 3(1, 1)
1(2, 0), 1(2, 1)

旋轉後得 

1
2
1(0, 0) 1(0, 1) 2(0, 2)
1(1, 0) 3(1, 1) 1(1, 2)

透過觀察位置的變化就會發現其規律。

  • 翻轉及其反操作
    經過翻轉 座標變化 ->

Note:
這裡的操作次數為 因為每次執行會交換到兩條行數

  • 旋轉及其反操作
    經過旋轉 座標變化 ->

Note
這裡的 參數已經變為控制列的 參數
因此要將兩者的值調換，避免 與 變成了錯誤的行列數

因題目要求因此實作時記得將操作改為反操作的形式

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

int arr[10][10], r, c, m, ops;

void flip_back(){
    for (int i = 0; i < r/2; i++)
        for (int j = 0; j < c; j++)
            swap(arr[i][j], arr[r-i-1][j]);
}

void rotate_back(){
    int tmp[10][10];
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            tmp[i][j] = arr[i][j];

    swap(r, c);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            arr[i][j] = tmp[j][r-i-1];
}

int main(){
    cin >> r >> c >> m;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> arr[i][j];
        }
    }
    
    while (m--) {
        cin >> ops;
        if (ops)
            flip_back();

        else
            rotate_back();   
    }

    cout << r << ' ' << c << '\n';
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) 
              cout << arr[i][j] << ((j+1 == c)? "":" ");
        
        cout << '\n';
    }
}

p3. 線段覆蓋長度

題目連結

這題我們用貪心的角度去思考，如果將線段按左界排序，我們就可以逐步判斷線段覆蓋的區間。
我們定義當前最大左右界為 單一線段的左右界為
因為排序的關係所以我們可以保證新加入的線段 。

  • 如果新加入的線段 ，那麼覆蓋長度則不變
  • 如果新加入的線段 ，那麼代表說 這個區間已經被覆蓋了，因此我們只需要新增未被覆蓋的區間
  • 如果新加入的線段 ，那麼代表說 這塊是完全獨立的線段，我們只需新增它即可

實作時記得每次都要更新當前最大右界 。
複雜度：程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define l first
#define r second

priority_queue<pii, vector<pii>, greater<pii>> pq;

int main(){
    int n, a, b;
    cin >> n;
    while (n--){
        cin >> a >> b;
        pq.push({a, b});
    }

    int mr = -1, result = 0;
    while (pq.size()) {
        pii t = pq.top();
        pq.pop();
        if (t.r <= mr)
            continue;

        result += (t.l <= mr)? (t.r - mr): (t.r - t.l);
        mr = t.r;
    }

    cout << result << '\n';
}

p4. 血緣關係

題目連結

這題算是圖論的經典題，問你圖上距離最遠的兩個點，即為所謂的樹直徑。
由於只有詢問一次，所以只要做兩次 Depth-First-Search 就行。
至於 DFS 的實作這裡就不多作介紹。

  • 第一次 DFS 的時候先搜尋離當前節點最遠的節點。
  • 第二次 DFS 的時候以第一次搜尋到的點作為起點搜尋最遠的節點。

複雜度：

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
int md = -1, mi = -1;

void dfs(int idx, int father, int depth){
    for (auto i: g[idx]){
        if (i != father){
           dfs(i, idx, depth+1);
        }
    }

    if (depth > md){
        md = depth;
        mi = idx;
    }
}

signed main(){
    int n, a, b;
    cin >> n;
    g.assign(n, {});
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(0, -1, 0);
    dfs(mi, -1, 0);
    cout << md << '\n';
}