# S3 演算法 week 4
###### tags: `S3 公開資源`

:::info
時間：11/13 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：複雜度分析與程式技巧
直播連結：https://youtu.be/ecpPlY5Xk-M
:::

## 課程內容
因進度調整，複雜度與程式技巧延至本周上課
- 複雜度分析
- 程式技巧
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS

## 注意事項
1. 本次上課會開始進到演算法的領域，請務必熟悉前三週的內容，並預習講義第二章之後的內容
2. 上次練習賽的題解已經上傳至 YouTube：https://youtu.be/8U8OAURzDew
3. 所有上課相關連結都會放在資源彙整裡：https://hackmd.io/@SCIST/rykldedMj
4. 上課期間請全程配戴口罩
5. 建議學員可以帶自己的筆電，以減少重新設定的時間成本
6. 請假表單：https://forms.gle/2ESVuTezcHCK959H6

# 必作題題解

[TOC]

## 時間複雜度分析_解答

### P1
$O(n^3)$
補充：這是最短路徑演算法中的 Floyd–Warshall 可以知道每個點到每個點的最短距離

### P2
$O(n\log n)$

### P3
$O(nk)$
補充：選擇排序

### P4
$O(n^3)$

## 初章後半

### [ZJ c290](https://zerojudge.tw/ShowProblem?problemid=c290)

撰寫者：小麥

用string一個一個的讀出來，再char轉int，之後相減。

:::spoiler 參考程式碼

#include <iostream>
#include <string>

using namespace std;

int main() {

    string input;
    cin >> input;
    
    int len = input.length();

    int odd_sum = 0;
    for (int i = 1; i < len; i+=2) {
        odd_sum += input[i] - '0';
    }
    int even_sum = 0;
    for (int i = 0; i < len; i+=2) {
        even_sum += input[i] - '0';
    }

    int ans = odd_sum - even_sum;
    if (ans < 0) {
        cout << (ans * -1) << '\n';
    }
    else {
        cout << ans << '\n';
    }

    return 0;

}

:::

---

### [ZJ h082](https://zerojudge.tw/ShowProblem?problemid=h082)

撰寫者：

---
### [ZJ f606](https://zerojudge.tw/ShowProblem?problemid=f606)

撰寫者：fishhh

這裡就提供參考程式碼
若需要更詳細的解題報告，請參考講師的講義~

:::spoiler

#include "iostream"
using namespace std;
#define int long long
signed main(){
    int n,m,k;
    int q[60][60]={};
    cin>>n>>m>>k;
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            cin>>q[x][y];
        }
    }
    int minn=1e9;
    while(k--){
        int ans=0;
        int sum[60][60]={};
        int l;
        for(int i=0;i<n;i++){
            cin>>l;
            for(int v=0;v<m;v++){
                sum[l][v]+=q[v][i];
            }
        }

        for(int y=0;y<m;y++){
            for(int x=0;x<m;x++){
                if(x==y){
                    ans+=sum[x][y];
                }
                else if(sum[x][y]<=1000){
                    ans+=sum[x][y]*3;
                }
                else{
                    ans+=3000;
                    ans+=(sum[x][y]-1000)*2;
                }
            }
        }
        minn= min(minn,ans);
    }
    cout<<minn;
}

:::

---
## 二章 - 第一節

### [UVa 483](http://domen111.github.io/UVa-Easy-Viewer/?483)

撰寫者：Jun-an

使用 getline(cin, str) 讀入整行字串，接著遍歷字串，
宣告一個字串變數 temp 儲存遍歷過的字元，
如果讀到空白就將 temp 反著輸出，再把 temp 清空，
因為是讀到空白再輸出，如果沒有空白就不會有輸出，
所以輸入字串後在後面加上一個空白。

:::spoiler 參考程式碼

#include <iostream>

using namespace std;

int main() {
    string sentence;

    while (getline(cin, sentence)) {
        sentence += " ";

        string temp;
        bool appeared = false;

        for (int i = 0; i < sentence.size(); i++) {
            if (sentence[i] == ' ') {
                if (appeared) {
                    cout << " ";
                }

                for (int j = temp.size(); j > 0; j--) {
                    cout << temp[j - 1];
                }

                temp = "";
                appeared = true;

                continue;
            }

            temp += sentence[i];
        }

        cout << '\n';
    }

    return 0;
}

:::

---

## 二章 - 第二節

### [ZJ b840](https://zerojudge.tw/ShowProblem?problemid=b840)

撰寫者：小麥

窮舉每個點當作左上角的起點，然後用兩層for迴圈窮舉所有子矩形的大小(長&寬) 再遍歷

所以最後程式長相會是有6個for迴圈包在一起

時間複雜度：$O(n^6)$
$n \leq 20$ 所以 $n^6$ 的計算量可以在 1 秒內跑完!

補充：

先用建立二維前綴和，在枚舉起點和終點。
時間複雜度：$O(n^2)$

:::spoiler 參考程式碼

#include <iostream>

using namespace std;

int nums[20][20];
int prefixSum[20 + 1][20 + 1];

int main() {

    int n;
    
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> nums[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            prefixSum[i][j] = (prefixSum[i-1][j] - prefixSum[i-1][j-1]) + prefixSum[i][j-1] + nums[i-1][j-1];
        }
    }
    
    int maxi = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int o = i; o <= n; o++) {
                for (int k = j; k <= n; k++) {
                    int sum = prefixSum[o][k] - prefixSum[o][j-1] - prefixSum[i-1][k] + prefixSum[i-1][j-1];
                    if (sum > maxi) {
                        maxi = sum;
                    }
                }
            }
        }
    }

    cout << maxi << '\n';

    return 0;

}

:::

---

### [ZJ f312](https://zerojudge.tw/ShowProblem?problemid=f312)

撰寫者：小麥

先從第一個工廠有最多的員工開始，第一個工廠-1，第二個工廠就+1，一直到第一個工廠到0為止

:::spoiler 參考程式碼

#include <iostream>

using namespace std;

int main() {

    int A1, B1, C1;
    int A2, B2, C2;
    int n;

    cin >> A1 >> B1 >> C1;
    cin >> A2 >> B2 >> C2;
    cin >> n;

    int maxi = -1000000;
    int left_pointer = n;
    int right_pointer = 0;

    while (right_pointer != n + 1) {
        int Y1 = A1 * (left_pointer * left_pointer) + B1 * left_pointer + C1;
        int Y2 = A2 * (right_pointer * right_pointer) + B2 * right_pointer + C2;
        int sum = Y1 + Y2;
        if (maxi < sum) {
            maxi = sum;
        }
        left_pointer--;
        right_pointer++;
    }

    cout << maxi << '\n';

    return 0;

}

:::

---