從零開始的演算法競賽入門教學

0-7 陣列

發表於 2020-11-05 更新於 2020-11-10

陣列

當我們要儲存 5 個變數時，要怎麼做呢？

1	int a, b, c, d, e;

我們可能會這樣寫。但，如果今天要儲存 5000 個變數時，要怎麼做呢？

宣告

使用陣列，可以以陣列名稱+位置，儲存大量資料，基本語法如下：

int arr[15];
char c[15];
double d[20];
string strs[15];

arr 是這個 int 陣列的名稱，而15則是它的大小。

陣列也可以在宣告時指定值，例如：

1 2	int arr[4] = {1, 4, 2, 3}; cout<<arr[0]<<" "<<arr[3]<<'\n';

輸出：

1 3

可以不用指派每一個元素的值，只指派前幾個，不足者會自動補 0。像這樣：

1 2	int arr[4] = {1, 4}; cout<<arr[0]<<" "<<arr[3]<<'\n';

輸出：

1 0

但若全部未指定值，則陣列中每個元素的值可能是任何值！

陣列宣告過後，不可改變大小或重新宣告。

取值、修改

如果我們想輸出陣列中位於 3 號的元素的值，這樣寫：

1	cout<<arr[3]<<'\n';

其中，arr是你自己取的陣列名稱，[]是中括號。

要特別注意的一點是，在程式語言的世界裡，編號從 0 開始，因此編號 3 其實是這個陣列的第 4 個值。若宣告大小為 5 的陣列，其可用空間為 0 號到 4 號，若使用 5 號元素會產生不可預期的錯誤！

陣列中的元素就像一般元素一樣，可以加減乘除，可以任意指派值，直接把它當成平常的變數就好：

1
2
3

arr[1] += 15;
arr[3] = arr[2] - 1;
arr[5] = 65;

產生 RE 錯誤

若存取了超過陣列空間的元素，例如：

1
2
3

int arr[5];
arr[-1] += 5; // 不可是負的
arr[5] --; // 陣列大小是 5 的話，可用的編號是 0 ~ 4

有機率產生 Runtime Error 錯誤。

錯誤發生時，其表現與 / 0 時相同，在windows上會當機一小段時間，之後出現非 0 的 return code。

這樣的錯誤不會導致Compile Error，因此很危險。更危險的地方是，這樣的錯誤不一定每一次都會發生，甚至有機率在本地測試時是正確的！

因此，務必特別注意此類錯誤，不要再依賴編譯器了！

競賽中的慣例

陣列放在全域

全域，在這裡先理解為：main函式以外。

全域與它的相反–區域是個重要的概念，之後會有詳細介紹。

如果要宣告陣列，在競賽中我們通常不會這樣寫：

1
2
3

int main(){
    int arr[5];
}

我們會這樣寫：

int arr[5];
int main(){

}

為什麼呢？有以下兩個原因

全域變數會自動初始化為每種型態的預設值，在 int 是 0，在 string 是 “” (空字串)，可避免很多不必要的錯誤。
- 複習一下，如果宣告在區域又未指定初始值，它的值是不一定的喔！
在硬體中的儲存位置，導致區域陣列通常只能開到數百萬的大小，但全域陣列可開到數千萬。
- 區域陣列開太大超出限制的話，會在運行到那一行時產生RE。
- 全域陣列開太大超出限制的話，在編譯時，編譯器就會將其擋住，無法通過編譯。

因此，在競賽上，我們通常將陣列宣告於全域。

開多大？

在全域變數宣告的缺點，便是無法依據輸入大小調整陣列大小，不能寫像這樣的code：

int N;
int main(){
    cin>>N;
    int arr[N+5];
}

因為陣列宣告後，是不可改變大小的，因此通常以題目的最大值作為陣列大小。

你說題目沒有給你最大個數限制？那就亂開吧，發生RE的話，就再開大一點。

順帶一提，沒有範圍的題目，99%是爛題。

多維陣列

陣列是可以有多個維度的，例如：

1
2
3

int arr[15][15][15][15];
cin>>arr[1][2][3][4];
cout<<arr[5][3][1][0]<<'\n';

若一個陣列有 n 列 m 行，則其可儲存 n*m 個資料，編號從 [0][0] 、 [0][1] …. [0][m-1] [1][0] … 到 [n-1][m-1]。多維以此類推。

多維陣列用法與相同。要注意，乘起來不可以超過大小限制(約 $10^8$)，不然會 RE / CE。

練習

陣列練習題通常會配合迴圈的使用，以進行讀取或輸出，因此練習題統一置於下一章節。

0-6 進階輸入輸出

發表於 2020-11-04 更新於 2020-11-11

輸入含空白的字串

若輸入一個字串，使用 cin 會讀入到空白為止，但是，如果輸入是像這樣：

1	dasd sakf jfsak fsakl

那該怎麼讀入呢？

可以使用 4 次 cin，但如果空白個數不定，就糟糕了。

在這裡，介紹新的輸入字串方式：

1 2	string s; getline(cin,s);

getline(cin,字串名) 可以讓你輸入整行的含空白字串，直到讀入換行符號’\n’為止。

於是可以這樣輸入：

1
2
3

string s;
getline(cin,s);
cout<<s<<'\n';

getline其實也可以指定讀到特定字元為止，附上詳細教學連結。

注意，若使用char[]宣告字串，語法不同，需這樣寫：

1
2
3

char s[105];
cin.getline(s);
cout<<s<<'\n';

這份講義之後的code，會全數使用string。

getline 與 cin 混用時

輸入一個整數，然後輸入一個含空白的字串，要怎麼寫呢？

直覺的想法可能是：

