資訊讀書會的上課內容及筆記

有任何錯誤歡迎糾正 我好懶
所附程式只是我目前能力認為最簡易且可讀性最佳的

注: 滑鼠移動到 　黑條 　上自動反白，點開

會顯示Subtask詳解，想自己解的自行注意

梁哲豪 dc:flightz#0378

• 競賽程式導論
• $STL\mathrm{與}\mathrm{二}\mathrm{分}\mathrm{搜}$
  最近很忙，忘記更新sor
  

---

上課題目（動態更新）

a013

• You can say that again!

題解: 　使用getline()函式 　

#include <bits/stdc++.h>
using namespace std;
//
int main() {
    string x; //建立名叫"x"的字串
    getline(cin, x); // 輸入整行字串
    cout << x << " " <<x; 
    return 0;
}

a019

• 0 與 1

題解: 　可以使用位元運算或基礎數學運算 　

//位元運算
#include <bits/stdc++.h>
using namespace std;
int main() {
  bool x;
  cin>> x;
  cout<< !x; //0的相反=1 1的相反=0
  return 0;
}

a020

• ㄑㄧˊ 數？

題解: 　使用 %2 來判斷奇數偶數 　

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin >> x;
    if(x%2==0) //判斷除以二之餘數
    {
        cout << "Even";
    }
    else
    {
        cout << "Odd";
    }
    return 0;
}

進階寫法

#include<bits/stdc++.h>
using namespace std;
int main(){
    int x;
    cin>>x;
    cout<<((x&1)?"Even":"Odd")<<'\n';
    return 0;
}

a023

• 文文的求婚–續集 (1 行版)

題解: 　若把以4之餘數當第一個判斷,那不就輪不到 100or400 了嗎?? 　

這是斜咖做法,你們絕對想的到更好的方法

#include <bits/stdc++.h>
using namespace std;
int main() {
   int x;
   while(cin>>x)
   if(x%400==0) 
   {
       cout<<"a leap year";
   }
   else if(x%100==0)
   {
       cout<<"a normal year";
   }
   else if(x%4==0)
   {
       cout<<"a leap year";
   }
   else
   {
       cout<<"a normal year";
   }
    return 0;
}

a026

• 文文的求婚–續集 (0 尾版)

題解: 　使用while迴圈, 在輸入為0時結束程式 　

#include <bits/stdc++.h>
using namespace std;
int main() {
   int x, y, i;
   while(cin>>x)
   {
       if(x==0) //結束
   {
       break;
   }
       else if(x%400==0)
   {
       cout<<"a leap year"<<endl;
   }
       else if(x%100==0)
   {  
       cout<<"a normal year"<<endl;
   }
       else if(x%4==0)
   {
       cout<<"a leap year"<<endl;
   }
       else
   {
       cout<<"a normal year"<<endl;
   }
   }
    return 0;
}

註:有更簡單,更好的做法,之後應該會教,帶這是用來練習while的

a035

• 伏林的三角地

題解: 　使用海龍公式 　

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, y, z, s;
    cin >> x >> y >> z;
    s=(x+y+z)/2;
    cout<<s*(s-x)*(s-y)*(s-z);
    return 0;
}

a431

• 數字三角形

題解: 　多重for迴圈的控制及使用 　

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin>>x;
    for(int i=1;i<=x;i++) {
        for(int t=i;t>0;t--) {
            cout<<i;
        }
        cout<<'\n';
    }
    return 0;
}

a442

• 迴文

題解: 　sting的語法 　

從最前面跟最後面開始
判斷是不是一樣
之後往中間縮

#include <bits/stdc++.h>
using namespace std;
signed main() {
	fast;
	string s;
	cin>>s;
	int l=0,r=s.size()-1;
	bool ans=true;
	while(l<r){
		if(s[l]!=s[r]){
			ans=false;
			break;
		}
		l++,r--;
	}
	cout<<(ans?"YES\n":"NO\n");
	return 0;
}

a441

• 倒背如流

題解: 　sting的語法 　

可以看看一個函式叫做reverse()

#include <bits/stdc++.h>
using namespace std;
signed main() {
    string s;
    cin>>s;
    int len=s.size()-1;
    for(;len>=0;len--) cout<<s[len];
    return 0;
}

---

作業較困難題目（動態更新）

a097

• 完全奇數判斷

題解: 　基本語法 　

就是要把數字的每一項分解再進行運算

