# 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
Sign in with Wallet
Connect another wallet