int n;
string s;
cin >> n;
getline(cin, s);
cout << n << '\n';
cout << s << '\n';

然而，輸入若是：

1 2	3 dasd fasf gasf

輸出的結果卻是：

1
2

為什麼會這樣呢？

還記得 cin 一個整數時的運作原理嗎？一直讀入直到遇見不是整數的字元。

那 getline 的運作原理是，讀入直到遇見換行字元。

發現了嗎？若輸入的檔案是一整數、換行、一字串，cin 遇到換行停在換行的位置，這時使用 getline，就不幸的吃到那個換行後結束了。因此讀到的字串什麼都沒有。

要怎麼解決這個問題呢？最簡單的方法是再呼叫一次getline：

int n;
string s;
cin >> n;
getline(cin, s);
getline(cin, s);
cout << n << '\n';
cout << s << '\n';

然而，這麼寫會影響程式可讀性。因此，可以用 cin.ignore() 來表示我要忽略下一個字元：

int n;
string s;
cin >> n;
cin.ignore();
getline(cin, s);
cout << n << '\n';
cout << s << '\n';

這樣一來，換行字元就成功被跳過了！

cin/cout 加速

cin/cout 其實是一個速度很慢的功能，原因請點連結。

而速度於程式解題競賽中是相當重要的一部分，因此，我們要想辦法讓 cin/cout 加速。

加速的方法有以下兩種：

使用輸入優化

也就是在上方連結可看到的：
1
ios::sync_with_stdio(0), cin.tie(0);
在main函式的開頭，打上這句，cin就加速許多，原因一樣在上方那篇。

因此看起來會像這樣：
1
2
3
4
5
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
}
避免使用 endl

endl其實是由，’\n’與flush組成，flush會使目前輸出的所有東西立刻顯現至螢幕上，但作為代價，其速度並不高。因此，細心的讀者可以注意到，本講義中，所有需要換行的場合，都是使用’\n’進行換行

以上兩點，需同時使用，才能快速進行高達百萬級的輸入輸出。

若只使用第一點，不使用第二點，則在輸出時仍然會因為flush過慢拖累整體執行效率。

若只使用第二點，雖然輸出時不會 flush，但 cin 時預設也會 flush，因此依然很慢。

雖然目前可能還不需要用到，但是在TLE時，請務必想想：是不是輸入太慢造成的問題？

練習

TOJ 5

TOJ 355

355這題會用到一點迴圈的概念，可以先往後讀，之後再回來。

AC Code

// TOJ 5
#include<iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    cout << "Hello ," << s << " !\n";
}

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

int n, k;

int main(){
	ios::sync_with_stdio(0), cin.tie(0); // 試試看把這行刪掉會發生什麼事
	cin >> n >> k; // k 無用
	int mx = 0, sec = 0; // 紀錄當前第一大與第二大數
	for(int i=0,x;i<n;i++){
		cin >> x;
		if(x > mx){ // 比第一大還大
			sec = mx;
			mx = x;
		}
		else if(x > sec){ // 不比第一大還大，但比第二大還大
			sec = x;
		}
	}
	cout << sec << '\n';
}

0-5 進階運算

發表於 2020-10-29 更新於 2020-11-09

浮點數運算誤差處理

使用 double 進行加減乘除時，多少會產生一點誤差，例如，100.0 * 99.0 可能被誤算為 9899.9999999。

此時，若運算中含有 == 等符號，將會出現問題。因此我們不以 == 進行浮點數是否等於的判斷。

取而代之，我們判斷兩個浮點數是否相等，只需判斷他們之間的差的絕對值是否小於某個特定值即可，這個值我們稱作 epsilon，以eps在程式中出現，一般為 10 的 -9 次方，寫作 1e-9。

double a, b, c;
double eps = 1e-9;
cin>>a>>b>>c;
if(c - a*b <= eps && c - a*b >= -eps){ // a * b == c is not good
    cout<<"Equal!\n";
}

字元運算

其實，字元可以加減！

ASCII TABLE

字元在運算的時候，將會被視為其ASCII碼！例如：

1	cout<<'a'+10<<'\n';

輸出將會是：

因為 ‘a’ 的 ASCII 碼是 97，在運算時便將其視為 97 了！

知道這個之後，可以做什麼呢？

可以注意到，**’A’～’Z’以及’a’～’z’以及’0’～’9’，在ASCII table的位置是連續的**，因此若將 ‘a’ 加上 4，就會變成在小寫字母裡，排在 ‘a’ 後面 4 個位置的 ‘e’ 。

1
2
3

char c = 'a';
c += 4;
cout<<c<<'\n';

輸出：

大寫轉小寫

char c;
cin>>c;
c += 'a' - 'A'
cout<<c<<'\n';

將輸入進來的大寫字母，加上 ‘a’(ASCII碼：97) 與 ‘A’(ASCII碼：65) 間的差距，就可以將其轉為大寫了！

字元比較

字元的比較，以其 ASCII 碼為準。

例如，’Z’ 的 ASCII 碼是 90，’a’ 是 97，因此 ‘Z’ < ‘a’。

字串運算

字串可以進行加法，意思為在其後方串接另一字串。

例如：

string s = "abc";
s += "def";
cout<<s<<'\n';
s += 'a';
cout<<s<<'\n';
s = s + s + s;
cout<<s<<'\n';

輸出：

1
2
3

abcdef
abcdefa
abcdefaabcdefaabcdefa

但要注意，字串只有加法，沒有減、乘、除法。

字串比較

字串比較的原則是這樣的：先比第一個字元、一樣的話比第二個、之後比第三個……。如果那個位置是空的，那它比任何字元都小

例如：

“abc” < “baa” (第一個字元，’a’ < ‘b’)

