---
# System prepended metadata

title: SCIST S5 演算法推廣課程題解
tags: [S5 公開資源]

---

# SCIST S5 演算法推廣課程隨堂練習題解參考程式碼

> 撰寫者 [name=4Yu]

[toc]

# 上午 C++ 語法 講師：4Yu

## 1. [d483. hello, world](https://zerojudge.tw/ShowProblem?problemid=d483)
`C++ 基本架構` `輸出`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() 
{
    cout << "hello, world\n";
    return 0;
}
```

## 2. [a001. 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001)
`輸入輸出` `變數`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() 
{
	string s; 
	cin >> s;
	cout << "hello, " << s << '\n';
	return 0;
}
```

## 3. [a002. 簡易加法](https://zerojudge.tw/ShowProblem?problemid=a002)
`輸入輸出` `變數` `運算子`

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

int main() 
{
	int a, b;
	cin >> a >> b;
	cout << a + b << '\n';
	return 0;
}
```

## 4. [d827. 買鉛筆](https://zerojudge.tw/ShowProblem?problemid=d827)
`輸入輸出` `變數` `運算子`
> 提示：
> ||一打 12 支||
> 
> 總價 = ||幾打 * 一打價錢 + 剩下的 * 一支價錢||
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() 
{
	int n; cin >> n;
	cout << (n / 12 * 50) + (n % 12 * 5) << '\n';
	return 0;
}
```

## 5. [d064. ㄑㄧˊ 數？](https://zerojudge.tw/ShowProblem?problemid=d064)
`if-else 條件判斷式`

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

int main() 
{
	int n; cin >> n;
	if (n % 2 == 0) cout << "Even\n";
	else cout << "Odd\n";
	return 0;
}
```

進階解法：[三元運算](https://seansie0830.github.io/posts/cpp-3opeator/)
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() 
{
	int n; cin >> n;
	cout << (n % 2 ? "Odd" : "Even") << '\n';
	return 0;
}
```

## 6. [d058. BASIC 的 SGN 函數](https://zerojudge.tw/ShowProblem?problemid=d058)
`多重條件判斷式`

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

int main() 
{
    int n; cin >> n;
    if (n > 0) cout << 1 << '\n';
    else if (n == 0) cout << 0 << '\n';
    else cout << -1 << '\n';
    return 0;
}
```

## 7. [d498. 我不說髒話](https://zerojudge.tw/ShowProblem?problemid=d498)
`迴圈`
- for 迴圈寫法
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    for (int i=0; i<n; i++)
    {
        cout << "I don't say swear words!\n";
    }
}
```
- while 迴圈寫法
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    while (n--)
    {
        cout << "I don't say swear words!\n";
    }
}
```

## 8. [a058. MOD3](https://zerojudge.tw/ShowProblem?problemid=a058)
`迴圈` `多重判斷式`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n; cin >> n;
	int a = 0, b = 0, c = 0, t;
	while(n--)
	{
		cin >> t;
		if (t % 3 == 0) a++;
		else if (t % 3 == 1) b++;
		else c++;
	}
	cout << a << ' ' << b << ' ' << c << '\n';
	return 0;
}
```
- 補充做法：switch-case 多重選擇
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n; cin >> n;
	int a = 0, b = 0, c = 0, t;
	while(n--)
	{
		cin >> t;
		switch(t % 3)
		{
			case 0:
				a++;
				break;
			case 1:
				b++;
				break;
			case 2:
				c++;
				break;
		}
	}
	cout << a << ' ' << b << ' ' << c << '\n';
	return 0;
}
```

## 9. [d046. 文文採西瓜](https://zerojudge.tw/ShowProblem?problemid=d046)
`迴圈` `判斷式` `陣列` 
- 用 while 迴圈不用到陣列寫法
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    int w, ans = 0;
    while (n--) 
    {
        cin >> w;
        if (w <= 10) ans++;
    }
    cout << ans << '\n';
    return 0;
}
```
- 用 for 迴圈 + 陣列寫法
```cpp=
#include <bits/stdc++.h>
using namespace std;

int N = 105, w[N];

int main()
{
    int n; cin >> n;
    int ans = 0;
    for(int i=0; i<n; i++) cin >> w[i];
    for(int i=0; i<n; i++)
    {
        if (w <= 10) ans++;
    }
    cout << ans << '\n';
    return 0;
}
```

