Try   HackMD

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

撰寫者 4Yu

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

1. d483. hello, world

C++ 基本架構 輸出









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

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

2. a001. 哈囉

輸入輸出 變數











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

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

3. a002. 簡易加法

輸入輸出 變數 運算子











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

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

4. d827. 買鉛筆

輸入輸出 變數 運算子

提示：
一打 12 支

總價 = 幾打 * 一打價錢 + 剩下的 * 一支價錢










#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. ㄑㄧˊ 數？

if-else 條件判斷式











#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;
}

進階解法：三元運算










#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 函數

多重條件判斷式












#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. 我不說髒話

迴圈

  • for 迴圈寫法











#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 迴圈寫法











#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

迴圈 多重判斷式


















#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 多重選擇


























#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. 文文採西瓜

迴圈 判斷式 陣列

  • 用 while 迴圈不用到陣列寫法















#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 迴圈 + 陣列寫法

















#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. 新手練習題—陣列

迴圈 陣列














#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. 前綴和練習

前綴和建置 迴圈 陣列

注意數字範圍可能會產生溢位（Overflow），變數型別要開 long long






















#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. 吞食天地

前綴和應用 EOF 輸入 複雜度分析

O(n) 建前綴和，
O(1) 查詢


























#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. 吞食天地二

二維前綴和 巢狀迴圈 二維陣列 EOF 輸入 排容原理





























#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 浪費空間





























#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 練習

STL 資料結構 queue 佇列
























#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 練習

STL 資料結構 stack 堆疊
























#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. 免費仔

STL 資料結構 set 集合




















#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.明明的随机数

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

運用了 set 可以去除重複元素並排序的特性
最後用 for(auto i : s) 遍歷全部元素並輸出
















#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 爬樓梯

DP 動態規劃

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





















#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

DP 動態規劃

定義 dp[i] = 用硬幣組合出 i 元的最大方法數
跟上一題差不多，只不過種類更多了，從 2 種（走 1 步或走 2 步）變成 5 種（5 種不同的幣值），所以我們再套一層迴圈去累計每種的方法數


























#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.传球游戏

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] 即為答案



















#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

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

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
































#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

Last changed by 
 
SCIST
南臺灣學生資訊社群
0
1
185

Read more

SCIST 美食地圖

https://maps.app.goo.gl/2y4ArncwqSnS174j6

Jun 2, 2025
SCIST S5 培訓課程 113 學年度實體學員須知

本篇內容將持續更新

May 15, 2025
【 SCIST S5 】113 學年度培訓課程資源大全

SCIST 官方網站

Apr 27, 2025
【 SCIST S5 】113 學年度培訓課程資源大全 封面

👈🏻 請打開側邊欄，此彙整將持續更新

Feb 25, 2025
Read more from SCIST
Published on HackMD