“abc” < “abd” (第三個字元，’c’ < ‘d’)

“abc” < “abcd” (比到第四個時，前面那個字串已經到尾了)

如果打開一本英文辭典，會發現單字就是照著這樣的規則排列的，因此這種方法稱為字典序。

bool的特殊用法

bool x = 5;
cout<<x<<'\n';
x = -1;
cout<<x<<'\n';
x = 0;
cout<<x<<'\n';

輸出：

1
2
3

1
1
0

bool的值只有 1 或是 0 。當一個int被指派給 bool，只要那個int不是0，無論正負，bool值都會是1。

因此，很多時候我們可以這樣寫：

if(a){
    ......
}

//相同於 if(a!=0)

位元運算

在電腦中，數值以二進位儲存，所謂位元運算，指的就是以一個一個只有 0 或 1 的位元為單位進行運算。

對整數而言，我們有以下幾種位元運算：

and &
or |
xor ^
not ~

and &

以位元為單位的and運算

1 & 1 -> 1

1 & 0 -> 0

0 & 0 -> 0

在對兩個整數進行 & 運算時，先將其分解為二進位，接著逐位進行 & 運算。

例如： 6 & 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

逐位進行 & 運算，只有最高位數兩者同時為1，得到結果為 100，為 4 的二進位表示法。

因此， 6 & 5 == 4

or |

以位元為單位的or運算

1 | 1 -> 1

1 | 0 -> 1

0 | 0 -> 0

例如： 6 | 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

110 與 101，在任何一個位數都至少有一個 1，因此 | 運算的結果為 111，為 7 的二進位表示法。

因此， 6 | 5 == 7

xor ^

不要把它當作次方！C++並沒有次方的運算子！

一樣是位元運算，xor是什麼意思呢？

1 ^ 1 -> 0

1 ^ 0 -> 1

0 ^ 0 -> 0

只有一個值為 1 的時候，結果才會為 1，若兩邊同時為 1 或 0，結果都是 0。

例如： 6 ^ 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

110 與 101，在最高位兩者皆為 1 ，在其他位數只有其中一方為 1 ，因此 ^ 運算的結果為 011，為 3 的二進位表示法。

因此， 6 ^ 5 == 3

位元運算的交換律與結合律

同種位元運算間，皆具有交換律與結合律，例如：

3 & 5 & 6 == 6 & 3 & 5

3 ^ (5 ^ 6) == 6 ^ (3 ^ 5)

3 | 5 | 6 == 6 | 3 | 5

但不同種位元運算之間則無結合律，例如：

(7 | 5) & 10 != 7 | (5 & 10)

xor 特別的地方

x ^ x == 0

因此， (a ^ x) ^ x == a ^ (x ^ x) == a ^ 0 == a

以及若 a ^ b = c， a ^ b ^ a = c ^ a，b = c ^ a

正是因為這樣的有趣性質，使得 xor 出現於許多加密演算法中。

練習

TOJ 99

TOJ 100

TOJ 101

AC Code

//TOJ 99
#include<iostream>
using namespace std;
double a,b,c,d;
double eps = 1e-9;

int main() {
    cin>>a>>b>>c>>d;
    double det = a*d - b*c; 
    if(det < eps && det > -eps){
        cout<<0<<'\n';
    }
    else{
        cout<<1<<'\n';
    }
}

// TOJ 100
#include<iostream>
using namespace std;
char c;

int main() {
    cin >> c;
    if(c == 'A'){
        cout<<'@'<<'\n';
    }
    else{
        c--;
        cout<<c<<'\n';
    }
}

// TOJ 101
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    char c = n + 'A' - 1;
    // 5 + 'A' - 1 = 'A' + 4 = 'E'
    cout << c << '\n';
}

0-4 條件判斷與基礎邏輯

發表於 2020-10-27 更新於 2021-12-09

條件判斷

台大的教學

話不多說，直接上程式碼

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

int a,b;

int main(){
    cin>>a>>b;
    if(a > b){
        cout<<a<<" is bigger than "<<b<<'\n';
    }
    else if(a == b){
        cout<<a<<" is equal to "<<b<<'\n';
    }
    else{
        cout<<a<<" is smaller than "<<b<<'\n';
    }
}

if

相信不用多加解釋，就是如果…就的意思。

if(a > b){
    cout<"HI!"<<'\n';
}

這段話的意思是，如果 $a$ 比 $b$ 大，就輸出”HI”。

特別需要注意的有以下幾點：

條件由小括弧包含住
滿足條件後要做的事情由大括號包含住
若滿足條件後要做的事情只有一句(以分號為界)，可不包大括弧
if 可單獨存在，也就是說，就算沒有後面的 else if 跟 else ，也是合語法的
if 可多層套疊

第三點的示範如下：

1 2	if(a>b) cout<<"HELLO!\n";

如果只有一行，可不必以大括弧包含，但還是建議新手盡量都把大括弧寫出來。

第五點的示範如下：

if(a>b){
    if(a>10){
        cout<<"HELLO!\n";
    }
}

if 裡包另一個 if 是可以的！

請比較下列程式輸出的異同：

if(5 < 3){
    cout<<"HELLO\n";
    cout<<"SECOND_LINE\n";
}

1
2
3

if(5 < 3)
    cout<<"HELLO\n";
    cout<<"SECOND_LINE\n";

在第一個程式中，不會有任何輸出，但在第二個程式中，卻輸出了：

1	SECOND_LINE

這是因為若 if 不以大括弧包含，其作用範圍僅限一個分號。

順帶一提，C++ 的換行跟空白沒有太多作用，與 python 不同，因此若這樣寫，雖然不會導致編譯錯誤，但其實效果等同於第二個程式，一樣會輸出 SECOND_LINE。