## 10. [f345. 新手練習題—陣列](https://zerojudge.tw/ShowProblem?problemid=f345)
`迴圈` `陣列` 
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+5; // 宣告一個常數 N 作為陣列要開的空間，題目說（N<=10^6），保險起見多加個 5
int P[N]; // 先開好陣列所需的空間為 1000005

int main()
{
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> P[i];
    for(int i=n-1; i>=0; i--) cout << P[i] << ' '; // 反過來輸出，注意 index 範圍要寫對
    return 0;
}
```

# 下午 基礎資料結構與演算法 講師：sakinu

## 1. [e339. 前綴和練習](https://zerojudge.tw/ShowProblem?problemid=e339)
`前綴和建置` `迴圈` `陣列` 
> 注意數字範圍可能會產生溢位（Overflow），變數型別要開 long long
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+5;
long long A[N], pre[N];

int main()
{
    int n; cin >> n;
    pre[0] = 0;
    for(int i=0; i<n; i++)
    {
        cin >> A[i];
        pre[i+1] = pre[i] + A[i];
    }
	
    for(int i=1; i<=n; i++)
    {
        cout << pre[i] << " ";
    }
}
```

## 2. [a693. 吞食天地](https://zerojudge.tw/ShowProblem?problemid=a693)
`前綴和應用` `EOF 輸入` `複雜度分析`
$O(n)$ 建前綴和，$O(1)$ 查詢
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int A[N], pre[N];

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        for(int i=0; i<n; i++)
        {
            cin >> A[i];
            pre[i+1] = pre[i] + A[i];
        }

        int l,r;
        while(m--)
        {
            cin >> l >> r;
            cout << pre[r] - pre[l-1] << "\n";
        }
    }
}
```

## 3. [a694. 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694)
`二維前綴和` `巢狀迴圈` `二維陣列` `EOF 輸入` `排容原理`

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

const int N = 505;
int tb[N][N], pre[N][N];

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cin >> tb[i][j];
                pre[i+1][j+1] = tb[i][j] + pre[i+1][j] + pre[i][j+1] - pre[i][j];
            }
        }

        int x1,y1,x2,y2;
        while(m--)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            cout << pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1] << "\n";
        }
    }
}
```


或是可以直接加在原本陣列上，不用多開個 pre 浪費空間
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
int A[N][N];

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                cin >> A[i][j];
                A[i][j] += A[i-1][j] + A[i][j-1] - A[i-1][j-1];
            }
        }

        int x1,y1,x2,y2;
        while(m--)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            cout << A[x2][y2] - A[x2][y1-1] - A[x1-1][y2] + A[x1-1][y1-1] << "\n";
        }
    }
}
```

## 4. [e447. queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447)
`STL 資料結構` `queue 佇列`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,t,x; cin >> n;
    queue<int> q;
    while(n--)
    {
        cin >> t;
        if(t == 1)
        {
            cin >> x;
            q.emplace(x);
        }
        else if(t == 2)
        {
            if(q.empty()) cout << "-1\n";
            else cout << q.front() << "\n";
        } 
        else if(!q.empty()) q.pop();
    }
}
```

## 5. [i213. stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213)
`STL 資料結構` `stack 堆疊`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,x; cin >> n;
    stack<int> s;
    while(n--)
    {
        cin >> k;
        if(k == 1)
        {
            cin >> x;
            s.push(x);
        }
        else if(k == 2)
        {
            if(s.empty()) cout << "-1\n";
            else cout << s.top() << "\n";
        }
        else if(!s.empty()) s.pop();
    }
}
```

## 6. [n369. 3. 免費仔](https://zerojudge.tw/ShowProblem?problemid=n369)
`STL 資料結構` `set 集合`
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; cin >> n;
    string a,b;
    set<string> s;
    while(n--)
    {
        cin >> a >> b;
        if(s.count(a)) cout << b << " account has been used\n";
        else
        {
            cout << "welcome, " << b << "\n";
            s.insert(a);
        }
    }
}
```

## 7. [b130. NOIP2006 1.明明的随机数](https://zerojudge.tw/ShowProblem?problemid=b130)

`STL 資料結構` `set 集合` `Range-based for loop`