• 數學解

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int x;
    bool k; //用布林來紀錄是否有偶數
    while(cin>>x) {
        k=0; 
        while(x!=0) {
            if(!((x%10)&1)) { //!(x%10是奇數)->即偶數
                k=1;
                break;
            }
            x/=10;
        }
        if(k) cout<<"NO\n"; //k=1(ture)就執行
        else cout<<"YES\n";
    }
    return 0;
}

再來用字串解解看

#include <bits/stdc++.h>
using namespace std;
signed main() {
	string s;
	while(cin>>s){
		bool ans=true;
		for(int i=0;i<s.size();i++){
			if(!((s[i]-'0')&1)){  //判斷是不是偶數
				ans=false;
				break;
			}
		}
		cout<<(ans?"YES\n":"NO\n");  //ans是true輸出YES反之輸出NO
	}
	return 0;
}```

a429

• 質數判斷

題解: 　任意正整數且非質數N，其最小非1的正整數因數必小於等於根號N 最好的例子就是9 　

試除法 這個可以去看看

可以在最一開始判斷是否為偶數，可以減少迴圈的執行次數，進而壓縮時間

#include<bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    if(N==2) {           //2:質數
        cout << "YES";
        return 0;
    }
    if(N%2==0) {         //非2偶數：不是質數
        cout << "NO";
        return 0;
    }
    for(int i=3;i*i<=N;i+=2) { //由3開始，判斷每一個奇數是否為N的因數
        if(N%i==0) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

a430

• 巧克力工廠

題解: 　多重for迴圈的控制及使用 　

根據題意,可以很明顯得知在輸入=

$W,H$ 時
輸出高為

$H$,寬為

$W$由#組成的長方形

#include<bits/stdc++.h>
using namespace std;
int main() {
	int W, H;
    cin >> W >> H;
    for(int i=0;i<H;i++) {  //from 0 to H-1; H-1 - 0 +1 = H
        for(int t=0;t<W;t++) { //same
            cout<<"#";
        }
        cout<<'\n'; //line-changing
    }
	return 0;
}

備註 : C++中的換行符號為endl及\n,但\n的效率更高

a444

• 編碼破解

題解: 　字串與字元陣列應用 　

題目要我們把所有字元往前推兩格
由於

$AB$會變成

$YZ$ 就特判為

$AB$的情況
後面直接做

$-2$就好了

#include<bits/stdc++.h>
using namespace std;
signed main() {
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='B'){
			cout<<"Z";
		}
		else if(s[i]=='A'){
			cout<<"Y";
		}
		else{
			s[i]-=2;
			cout<<s[i];
		}
	}
	return 0;
}

備註 : string可以看成char陣列 char可以做加減

---

為甚麼是C++

C++介紹

• C++是甚麼?

程式語言（英語：programming language），是用來定義電腦程式的形式語言。它是一種被標準化的交流技巧，用來向電腦發出指令，一種能夠讓程式設計師準確地定義電腦所需要使用資料的電腦語言，並精確地定義在不同情況下所應當採取的行動。

簡單來說就是可以透過程式語言對電腦下達指令，讓電腦知道它要如何執行。
。

• C++程式開發軟體

1. Code::Blocks
   Code::Blocks是一個免費、針對C/C++設計的整合開發環境，操作簡單，但Code::Blocks本身不包含編譯器，需要另外安裝。

2. Visual Studio code
   Visual Studio code是一款微軟的免費整合開發環境，使用時對硬體的消耗相對Visual Studio小，也有許多插件可用，很受競程選手歡迎。但不包含編譯器，需自行安裝。

3. 軟體安裝參考網站
   Code::Blocks
   Visual Studio code&&環境變數設定

---

C++基礎語法介紹

標頭檔及程式基礎架構

• 引入標頭檔&&<bits/stdc++.h>的介紹

code

#include <iostream> 標準標頭檔
#include <bits/stdc++.h> 萬用標頭檔

參考網址

---

變數宣告

在使用變數前，要先告訴電腦你要創造一個變數，這個動作叫做宣告。

• 宣告格式：變數型別 變數名稱;

例如 int x; 就是宣告一個整數變數x。
變數可分為

1. 整數-int
2. 浮點數-double
3. 字元-char
4. 字串-string

int x, y; ////宣告兩個整數
double a = 3.14159;  //宣告一個浮點數=3.14159
char b = 'A';  //宣告一個字元=A
string s="hello";  //宣告一串字串

浮點數介紹

---

輸入輸出

• 標準輸入輸出

輸入-cin
遇空格或是換行即結束

輸出-cout
在需要換行的地方可以輸出 endl 或是 '\n'。

code

int x, y; ////宣告兩個整數
double a = 3.14159;  //宣告一個浮點數=3.14159
cin >> x ; //輸入 x (5)
cout << "hello world " << x << " " << a ; 
//輸出 = hello world 5 3.14159

※ 不可使用沒設定變數值之變數（會是亂數）

補充

• 控制輸出位置精準度(精準度)
• 輸入時不要被空格split

---

運算子

在C++中，可以使用運算子來對變數或數值做運算。以下介紹幾種常用的運算子，同時也會提到當兩種不同型別的變數進行運算時，電腦會如何判斷要使用哪個型別，以及如何做強制型別轉換。

1. 指定運算子

使用等於=符號表示，會先對等號右邊進行運算，再將結果指定給左邊的變數。這個等號跟數學的等號不太一樣，需要花一點時間習慣。

int x;
x = 2 + 1; //x = 3 （//是註解，在C++程式編譯時不會被編譯）
x = x + 1; //x = 4，因為是先計算右邊的x + 1 = 3 + 1，再存到左邊的x

2. 算術運算子

算術運算子就是數學的運算符號，具有跟數學四則運算一樣，先乘除後加減的規則。

• 加法 +

int x = 3 + 2;

• 減法 -

int x = 10 - 5;

• 遞增 ++
  遞增可分成前置++x和後置x++，它們的不同在於，前置的值會是運算之後的值，後置的值則是運算之前的值。可以看成前置++x是先加再用，而後置x++是先用再加。

int x = 0;
cout << ++x << endl;// x = 1, 輸出1
x=0;
cout << x++ << endl; // x = 1, 輸出0

• 遞減 --
  與遞增相同，一樣有分成前置和後置。

int x = 0;
cout << --x << endl; // x = -1, 輸出-1
x=0;
cout << x-- << endl; // x = -1, 輸出0

• 乘法 *

int x = 2 + 3 * 4; //x = 14, 先乘除後加減

• 除法 /
  兩個整數在做運算時， 當對兩個整數做除法/，會自行向下取整，也就是取商。

int x = 7 / 2;       // x = 3
float y = 1.0 / 2.0; // y = 0.5

• 取餘數 %

int x = 5 % 2; // x = 1

• 括號 ()
  在C++中，一樣可以使用括號來標示優先計算的部分，且都是使用小括號()。

cout << (1 + 2) * 3 << endl;           //輸出9
cout << 2 * ((1 + 2) * 3 + 2) << endl; //輸出22

3. 比較運算子
在比較運算中只會有true或 false 兩種結果。

• <小於、>大於
• <=小於等於、>=大於等於
• == 相等 、 != 不相等
  （相等是==，而=是指定運算子，意義跟用途都不同，要小心不要搞混。）

4. 邏輯運算子
在邏輯運算中只會有 true 或 false 兩種結果。

• 邏輯AND &&
  A、B皆為 true 時， A && B 為true，
  否則 A && B 為 false。

A && B	B : true	B : false
A : true	true	false
A : false	false	false

• 邏輯OR ||
  A、B其中一個為true時，A||B為true，兩者皆為false時為false。

A || B	B : true	B : false
A : true	true	true
A : false	true	false

• 邏輯NOT !
  A為true時，!A為false，A為false時，!A為true。

!A	A : true	A : false
result	false	true

---

強制型別轉換

強制型別轉換是在程式運算過程中，對型別做強制的轉換。
轉換格式：

(轉換型別) 變數;
(轉換型別) 數值;

例如要將數字轉為字元的編號：

int x = 3;
cout << (double)x / 2 << endl; //輸出 1.5
cout << (char)97 << endl;      //輸出「a」, 97是字元'a'在ASCII碼中的編號

---

選擇結構

選擇結構在C++ 中用於判斷條件並決定要執行哪些程式，C++使用if、else和else if作為選擇結構的語法，接下來會一個一個介紹它們的用法。

if

if的使用格式如下：

if(判斷條件){
    判斷條件成立時執行的程式;
}

if後的小括號用於放判斷式，如果判斷式運算結果為true，就會執行大括號內的程式碼。要注意大括號後不需要加分號。

以下是一個用於判斷你輸入的數是否大於100的程式，如果大於100，將輸出「x大於100」：

int x;
cin >> x;
if(x > 100){
    cout << x << "大於100" << endl;
}

else

若在if判斷為false，就可能會需要處理條件不成立的狀況，這時就會用到else。else需要接在if或else if後，else if會在後面提到。
以下是else的用法：

if(判斷條件){
    判斷條件成立時執行的程式;
}else{
    判斷條件不成立時執行的程式;
}

以下是一個用於判斷輸入的數是否大於100的程式。如果大於100，將輸出「x大於100」；否則輸出「x小於等於100」：

int x;
cin >> x;
if(x > 100){
    cout << x << "大於100" << endl;
}else{
    cout << x << "小於等於100" << endl;
}

else if

當你需要多個選擇時，你可以使用else if來達成，else if可以接在if或else if後面，以下是else if的用法：

if(判斷條件1){
    判斷條件1成立時執行的程式;
}else if(判斷條件2){
    判斷條件2成立時執行的程式;
}
else{
    判斷條件2不成立時執行的程式;
}

要特別注意的是，在整個選擇結構中，如果在其中一項成立，它就會跳過結構中後面的部分。
以下是一個用於判斷輸入的數是否大於100的程式。如果x大於100，將輸出「x大於100」；如果x等於100，則輸出「x等於100」；否則輸出「x小於100」：

int x;
cin >> x;
if(x > 100){
    cout << x << "大於100" << endl;
}else if(x == 100){
    cout << x << "等於100" << endl;
}else{
    cout << x << "小於100" << endl;
}

迴圈

當你需要重複執行一樣的程式時，可以使用迴圈反覆執行相同的程式。在C++中，迴圈分為兩種：for迴圈和while迴圈。

for

for迴圈通常用在需要重複的次數已知時使用，它的格式如下：

for(一開始要執行的動作; 迴圈執行條件; 每次迴圈跑完後要執行的動作){
    迴圈內的程式;
}

在for迴圈的大括號後不需要加分號。
比較常見的程式寫法如下：

for(int i = 0; i < 執行次數; i++){
    //迴圈的內容
}

以下是一個可以輸出0 ~ n - 1的程式：

int n;
cin >> n;
for(int i = 0; i < n; i++){
    cout << i << ' ';
}
cout << endl;

while

while迴圈的結構比for迴圈簡單，只需要一個迴圈執行條件，格式如下：

while(判斷條件){
    迴圈內的程式;
}

這是一個計算輸入數字是幾位數的程式：

int x;
cin >> x;
int cnt = 0;
while(x > 0){
    cnt++;
    x = x / 10;
}
cout << cnt << endl;

while迴圈還有另一種寫法，是使用do-while。

do{
    迴圈內容
}while(執行條件);

它跟while迴圈不同的地方是，while迴圈會在一開始就檢查是否執行迴圈，而do-while則是先執行過第一次之後再判斷是否繼續執行迴圈。還有要注意在do-while的大括號後需要加上分號，while迴圈則不用。

break

break是迴圈的一個特別的指令，只能在迴圈內使用。當執行到break時，電腦會直接結束break所屬的迴圈。
以下是一個輸入數字n，輸出0 ~ n - 1的程式:

int n;
cin >> n;
int now = 0;
while(true){
    if(now >= n)
        break;
    cout << now++ << ' ';
}

continue

continue也是迴圈的指令，當執行到continue時他會跳過迴圈剩下的部分，直接回到判斷迴圈條件的步驟。
以下是一個輸入數字n，輸出0 ~ n - 1的偶數的程式:

int n;
cin >> n;
for(int i = 0; i < n; i++){
    if(i % 2 == 1)
        continue;
    cout << i << '\n';
}

陣列

陣列是多個相同資料型別的變數所組成的，陣列中的每個元素都是一個變數。它的宣告格式如下：

變數型別 陣列名稱[陣列大小];  //陣列大小須為正整數

當要使用時，用中括號［］加上索引值陣列名稱[索引值]來表示陣列的某個變數。要特別注意的是，陣列的第一個位置索引值是0，以下是一些簡單的操作方式：

int a[5];
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;

陣列和迴圈

陣列經常搭配迴圈一起使用，以下是一個簡單的程式：

int a[10];
for(int i = 0; i < 10; i++){
    cin >> a[i];
}

---

結語

謝謝看到這裡的各位,希望你們都能在資訊界大放異彩,用你們強大的電壓電死我（ 怕