1 2	if(5 < 3) cout<<"HELLO\n"; cout<<"SECOND_LINE\n";

即使 C++ 沒有像 python 那樣，強制規定你的 tab 跟換行，但為了可讀性與美觀，還是應該在自己的程式碼內適當的使用 tab。一般來說，以大括弧包含起來的程式碼，都應該比括弧外的程式碼多按一個 tab 鍵。

else

不滿足 if 內的情況時，所要執行的指令，以中文來說，就是否則的意思

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

int a,b;

int main(){
    cin>>a>>b;
    if(a > b){
        cout<<a<<" is bigger than "<<b<<'\n';
    }
    else{
        cout<<a<<" is not bigger than "<<b<<'\n';
    }
}

上方的 if，條件為 $a > b$，若沒有滿足 $a > b$，則進入下方的 else 區塊，因此若輸入為 5 7，因為 5 並沒有大於 7 (注意，不是小於，是沒有大於) ，因此程式進入 else 區塊，輸出會是：

1	5 is not bigger than 7

也因為這樣，else 無法單獨存在，必定要有 if 在其之前。

else if

有些事情，例如人生，是無法以簡單的二分法作選擇的，這時，我們需要 else if！

~~雖然我也不覺得用了else if就能為人生作選擇~~

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

int a,b;

int main(){
    cin>>a>>b;
    if(a > b){
        cout<<a<<" is bigger than "<<b<<'\n';
    }
    else if(a == b){
        cout<<a<<" is equal to "<<b<<'\n';
    }
    else{
        cout<<a<<" is smaller than "<<b<<'\n';
    }
}

以中文翻譯，else if大概就是”否則，如果”的意思吧！

當輸入為 5 7 時，程式首先判斷第一個條件：

1	如果 a > b ......

此時，$a$ 是 5，$b$ 是 7，5 並沒有大於 7，因此落入下一個區塊。

第二個區塊為：

1
2
3

else if(a == b){
    cout<<a<<" is equal to "<<b<<'\n';
}

5 並沒有等於 7，因此進入最後區塊，輸出：

1	5 is smaller than 7

聰明的你應該可以發現，else if 是可以無限串接的！也就是說，可以這樣寫。

if(a){
    ...
}
else if(b){
    ...
}
else if(c){
    ...
}
else if(d){
    ...
}

沒加 else if 的後果

讓我們試試將上方程式碼中的 else if 改成 if。

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

int a,b;

int main(){
    cin>>a>>b;
    if(a > b){
        cout<<a<<" is bigger than "<<b<<'\n';
    }
    if(a == b){
        cout<<a<<" is equal to "<<b<<'\n';
    }
    else{
        cout<<a<<" is smaller than "<<b<<'\n';
    }
}

接著執行程式，輸入同樣的 5 7，結果為：

1	5 is smaller than 7

恩，一模一樣，所以沒有差…嗎？

輸入 7 5，結果為：

1 2	7 is bigger than 5 7 is smaller than 5

為什麼？

因為，上方的兩個if，是分開的！

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

int a,b;

int main(){
    cin>>a>>b;
    if(a > b){
        cout<<a<<" is bigger than "<<b<<'\n';
    }



    if(a == b){
        cout<<a<<" is equal to "<<b<<'\n';
    }
    else{
        cout<<a<<" is smaller than "<<b<<'\n';
    }
}

第二段中，那個 if/else 片段的意思是：

如果 a 等於 b，輸出 a is equal to b，否則，輸出 a is smaller than b

因此，程式判斷了 a 不等於 b，所以產生了第二個輸出！

基礎邏輯

> 大於
< 小於
== 等於 (注意，不是=)
!= 不等於
>= 大於等於
<= 小於等於
&& 且
|| 或
! 否

運用這十種組合，搭配上方的 if else，我們終於可以寫出一點自己的東西了！

&&(and) 與 ||(or)

&&(且) 與 ||(或) 在判斷式中的使用法，是連接很多個不同的敘述。例如：

1
2
3

if( a>=5 && a<b ){
    ...
}

意思即為：若 $a \ge 5$ 以及 $a<b$ 都成立的話，就…

1
2
3

if( a>=5 || a<b || a>c){
    ...
}

這句的意思則是，若 $a \ge 5$ 或 $a<b$ 或 $a>c$ 任何一個成立的話，就…

!(not)

!的運用則是，加在一判斷式之前，若判斷式成立則結果為非，若不成立則為是。

簡單來說，把判斷的結果相反就對了

1
2
3

if(!(a>5)){
    ...
}

這句的意思是，如果 $a>5$ 不成立的話，就…

在這個範例裡，這其實等同於：

1
2
3

if(a<=5){
    ...
}

後者明顯好懂許多，因此，好懂也是程式中重要的一環！

來點範例吧！

我們知道一個西元年份是閏年的話，它必須是4的倍數，但如果是 100 的倍數就不閏，但如果它是400的倍數就又是閏年，~~真麻煩~~

因此，要判斷一個西元年分是不是閏年，可以這麼寫：