> 運用了 set 可以去除重複元素並排序的特性
> 最後用 `for(auto i : s)` 遍歷全部元素並輸出
> 
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,t; cin >> n;
    set<int> s;
    while(n--)
    {
        cin >> t;
        s.insert(t);
    }
    cout << s.size() << '\n';    
    for(auto i : s) cout << i << ' ';
}
```

## 8. [c547. Bert 爬樓梯](https://zerojudge.tw/ShowProblem?problemid=c547)

`DP 動態規劃`

定義 dp[i] = 走到第 i 階時的最大走法數
轉移式為 dp[i] = dp[i-1] + dp[i-2]
因為一次只能走 1 階或 2 階，所以第 i 階只能從第 i - 1 階和第 i - 2 階走過來
先推出每項的值，每當詢問時直接查詢就好

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

const int MOD = 1e9+7, N = 10005;
int dp[N];

int main()
{
    dp[0] = dp[1] = 1;
    for(int i=2; i<=N; i++)
    {
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    }
    
    int n;
    while(cin >> n)
    {
        cout << dp[n] << "\n";
    }
}
```


## 9. [d133. 00357 - Let Me Count The Ways](https://zerojudge.tw/ShowProblem?problemid=d133)

`DP 動態規劃`

定義 dp[i] = 用硬幣組合出 i 元的最大方法數
跟上一題差不多，只不過種類更多了，從 2 種（走 1 步或走 2 步）變成 5 種（5 種不同的幣值），所以我們再套一層迴圈去累計每種的方法數
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int N = 30005, coins[5] = {1,5,10,25,50};
long long dp[N];

int main()
{
    dp[0] = 1;
    for(int i=0; i<5; i++)
    {
        for(int j=coins[i]; j<=N; j++)
        {
            dp[j] += dp[j - coins[i]];
        }
    }

    int n;
    while(cin >> n)
    {
        if(dp[n] == 1) cout << "There is only 1 way";
        else cout << "There are " << dp[n] << " ways";
        cout << " to produce " << n << " cents change.\n";
    }
}
```

## 10. [d105. NOIP 2008 3.传球游戏](https://zerojudge.tw/ShowProblem?problemid=d105)

`DP 動態規劃`

定義 dp[i][j] = 經過 j 次傳球後回到 i 手上的路徑數
將 dp[0][0] 初始化為 1，因為經過 0 次傳球後回到 0 手上的路徑數只有一個
將 dp[0][1 ~ n-1] 初始化為 0，因為不可能經過 0 次傳球後回到 1 ~ n-1 手上
每次只能往左邊或右邊傳球，所以轉移式為 `dp[i][j] = dp[i-1][(j+1)%n] + dp[i-1][(j-1+n)%n];` 要 % n 讓它可以循環
我們要求經過 m 次傳球回到 0 手上的路徑數，取 dp[m][0] 即為答案

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

int main()
{
    int n, m; cin >> n >> m;
    int dp[31][31] = {0};
    dp[0][0] = 1;
    for(int j=1; j<n; j++) dp[0][j] = 0;
    for(int i=1; i<=m; i++)
    {
        for(int j=0; j<n; j++)
        {
            dp[i][j] = dp[i-1][(j+1)%n] + dp[i-1][(j-1+n)%n];
        }
    }
    cout << dp[m][0] << "\n";
}
```


## 11. [b304. 00673 - Parentheses Balance](https://zerojudge.tw/ShowProblem?problemid=b304)

`stack 進階應用` `括號匹配問題` `getline 輸入`

可以使用 stack 實作括號匹配問題，想法是維持 stack 內都只放入左括號，遇到右括號時，若與 stack 最上方的左括號匹配就 pop，否則就不是一個正確的運算式，例如：`[)` 無法匹配就不可能正確了。因為每對括號若匹配就會被 pop 掉，所以直到最後若 stack 為空，就是一個正確的運算式。

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

int main()
{
    int n; cin >> n; 
    string s; getline(cin,s);
    while(n--)
    {
        stack<char> sk;
        getline(cin,s);
        if(s == " ")
        {
            cout << "Yes\n";
            continue;
        }

        bool ans = true;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || sk.empty()) sk.push(s[i]);
            else if(!sk.empty())
            {
                if((sk.top() == '(' && s[i] == ')') || (sk.top() == '[' && s[i] == ']')) sk.pop();
                else { ans = false; break; }
            }
        }
        if(ans && sk.empty()) cout << "Yes\n";
        else cout << "No\n";
    }
}
```

注意這題有空白行，所以要用 getline 輸入，雖然推廣課程沒教到，不過培訓課程會教，所以快報名吧！
# https://forms.gle/3dSRs2JsfqsDgnWx8