int year;
cin>>year;
if(year%4==0){
    if(year%100==0){
        if(year%400==0){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    else{
        cout<<"YES\n";
    }
}
else{
    cout<<"NO\n";
}

另一種寫法是

if(year%400==0){
    cout<<"YES\n";
}
else if(year%100==0){
    cout<<"NO\n";
}
else if(year%4==0){
    cout<<"YES\n";
}
else{
    cout<<"NO\n";
}

對於同樣的一個問題，我們可能會產生不同解法，而這就是程式解題的迷人之處！

特別注意

小於/大於不支援超過兩個數字的比較，因此請勿寫成：

1	if(a<=b<=c)

危險的地方是，這個程式碼並不會導致編譯錯誤！
進行運算時，程式首先判斷 a<=b，得到的結果為 true / false。接著，再將其與 c 做比較，因此如 a <= b，會變成：

1	if(true <= c)

而 true 的值為 1，false 為 0。因此程式便判斷 1 <= c 是否成立，至此，已經完全不是原來所想的那樣了。

若要判斷 $a \le b \le c$，應該寫成這樣才是正確的：

1	if(a<=b && b<=c)

練習

條件判斷這個章節，可能是你第一個卡關的地方，有些人需要大量的實際練習才能熟悉，因此這裡提供大量題目，讀者可根據自己狀況進行練習。

★★ TOJ 461

★★★★★ ZJ f312

AC Code

// TOJ 94
#include<iostream>
using namespace std;
int main(){
    int a ;
    cin >> a ;
    if(a >= 3 && a <= 5){
        cout << "Spring!" << endl ;
    }
    else if (a >= 6 && a <= 8){
        cout << "Summer!" << endl ;
    }
    else if (a >= 9 && a <= 11){
        cout << "Autumn!" << endl ;
    }
    else{
        cout << "Winter!" << endl ;
    }
}

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

int main(){
    int a,b;
    cin>>a>>b;
    if(a==1){
        if(b>=8) cout<<"PASS!\n";
        else cout<<"FAIL! You see see you!\n";
    }
    else if(a==2){
        if(b>=9) cout<<"PASS!\n";
        else cout<<"FAIL! You see see you!\n";
    }
    else{
        if(b==10) cout<<"PASS!\n";
        else cout<<"FAIL! You see see you!\n";
    }
    return 0;
}

// TOJ 96
#include<iostream>
using namespace std;

int main(){
    int a,c,ans;
    char b;
    cin >> a >> b >>c;
    if(b=='+'){
        cout <<a<<" + "<<c<<" = "<<(a+c)<<endl;
    }
    else if(b=='-'){
        cout <<a<<" - "<<c<<" = "<<(a-c)<<endl;    
    }
    else if(b=='*'){
        cout <<a<<" * "<<c<<" = "<<(a*c)<<endl;    
    }
    else{
        if(c==0){
            cout <<"ERROR"<<endl; 
        }
        else{
        cout <<a<<" / "<<c<<" = "<<(a/c)<<" ... "<<(a%c)<<endl;
        }
    }
}

// TOJ 102
#include<iostream>
#include<iomanip>
using namespace std;

int main() {
    double a,b;
    char k;
    cin >> a >> k >> b;
    cout << fixed  <<  setprecision(4);
    if(k == '+'){
        cout << a << ' ' << k;
        cout << ' ' << b << " = ";
        cout << a+b << endl;
    }
    else if(k == '-'){
        cout << a << ' ' << k;
        cout << ' ' << b << " = ";
        cout << a-b << endl;
    }
    else if(k == '*'){
        cout << a << ' ' << k;
        cout << ' ' << b << " = ";
        cout << a*b << endl;
    }
    else if(k == '/'){
        if(b == 0){
            cout << "ERROR\n";
            return 0;
            // return 0 表示結束整個程式的意思
        }
        cout << a << ' ' << k;
        cout << ' ' << b << " = ";
        cout << a/b << endl;}
}

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

int main() {
    string a,b,c,d;
    cin>>c>>a;
    cin>>d>>b;
    if(a==b&&c==d)
        cout<<"GOOD"<<"\n";
    else if(a==b||c==d)
        cout<<"=~="<<"\n";
    else
        cout<<"OTZ"<<"\n";
}

// TOJ 535
#include <bits/stdc++.h>
using namespace std;
int main(){
    int s;
    cin >> s ;
    if(s == 100) cout << "S\n";
    else if(s>=90) cout << "A\n";
    else if(s>=80) cout << "B\n";
    else if(s>=70) cout << "C\n";
    else if(s>=60) cout << "D\n";
    else cout << "F\n";
}

// TOJ 538
#include <iostream>
using namespace std;

int main(){
    double math, eng, sci, data, pro, score, tagert;
    cin >> eng >> math >> sci >> data >> pro >> tagert;

    score = (((eng * 1.25) + (math * 2) + sci) / 63.75) * 20 + 0.4 * (pro + data);

    if (score >= tagert){
        cout << "YA\n";
    }
    else{
        cout << "QQ\n";
    }
}

// TOJ 461
#include<iostream>
using namespace std;
int main(){
    double x;
    cin>>x;
    if(x==0||x==180){
        cout<<"2"<<'\n';
    }
    else{
        cout<<"4"<<'\n';
    }
}

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

int a1,b1,c1,a2,b2,c2,n;

int main(){
	cin>>a1>>b1>>c1>>a2>>b2>>c2>>n;
	
	double x = 1.0 * (2 * a2 * n + b2 - b1) / (2 * (a1 + a2));
    // 找到二次函數極值發生的位置，與端點取max
	int ans = -100000000;

	int p = x, l = n-p;
	if(0 <= p && p <= n){
		int ans1 = a1 * p * p + b1 * p + c1 + a2 * l * l + b2 * l + c2;
		if(ans1 > ans) ans = ans1; // ans = max(ans, ans1)
	}

    // 微分後答案不一定是整數，因此要試兩個點
	p++, l--;
	if(0 <= p && p <= n){
		int ans1 = a1 * p * p + b1 * p + c1 + a2 * l * l + b2 * l + c2;
		if(ans1 > ans) ans = ans1;
	}
	
	int ans0 = a2 * n * n + b2 * n + c2 + c1; // 左端點
	int ansn = a1 * n * n + b1 * n + c1 + c2; // 右端點
	if(ans0 > ans) ans = ans0; // ans = max(ans, ans0)
	if(ansn > ans) ans = ansn; // ans = max(ans, ansn)
	cout<<ans<<'\n';
}

0-3 四則運算

發表於 2020-10-26 更新於 2020-11-23

四則運算

在C++裡，四則運算大多就跟平常一樣。也遵從著先乘除後加減、括號先算……等等正常的運算規則。

在進行很大的數字相加/相乘時務必注意，若於運算中之任何時刻超過int可表示的範圍，即使最終答案在int範圍，也會導致overflow而使答案錯誤

overflow的說明

1 2	int a = 5, b = 3; cout << a+b << ' ' << a-b << ' ' << a*b << '\n';

結果：

8 2 15

除法

1 2	int a = 5, b = 3; cout << a/b << '\n';

結果：

會有這樣的結果是因為，5是一個整數，3也是一個整數，整數之間的運算，結果在C++裡只會是整數。

因此，小數點以後的部分被捨棄了。

除以 0

在除以 0 時，程式會產生執行期間錯誤(Runtime Error)，在 Online Judge 上顯示為 RE / Runtime Error / Segmentation fault。請務必注意此情形，並且預先處理掉除數可能為 0 的情況。

如何讓整數之間的運算結果產生小數

你可以在運算時預先乘上 1.0 ，這樣，在進行運算時，數字是以浮點數的方式進行運算，最終結果也自然就是浮點數了。

1 2	int a = 5, b = 3; cout << 1.0*a/b << '\n';

結果：

1.66667

控制小數點以下的輸出位數

從上面的例子，我們可以發現，答案只輸出到小數點後第五位。

若要輸出到小數點後第十位，該怎麼做呢？

#include<iostream>
#include<iomanip>
//#include<bits/stdc++.h> // 萬用標頭檔
using namespace std;

int main(){
    int a = 5, b = 3;
    cout << fixed << setprecision(10) << 1.0*a/b << '\n';
}

結果：

1	1.6666666667

其中，fixed表示的，是小數點以下的意思，因此，若沒有fixed，setprecision(10)代表的，其實是總共輸出十位數字。

fixed與setprecision在iomanip標頭檔中，使用時必須先

1	#include<iomanip>

如使用萬用標頭檔bits/stdc++.h則不須理會。

設定一次輸出位數後，下一次便不需要重新設定，例如：

1
2
3

int a = 5, b = 3;
cout << fixed << setprecision(10) << 1.0*a/b << '\n';
cout << 3.0*a*b/1.24*0.445 << '\n';

結果為：

1 2	1.6666666667 16.1491935484

模運算

若我們要取得 a 除以 b 的餘數，可以這樣寫：

1
2
3

int a, b;
cin>> a >> b;
cout<< a - a/b*b << '\n';

因 $a,b$ 都是整數，因此 $a/b$ 僅會保留整數部分，根據除法原理，$a / b = c … d$ 可改寫為 $a = b * c + d$，其中 $0 \le d < b$。因此，$c$ 就是 $a/b$ 的整數部分，將 $a$ 減去 $b*c$ 後，就得到餘數 $d$ 了！

其實，在C++裡，有個幫你寫好的餘數功能：

1
2
3

int a, b;
cin >> a >> b;
cout << a % b << '\n';

% 的優先次序與乘除法相同，因此，若要取 a+b 除以 c 的餘數，必須這樣寫：

1
2
3

int a, b, c;
cin >> a >> b >> c;
cout << (a + b) % c << '\n';

運算後指派

int a = 5, b = 4, c = 0;
a = a + 1; // 計算 a+1 後 指派給 a，現在 a 是 6
b = a - 1; // 計算 a-1 後 指派給 b，現在 b 是 5
c = a * b; // 計算 a*b 後 指派給c，現在 c 是 30
cout<<a<<b<<c<<'\n';

C++ 中，針對 $a = a + 5$ 之類的操作，有著更簡潔的寫法：

a += 5; // a = a + 5
b -= 2; // b = b - 2
c *= 3; // c = c * 3
d /= 45; // d = d / 45

針對 $a = a + 1$ 之類的操作，還有更簡單的寫法：

1 2	a++; // a += 1 b--; // b -= 1

練習

TOJ 93

TOJ 98

TOJ 522

AC Code (強烈建議自行寫完後再看)

// TOJ 93
#include<iostream>
using namespace std;

int main() {
    int a,b,c;
    cin>>a>>b>>c;
    int s=(a+b)*c/2; // why (a+b)/2*c is wrong???
    cout<<s<<"\n";
}

// TOJ 98
#include<iostream>
using namespace std;

int main() {
    long long a,b,c,d,e,f;
    // 如果用int，會發生什麼？
    a=299792458;
    b=a*60;
    c=b*60;
    d=c*24;
    e=d*7;
    f=d*365;
    
    cout <<"1 Light-second(LS) is "<<a<<" metres.\n";
    cout <<"1 Light-minute(LM) is "<<b<<" metres.\n";
    cout <<"1 Light-hour(LH) is "<<c<<" metres.\n";
    cout <<"1 Light-day(LD) is "<<d<<" metres.\n";
    cout <<"1 Light-week(LW) is "<<e<<" metres.\n";
    cout <<"1 Light-year(LY) is "<<f<<" metres.\n";
}

// TOJ 522
#include <iostream>
using namespace std;

int main() {
    int x;
    cin>>x;
    cout<<x*x%10<<'\n';
}

0-2 基本輸入輸出

發表於 2020-10-26 更新於 2020-11-23

可能不太好看懂的教學

輸入

在以下的程式碼中，宣告了整數a、字元b、浮點數c、與字串d。
並將其讀入。

int a;
char b;
double c;
string d;
cin>>a>>b>>c>>d;

cin的語法很特殊，總之像上面那樣，注意不要打成<<，也不要在中間加入無用空格，像這樣：

1
2
3

//錯誤示範
cin>>a>>" ">>'\n'>>b;
cin<<a;

當然，不一定要將輸入的東西全部擠成一行，可以寫作如下形式，效果相同：

cin>>a;
cin>>b;
cin>>c;
cin>>d;

如果輸入了不合法的東西，程式會有不正常的反應，如：

1 2	int x; cin>>x;

這時，若輸入abc，由於abc並非整數，因此x將不會讀入任何值。

輸出

int a;
char b;
double c;
string d;
cin>>a>>b>>c>>d;
cout<<a<<b<<c<<d;

跟cin語法基本相同，但箭頭相反方向。

注意事項

若用上方程式碼輸入這行，得到的輸出會是什麼呢？

1	45 a 5.25 sfdljkg

答案是：

1	45a5.25sfdljkg

壞掉了嗎？並沒有，那為什麼空白不見了？

原因是cin會自動忽略所有不可見字元，包含空格以及換行字元。

因此，只要確實分離，不論輸入是這樣：

1	45 a 5.25 sfdljkg

這樣：

1	45 a 5.25 sfdljkg

還是這樣：

1
2
3

45  a
 5.25 
 sfdljkg

程式都能夠正確讀取！

cin如何運作

1 2	int x; cin>>x;

若我輸入123abc，程式運行結果會是如何？

答案是：

因此，cin一個整數時，程式會一直讀取直到下一個位置的字元不是數字為止！

因此，若上方的輸入為：

1	45a5.25sfdljkg

首先，整數讀入45後停止，字元讀入一個字元’a’後停止，浮點數讀入5.25後停止，字串讀入至行尾停止。

因此，在這個範例裡，輸出結果跟原來一模一樣！

1	45a5.25sfdljkg

那怎麼輸出空格？

輸出一個空白字元，或者一個含一個空白的字串，接著將其輸出！

int a = 10;
char space = ' ';
int b = 12;
cout<<a<<space<<b<<'\n';

10 12

這麼麻煩嗎？

其實，輸出的東西，不一定要是變數！

1	cout<<10<<' '<<12<<"hello!"<<'\n';

1	10 12 hello!

對比：cin的輸入對象一定要是變數，不然你輸入進來要存在哪裡？

因此，若要以空格分隔上方輸出，上方程式碼可改寫為：

int a;
char b;
double c;
string d;
cin>>a>>b>>c>>d;
cout<<a<<" "<<b<<" "<<c<<" "<<d<<'\n';

練習

TOJ 92

TOJ 519

TOJ 520

再次提醒，行尾要輸出換行字元’\n’！

AC Code

// TOJ 92
#include<iostream>
using namespace std;
string a,b,c;

int main(){
    string a, b, c;
    cin>>a>>b>>c;
    cout<<"Hello, "<<a<<", "<<b<<", and "<<c<<"!\n";
}

// TOJ 519
#include <iostream>
using namespace std;
int a, b;

int main(){
    cin>>a>>b;
    cout << "Do you want to say " << a <<" and " << b <<" ??\n";
}

// TOJ 520
#include <iostream>
using namespace std;
int a,b;

int main() {
    cin>>a>>b;
    cout<<b<<" "<<a<<"\n";
}

備註

有另外一種輸入輸出方法：scanf / printf，與cin/cout功能相同，若有興趣可自行查詢相關資源。

0-1 變數的宣告

發表於 2020-10-23 更新於 2020-11-23

教學文章

變數宣告

int a = 1;
long long b = 2;
char c = 'a';
double d = 2.564;
string e = "ABC";

競程常見資料型態

int
- 最常出現
- 以二進位方式儲存，占 4 個 Byte，32 個 bit
- 因此範圍為 $-2^{31}$ ~ $2^{31}-1$
- 超過會產生不可預期的結果
long long
- 占 8 個 Byte
- 範圍為 $-2^{63}$ ~ $2^{63}-1$
- 運算速度較 int 稍慢
- 你絕對會因為忘記使用它而 WA
char
- 儲存的是字元
- 字元以 ‘’ 括住
- char 與 int 的轉換請見 ASCII TABLE
- 可以使用 int() 得到一個字元的ASCII值
  1
  cout<<int('a')<<'\n';
- 可以使用 char() 得到一個ASCII的值對應的字元
  1
  cout<<char(97)<<'\n';
double
- 儲存非整數時使用
- 不是精準值，存在誤差。原因
long double
- 更精準的double
- 更慢的double
string
- 儲存字串使用
- 字串以 “” 括住
- 也有人會使用 char[] 儲存字串，但 string 方便又好用
- char[] 與 string 在某些時候語法不同，這份教學都會用 string 的語法寫
bool
- 僅表示1(true) 或 0(false)
- 一般用來表示一個東西的狀態(是否活著、是否用過…)
- 通常不會拿來輸入輸出
- 雖可用 int 替代，但會導致程式可讀性下降

注意事項

因誤差極大，請勿於競程中使用 float。
基本上不需使用到 short，需要整數直接用 int 就好
若宣告時未指派值，變數的值不一定是 0，可能是任何數。

指派

在程式語言的世界裡， = 這個符號有著不同的意思。

它代表著的，並非我們日常生活中的等於，而是指派。

因此，當我們寫：

1	int a = 10;

並非表示a等於10，而是表示：

1	a，你從現在開始變成10囉！

因此，以下的程式碼並不存在任何錯誤：

1
2
3

int a = 10;
a = 456;
a = 731;

我只是不斷的將新的值指派給a這個變數而已，沒有問題。

順帶一提，C++中，表示等於的符號是==，在之後的章節會有更進一步的介紹。

型態互轉

有些型態是可以互轉的，例如：

long long x;
int y;
double z;
z = 123.45
y = z;
x = y;

他們都是數字，因此互轉沒有問題！但要注意的是，浮點數在轉換為整數時，小數點以下所有數字會被直接捨去！因此在上方程式碼執行完畢後，y與x的值都是123。

練習

因所有題目都需要輸入/輸出，因此習題合併於下一章節

0-0:Hello World! 標頭檔與命名空間

發表於 2020-10-21 更新於 2020-11-23

Hello World!

我們直接來看一下，要如何在螢幕上輸出 Hello World 吧！

~~學完後，就可以說：我會C++喔~~

#include<iostream>
using namespace std;

int main(){
    cout<<"Hello World!\n";
}

程式應該會輸出：

1	Hello World!

下面，我們就一個一個來看，每一行在做什麼吧！

標頭檔

#include 這句，意思是引入名為 iostream 的標頭檔。

標頭檔wiki

簡單來說，是存放你要使用的功能的地方。

例如，假如你想要使用 cout 這個功能，便需要在程式的開頭加上這行，因為 cout 是 iostream 裡的功能，所以必須 include 後才能使用。

1	#include<iostream>

命名空間

using namespace std 這句，意思是使用名為 std 的命名空間。

教學

若有兩個人同名，我們不知道要如何分辨時，我們可能會說：X年X班的XXX….

在這裡概念是類似的！using namespace std 就是跟程式說，我接下來叫的人，是在 std 這個班級裡，這樣就不用每次叫人都加上班級了！

在 include 後，main 前打上這一段。

1	using namespace std;

若沒有這一行，每次使用 cout 以及其他在 std 命名空間下的功能時，將需要寫成如下形式，十分麻煩。

#include<iostream>

int main(){
    int x,y;
    std::cin>>x>>y;
    std::cout<<"HI\n";
    x = std::min(x,y);
    std::cout<<x<<"\n";
}

main 函式

函式，可以想成一個機器，工作在函式裡執行。之後將有函式的詳細介紹

一個 C++ 程式裡，開始執行的地方，我們叫它 main 函式。

語法是：

1
2
3

int main(){

}

由大括號包覆起來的區塊，就是我們要寫程式的地方！

cout

C++ 裡的輸出指令，cout後面加上<<，再加上你要輸出的東西，就可以將它顯示在螢幕上！

“Hello World” 是一個字串，以雙引號包覆。

‘\n’ 為換行字元，雖然看不到，但可以將輸出換行，在 Online Judge 裡非常重要。

1	cout << "Hello World\n";

這句的意思，就是輸出 Hello World 後換行！

組合

將上面全部拼合在一起，就是我們的第一個 C++ 程式啦。

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"Hello World!\n";
}

複製到自己的 Dev C++ 裡，按下 F11 試試看吧！

之後，自己試著寫一次！

競程上

競程上，我們通常使用萬用標頭檔 bits/stdc++.h，並且使用 std 命名空間。bits/stdc++.h 包含了如 iostream 以及 algorithm 等競程上 99% 你所需要的標頭檔，直接用就對了，namespace std 也是，你需要的所有東西都在裡面了。

練習題

zerojudge d483

AC code

在多數的Online Judge中的共識，是輸出後要換行。且因為輸出是嚴格比對的，即使只少一個換行字元，解答都會被視為完全錯誤。

因此，請記得一定要在輸出結尾加上一個換行符號(“\n”)！

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"hello, world\n";
}

從零到一：那些演算法競賽會用到的基礎語法目錄

發表於 2020-10-21 更新於 2020-12-17

說明

以下為競程中常見的語法，僅列出作者平常會使用的，若我忘記加了某個重要語法，歡迎發PR。

每個語法分別會有其常見程度以及其不可替代程度，以 1 到 5 評分，分數越高表示越常見/不可由其他語法替代，反之則表示越稀少/容易用其他語法替代。

基本上，若只需要打競程，學習本章節中提到的語法便已綽綽有餘。放下你的 C++ 使用手冊，看這篇吧!

注意事項

請務必親自實作每個章節中之內容！在程式學習中，親手實作是最重要的！

下載 Dev-C++

Dev-C++使用說明

陣列

宣告

取值、修改

產生 RE 錯誤

競賽中的慣例

陣列放在全域

開多大？

多維陣列

練習

輸入含空白的字串

getline 與 cin 混用時

cin/cout 加速

練習

AC Code

浮點數運算誤差處理

字元運算

大寫轉小寫

字元比較

字串運算

字串比較

bool的特殊用法

位元運算

and &

or |

xor ^

位元運算的交換律與結合律

xor 特別的地方

練習

AC Code

條件判斷

if

請比較下列程式輸出的異同：

else

else if

沒加 else if 的後果

基礎邏輯

&&(and) 與 ||(or)

!(not)

來點範例吧！

特別注意

練習

AC Code

四則運算

除法

除以 0

如何讓整數之間的運算結果產生小數

控制小數點以下的輸出位數

模運算

運算後指派

練習

AC Code (強烈建議自行寫完後再看)

輸入

輸出

注意事項

cin如何運作

那 怎麼輸出空格？

這麼麻煩嗎？

練習

AC Code

備註

變數宣告

競程常見資料型態

注意事項

指派

型態互轉

練習

Hello World!

標頭檔

命名空間

main 函式

cout

組合

競程上

練習題

AC code

說明

注意事項

那怎麼輸出空格？