tags: `資訊科技`

程式設計(使用C++、ZeroJudge)

零、評量、學習歷程

1. 評量方式

上課基本練習(遲交期限：1週) 50%
期中上機考 20%
- 時間：三、迴圈教完後一週
- 上機考時網路會斷線，沒有任何參考資料，請每個子單元至少完成 1~2 題作業，熟練基本語法。
- 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少寫 1~2 題作業，上機考才會比較保險。
期末上機考(六、函式教完後一週) 20%
- 時間：六、函式教完後一週或倒數第 2 週。
解題報告 10%
- 想高分或上機考考差的同學請保握機會。
- 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。
- 中午電腦教室除考前1週外有開放時間，沒電腦、沒網路做作業的同學請善加利用。
- 繳交期限：
  - 最後一週上課前1天。接近期末考，最慢在期中上機考後就要開始動工。
- 分數：
  - 每一題10分，上限120分(12題)。
  - 每個單元至多可放 2 題
    - 不可以都寫同一單元的題目
    - 題號劃掉的太簡單了，只是用來增加信心，不能放入解題報告。
- 報告格式：
  - 第1頁為解題目錄(單元、題號、題目、頁碼)。
  - 每題的子標題為
    (1) 單元、題號、題目、題目簡述
    (2) 解題動態、評分結果截圖
    (3) 解題思路
    (4) 程式碼
    (5) 反思(遇到的錯誤、修正的地方、更好的方法…)
    (6) 錯誤程式碼
- 檢核方式：
  - 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。
  - 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。
- 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。
- 如果對寫程式有興趣並要參加APCS檢定，下學期多元選修可以選修APCS(大學程式設計先修檢測)程式實作，挑選標準主要為ZJ的解題數(請寫在多元選修意向書裏)。

2. TOI推廣計畫-線上練習賽

成績計算：分數/100直接加在總成績。
上學期10、11、12月，下學期3、4、5月，最後一週。
星期一08:00 ～星期五20:00。90分鐘。
證書

3. APCS

實作級分*2，直接加在總成績。
3級分免上機考，上機考成績為100。
4級分以上者，一切皆免，學期成績直接算100。

4. 學習歷程檔案(修課記錄、課程學習成果)

最後一週上課結束前如果認證完成，學期總成績加分。
撰寫「課程學習成果」參考資源。

5. 基礎教學網站

基礎程式設計 - C與C++簡報、影片

6. SoloLearn C++ Tutorial

全部學完可拿到證書(額外加分)。

7. 軟體

一、輸出與輸入、變數、運算式與運算子

1. 輸出與輸入

EX_1_1：d483: hello, world

快速鍵
Ctrl+滾輪：放大、縮小
F9：Build and run
Ctrl+a：全選
Ctrl+c：複製
Ctrl+v：貼上
Ctrl+x：剪下

EX_1_2：a001: 哈囉

int main()
{
    ~ // 變數宣告
    while(cin >> ~) //不需要加「;」
    {
        cout << ~ << endl;
    }
    return 0;
}

快速鍵
Shift+方向鍵、Home、End：選取程式
執行完的測試視窗要關閉，才能再次執行。

2. 變數型態

常用型態	意義	範圍
int	整數	-2147483648~2147483647
long long int	長整數	-2⁶³ ~ 2⁶³-1
float	單精度浮點數(小數)	±1.5x10⁻⁴⁵ ~ ±3.4x10³⁸
double	雙精度浮點數(小數)	±5.0×10⁻³²⁴ ~ ±1.7×10³⁰⁸
char	字元	'A'
string	字串	"Hello"
bool	布林	true、false

3. 變數宣告

int math=80;             // 資料型態 變數名稱;
double pi=3.14159265359; // 資料型態 變數名稱=初值;
int sum,ave,rank;        // 資料型態 變數名稱1,變數名稱2,變數名稱3...;

EX_1_3：a002: 簡易加法

cin >> a,b; 是錯誤的語法。
使用線上軟體或再開一個專案(homework)寫作業，未寫完存雲端。

EX_1_4：d489: 伏林的三角地

以海龍公式求三角形面積。
「*」不可省略。
先乘除後加減，可用小括號改變運算順序。
// 註解
需除錯時，可將變數印出來看。
cin >> a >> b >> c >> s → error，s不用輸入

~~d049: 中華民國萬歲！~~

a861: 1. Secure the Perimeter

c379: 成為出題者

d461: 班際籃球賽

d053: 10970 - Big Chocolate

4. 算數運算子

算數運算子	意義	備註
+	加
-	減
*	乘
/	除
%	取餘數
++	遞增	i++ 即 i=i+1
--	遞減	i-- 即 i=i-1

EX_1_5：d050: 妳那裡現在幾點了？

EX_1_6：d485: 我愛偶數

將 a 調整為後一個偶數， b 為前一個偶數，計算等差數列項數。
a 偶數 a=a+0，a 奇數 a=a+1
- a=a+a%2
複合指定運算子(a=a+5 → a+=5)

EX_1_7：d051: 糟糕，我發燒了！

(f-32)*5/9
整數除法、浮點數除法：5/2、5.0/2。
型態轉換(double)。
C++小數點位數控制。
f，c 全部宣告為 double？
- double 不可 %。

#include <iomanip>

cout << fixed << setprecision(3) << ... ;
// setprecision(n) 會將輸出的數值控制為 n 位數，如果加上 fixed 表示只控制小數點以下的位數。

d073: 分組報告

/ 整數除法

d827: 買鉛筆

b757: 頸美椰子樹

double
/

a862: 2. My Dear Friend VIR

double
/
C++小數點位數控制。

f651: 開關燈

/ 整數除法
觀察n=1~10，找規律。類似d073。

5. 關係運算子

關係運算子	意義	備註
==	等於	=是指派，==是判斷是否相等
!=	不等於
>	大於
>=	大於等於
<	小於
<=	小於等於
Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More → a < b < c 要寫成 a < b && b < c

6. 邏輯運算子

邏輯運算子	意義	備註
&&	and
\|\|	or
!	not

EX_1_8：d063: 0 與 1

EX_1_9：e343: BMI 計算

運算式中沒有中、大括號，通通都用小括號。
型態轉換。
C++小數點位數控制。
需除錯時，可將變數印出來看。

二、選擇

1. if 條件式語法

if(條件)
{
    條件「成立」時的程式碼
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

if()後不能加「;」

EX_2_1：a012: 10055 - Hashmat the Brave Warrior

long long
Q：cout << ans << endl; 放在if{ }內會發生什麼問題？

~~a799: 正值國~~

d068: 該減肥了！

b682: 2. 同學早安

提示
將時間全部轉成分鐘會比較好做，分鐘的時間差以/、%轉回小時、分。
因為校長最久只會站23小時59分，所以如果開始時間大於結束時間，表示站隔夜，結束時間要多加1440。

h658: 捕魚 (Fishing)

d(距離)及minD(最小距離)要宣告為double，minD的初值可假設為一個比可能最大值還要大的值(如1000)。
開根號用sqrt()，需含入 cmath 標頭檔，d=sqrt((x-a)*(x-a)+(y-b)*(y-b));
讀入每個魚群的中心座標，計算魚夫和魚群的距離，如果比目前的最小距離小，則記錄此時的最小距離和座標。

2. if~else 語法

if(條件)
{
    條件「成立」時的程式碼
}
else
{
    條件「不成立」時的程式碼
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

養成縮排的好習慣：大括號 { } 內的程式碼以Tab鍵向右縮排，可以增加程式碼的可讀性，並方便除錯。

EX_2_2：d064: ㄑㄧˊ 數？

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

常用運算子的優先順序

EX_2_3：d066: 上學去吧！

7<=h<17
→ h>=7 && h<17
→ h>=7 && m>=30 && h<17，幾點會造成錯誤？
→ (h>=8 && h<17) || (7點的狀況)
&&、||

b877: 我是電視迷

f373: 週年慶 Anniversary

題目簡述
- 天天百貨（編號0）消費滿2000折200，琪琪百貨（編號1）消費滿1000折100。
- 輸入一正整數 N （0 ≦ N ≦ 10000），代表預計花費的金額，請問去那個百貨可以得到最好的優惠（如果優惠後的價格一樣，預設去天天百貨）。
- 輸出折扣後的金額以及百貨的編號。
分別計算兩百貨折扣後的金額，比較大小輸出。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

如果測資的第一行有一個整數t，代表測試的筆數，要用以下的寫法。












cin >> t;
while(t>0)
{
    ~
    t--;
}
或
cin >> t;
while(t--)
{
    ~
}

e948: 1. 基礎代謝率 (BMR Calculation)

輸入的第一行有一個整數n，代表測試筆數。while(n–) // 兩個減號，寫法參考
C++小數點位數控制。

#include <iomanip>

cout << fixed << setprecision(2);

f043: 1. 小豪的回家作業 (Homework)

給定兩整數R、A，求出A＋B＝R的B值後輸出。
如果R＝A，則先將A-3再求B。
A、B小的寫在算式的前面。

3. 巢狀 if 語法

if(條件1)
{
    if(條件2)
    {
        條件1「成立」，且條件2「成立」時的程式碼
    }
    else
    {
        條件1「成立」，且條件2「不成立」時的程式碼
    }
}
else
{
    條件1「不成立」時程式碼
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

if或else的大括號{ }內，都可再增加條件式。

EX_2_4：d058: BASIC 的 SGN 函數

if(n>0) vs. if(n>=0)

EX_2_5：a006: 一元二次方程式

開根號用sqrt()，需含入 cmath 標頭檔。
d=0時，x1還是要計算過程。執行時，不會去執行不符合條件的程式碼。
F8除錯示範。
Q：x1、x2放在d後面計算可以嗎？負數開根號？

a003: 兩光法師占卜術

d065: 三人行必有我師

f165: 棒棒糖事件

判斷棒棒糖數除以小朋友人數的餘數r是否為0，當r=0時，輸出「OK!」，反之輸出r。
小朋友人數可能為0，不會搶成一團，所以蝸牛老師不需吃下任何棒棒糖，輸出「OK!」。
先排除小朋友人數為0的狀況，不然「%」運算會錯誤。

b899: 2. 物品探測

分別計算三點間的距離，最長的為正方形的對角線。
正方形四點 A、B、C、D，假設 A、C 為對角，則 D = A + C - B。

4. 多重選擇 if~else if~else 語法

if(條件1)
{
    條件1「成立」時程式碼區塊
}
else if(條件2)
{
    條件1「不成立」，且條件2「成立」時的程式碼
}
else if(條件3)
{
    條件1、2「不成立」，且條件3「成立」時的程式碼
}
...
else
{
    上述條件都「不成立」時的程式碼
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

else if()可視需要增加。

EX_2_6：d460: 山六九之旅

f337: 同樂會 (Party)

c382: 加減乘除

要宣告一個字元變數(char)讀「+ - * /」，比較時，字元前後要有單引號。

b676: 63萬勞工苦輪班不像人像機器

a053: Sagit's 計分程式

a244: 新手訓練 ~ for + if

long long
while(n–)

e972: 1. 貨幣轉換 (Currency)

變數可設為double。
先將預算轉成目的地的幣值。
依「預算<花費」，「預算-花費<0.05」(0.00以字串列印->"0.00")，「預算>花費」，分別輸出。
C++小數點位數控制。

#include <iomanip>

cout << fixed << setprecision(2) << money-m;

三、迴圈

1. for 迴圈語法

for(變數初值; 條件判斷; 改變量)
{
    程式碼
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

除錯練習
(1) Build and run (F9)後發現錯誤
(2) 設中斷點
(3) Debug (F8) (程式會執行到中斷點後停止，讓我們可以按 F7 逐行執行)
(4) Debugging windows/Watches
(5) Next line (F7) (行號旁出現黃色箭頭開始按 F7，黃色箭頭的這一行表示按 F7 後要執行)
(6) Stop debugger

EX_3_1：d498: 我不說髒話

int i;
for(i=1; ...)
{
    
}

Q1：如果改變量寫i+1，會發生什麼事，練習除錯(F8)。

i=i+1 或 i+=1 或 i++
i+1不會改到i

Q2：n輸入10，以除錯(F8)看流程，當n=10時，下一行會往上或往下執行？i 最後的值為？
Q3：n=10時，i+=3(i=i+3)，會印出幾次字串， i 最後的值為？

EX_3_2：d490: 我也愛偶數
Q1：先完成 a+…+b，但答案會錯誤？

先將 i、sum 印出來看，或除錯(F8)。
初值歸零

Q2：初值歸零後，第2次答案會錯誤？

變數範圍：int sum=0; // 宣告在while迴圈內
區塊變數：for(int i=a;)

~~b970: 我不說髒話 (續)~~

d046: 文文採西瓜

d786: 三、平均值

每筆測資sum要歸零。

c005: 10300 - Ecological Premium

long long
運算式可先化簡避免除法誤差。

f708: 蟲蟲危機 (Insect)

題目簡述
- 第一行有整數 M 和 N (1 ≤ M ≤ 2000, 1 ≤ N ≤ 2000) 代表螞蟻和蚱蜢的總數
- 第二行有 M 個數字表示螞蟻的身高 Ai (1 ≤ Ai ≤ 1000, 1 ≤ i ≤M)
- 第三行有 N 個數字表示蚱蜢的身高 Gi (1 ≤ Gi ≤ 1000, 1 ≤ i ≤ N)
- 若螞蟻的數量比蚱蜢多且螞蟻的總身高比蚱蜢高，螞蟻們才敢決定跟蚱蜢打一架爭，輸出 Yes，否則輸出 No。

f338: 后羿射日(Archer)

j178: 手遊廣告 (Advertisement)

break：強制跳出「整個」迴圈。

f312: 1.人力分配

以for迴圈枚舉所有可能的工人分配方法。
求最大值可用max函式或if。

f605: 1. 購買力

找出3物品最大值和最小值，可使用if或max、min函式。
max 若要傳入三個以上的參數，須用大括號包住，並含入 algorithm 標頭檔。

c299: 1. 連號或不連號

輸入數列時，找出其最大值和最小值，可使用if或max、min函式。
最大-最小+1==n，表示這個數列是連續的。

d660: 11764 - Jumping Mario

prev=now

2. 巢狀迴圈語法

for(變數1初值;條件1判斷;改變量)
{
    for(變數2初值;條件2判斷;改變量)
    {
        程式碼
    }
}
Q：在日常生活中，有什麼事像巢狀迴圈的概念？

EX_3_3：c418: Bert的三角形 (1)

EX_3_4：c419: Bert的三角形 (2)

除錯練習：內圈若寫j–會如何？

c420: Bert的三角形 (3)

f063: The Strongest Chain

巢狀迴圈。
求每條鏈子最小值中，找出最大值。

c013: 00488-Triangle Wave

巢狀迴圈。
下半部 for(k=A-1;k>0;k--)

3. while 迴圈語法

while(條件判斷)    // 條件為「真」的時候繼續執行
{
    程式碼
}












for(int i=1;i<=5;i++)
{
    cout << "hello ";
}
cout << endl;

int i=1;
while(i<=5)
{
    cout << "hello ";
    i++;
}

EX_3_5：d189: 11150 - Cola

請用 while 模擬換瓶過程，不可以直接套公式。
以除錯(F8)看換瓶過程，最後剩 2 空瓶，可借 1 空瓶多換 1 瓶。











int sum=n;

while()
{
    
}

if(n==2)
{
    sum++;
}

題目先借瓶，什麼狀況需要借？
→ 不管需不需要都借。為什麼 n=9 時，不需要借也借，卻不會錯誤。(F8)






int sum=n;
n++;
while()
{
    
}

EX_3_6：a038: 數字翻轉

前面有 0 的話應消除。如50200 不是輸出 00205，而是205。
0要輸出0。為何會TLE？除錯(F8)練習。

迴圈中斷

break：強制跳出「整個」迴圈。
continue：強制跳出「此次」迴圈，繼續進入下一次圈。








for(int i=1;i<=10;i++)
{
    if(i==5)
    {
        break; // continue;
    }
    cout << i << " ";
}

c079: 10346 - Peter's Smokes

d570: 神龍見首不見尾

f070: 1. 韓信點兵 (HanXin)

因為答案很小，暴力解即可。
while(true)，從1開始測，輸出符合條件的值。

c350: “綠白黃” 四校聯課

ans+=(n/k)*w; // 每次新換的電話號碼
n-=(n/k)*(k-w); // 因為 k > w，所以可以看成每一次的交換(k換w)，新號碼會減少 (k-w) 個。

4. do..while 迴圈語法

do
{
    程式碼
}while(條件判斷);  // 條件為「真」的時候繼續執行

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

do while()後要加分號！

EX_3_7：d356: NOIP2002 1.级数求和

型別轉換。
浮點數誤差(float->double)。

cout << –i << endl;

int a=1,b;
b=a++;
b=++a;
cout << a << " " << b << endl;

EX_3_8：a149: 乘乘樂

假設 n 固定只有3位數，練習求百位、十位、個位數字。
mul*=n%10 vs. mul=mul*n%10 (錯誤)
常用運算子的優先順序
以while迴圈改寫會發生什麼錯誤？

a215: 明明愛數數

c561: Bert 愛搗蛋

將數字反轉，記錄最大值。
將數值反轉的方法，假設 a為原數值，rvs為反轉後的數值(預設值為 0)
rvs=rvs*10+(a%10);
a/=10; // 讓個位數消失

f374: 分組 Grouping

四、陣列

1. 陣列宣告

int a[5];             // 宣告一個大小為5的int陣列
a[0]=80;              // 陣列的索引值由0開始
a[5]=90;              // 錯誤，索引值0~4
int a[5]={1,3,5,7,9}; // 宣告陣列時設定初值
int a[5]={1};         // a[0]初值1，其餘預設為0

for(int i=0;i<5;i++)  // 以 for 迴圈來控制陣列的 index
    cin >> a[i];

// 1-based indexing
int a[6];
for(int i=1;i<=5;i++)  // 以 for 迴圈來控制陣列的 index
    cin >> a[i];

int a2d[4][2];        // 宣告二維陣列(多維陣列)
int a2d[4][2]={{1,2},{3,4},{5,6},{7,8}};

Q：如何建立可以儲存班上期中考成績的二維陣列？
// a2d[r][c]表示第 r 列，第 c 欄的值(類似英文書寫習慣)

EX_4_1：b127: 會議中心（Room）

費式數列

EX_4_2：a693: 吞食天地

陣列宣告時，大小請直接指定為題目給的最大範圍，避免用變數。

int n;
while(cin >> n >> m)
{
    int food[n];      // 避免使用，編譯器不一定支援。
    int food[100005]; 
}

每次都重算會TLE。檔名：a693(TLE)
時間複雜度

前綴和，不要用爆力法

for(int i=1;i<=n;i++)  // 對每個idx 
{
    for(int j=1;j<=i;j++) // 從頭開始加到此idx
    {
        pfx[i]+=food[j]
    }
}

i=0時，food[i]=food[i-1]+t 會錯誤，所以改從index 1 開始放前綴和。
- 1-based indexing

EX_4_3：i071: 風景 (Landscape)

1-based indexing
從小明家往左、往右檢查>小明家樓高的數量，錯誤的原因為？
以變數(LMax、RMax)記錄小明家左邊、右邊最高樓高(初值為小明家樓高)。從小明家往左、往右檢查，如果檢查的樓高>LMax、RMax，則答案+1，並調整LMax、RMax。
或往右發現有比小明家高的樓高，就讓小明家長高，或讓小明搬家。(小明家高要先保留，往左檢查前要恢復原高)

for迴圈的計數變數來控制陣列存取的位置。

for(int i=1;i<=n;i++)
    cin >> h[n]; // 錯誤

f345: 新手練習題—陣列

b138: NOIP2005 1.陶陶摘苹果

f818: 物競天擇 (Survival)

設一個變數存身高*體重的最小值，初值為1000005。

e339: 前綴和練習

累加的數值會超過 int 上限。
若使用陣列記錄，小心不要出現b[-1]的狀況。

b558: 求數列第 n 項

f442: 老鷹抓小雞 Eagle

題目簡述
- 「老鷹抓小雞」的遊戲玩法為有一人是老鷹、一人是母雞、剩下的人為小雞(老鷹要抓小雞，母雞則要保護身後的小雞)。小雞被抓後會變成老鷹，老鷹則變成小雞(取代被抓小雞的位置)。
- 第一列有一正整數 N，代表有 N 隻小雞。
- 第二列有 N 個正整數，代表小雞的編號。
- 第三列有一正整數 E，代表老鷹的編號。
- 第四列有一正整數 Q，代表玩了 Q 回合。
- 第五列有 Q 個正整數，代表每回合被抓到小雞的編號。
- 輸出經過 Q 回合後，隊伍中小雞的編號。

b139: NOIP2005 2.校门外的树

可以宣告一個整數陣列tree(預設為0)，陣列的索引值代表位置，陣列值0、1表示有沒有樹。

a253: 王老先生的磨菇田

因為蘑菇編號只介於０～１００間，因此可以開一個大小為１０１的陣列（初始值皆為０），陣列的索引值代表蘑菇編號，儲存對應編號的蘑菇數量。

b374: [福州19中]众数

想法參考

c199: 爬山去(Hiking)-TOI練習賽y7m5-1

輸入時可先將重覆的數字去掉。

g308: pB. 跳跳布朗尼(Brownie)

使用布林陣列來記錄每個格子是否普經走過。
亦可直接使用記錄「傳送點資訊」的陣列，走過就設為「-1」。

2. 二維陣列

EX_4_4：a694: 吞食天地二

前綴和 ➜
如何以a693的方式加速？

[0][0]	[0][2]	[0][3]	[0][5]
[1][0]
[2][0]	[r1-1][c1-1]		[r1-1][c2]
[3][0]		[r1][c1]
[4][0]
[5][0]	[r2][c1-1]		[r2][c2]

陣列初值設為0

#include <cstring>
memset(a,0,sizeof(a));

C++ IO加速(原始網站)

ios::sync_with_stdio(false);
cin.tie(0);

EX_4_5：e798: p5. 卷積神經網路

求最大值可用max函式或if。
max 若要傳入三個以上的參數，須用大括號包住(initializer_list)，並含入 algorithm 標頭檔。

b367: 翻轉世界

假設 a180 為 a 轉 180 度後的陣列，a[i][j] 轉180度後會放在 a180[r-i-1][c-j-1];

f513: 舉旗遊戲 (Flag)

題目簡述
- 第一列有兩正整數 R、C（3 ≦ R、C ≦ 100），表示有 R×C 個人排成 R 列 C 行。
- 接著輸入 R 列，每列有 C 個正整數（1或2），代表每個人旗子的編號。
- 如果某人周遭的八個人，旗子的編號跟他都不一樣，則該人就被淘汰。請問有多少人會被淘汰？
陣列行、列可多開2個空間，index 0不要用，以免有些點的相鄰點會超出陣列。

如果自己的顏色和相鄰 8 點都不同，則淘汰人數+1。

if(a[i][j]!=a[i-1][j-1] && a[i][j]!=a[i-1][j] && a[i][j]!=a[i-1][j+1] && a[i][j]!=a[i][j-1] && ...)
// 左上、上、右上、左
    cnt++;

f418: Word Search Puzzle

char a[25][55];
不會有起始點在下，終點在上面的單字。
總共只有3種情況
- r1==r2 橫著印
- c1==c2 直著印
- 其它斜著印，從(r1+1,c1+1)，(r1+2,c1+2)…印到(r1+(r2-r1-1),c1+(c2-c1-1))，(r2,c2)

e787: b2.尋寶地圖(Map)

轉換圖計算行、列和時，重複算的要扣除。
題目
解題參考

f737: 農地 (Farmland)

類似 a694 的方法，以前綴和的方式計算(1,1)到每個點的總成本，-1不能開墾，可以將其值設為比開墾總預算大的值。
針對每個點，窮舉計算所有邊長的正方形農地的成本和。
因為只要知道最大的開墾面積，所以每次計算可從目前最大邊長+1開始即可。如果點座標+邊長超出邊界，或成本和 > 總預算，則之後的邊長都不用再檢查。
C++ IO加速。
解題參考

a867: 7. Minelayer

可以從index 1 開始放，想像盤面最外圍包了一圈0，例如3x5的盤面：
0000000
0●●*●*0
0**●●●0
0●**●●0
0000000
宣告二維的字元陣列
char mine[17][32]={0};
int cnt[16][31]={0};
不需最外層的while()

f148: 2. 定向越野 (Orienteering)

可以宣告一個 arr[26][3] 的二維陣列，初值均為 0。
- 26 表示有 26 個字母，a 對應到index 0、b 對應到index 1 …
- arr[ ][0]存字母是否存在，arr[ ][1]存列座標，arr[ ][2]存欄座標。
- 例如讀到 'a' 位於(0,2)
  arr[c-'a'][0]=1;
  arr[c-'a'][1]=0;
  arr[c-'a'][2]=2;
當讀取的地圖字元不是'0' 時，標記此字元存在，記錄其座標，並累計目標數量。
如果目標數量＜N，輸出"Mission fail."。否則從陣列 0 開始判斷該位子對應的字元是否存在，如果存在則輸出座標，直到滿 N 個目標。

五、字串(字元陣列)

1. 字串宣告

int a[3]={1,2,3};
cout << a << endl;             // 陣列名稱為陣列開始的位址

char c='x';                    // 宣告字元
cout << c << endl;
cout << (int)c << endl;        // ASCII

char s1[3]={'a','b','c'};      // 字元陣列，宣告長度為3的字串要多一個空間用來儲存空字元'\0'作為結束符號，否則會有錯誤
cout << s1 << endl;
char s1[4]={'a','b','c','\0'}; 
cout << s1 << endl;

string s2="abcd";               // 宣告string類別的字串
cout << s2 << endl;
cout << s2[1] << endl;
cout << s2.size() << endl;

2. 字串相關操作演算法筆記

EX_5_1：b428: 凱薩加密

if 或 %
Q：可以寫b[1]-a[1]嗎？

EX_5_2：d235: Q10929:You can say 11

11的倍數判別法：奇數位數字和與偶數位數字和相差為11的倍數。
字串長度：n.size() 或 n.length()
取絕對值函式：abs()
1～13的倍數判別法

EX_5_3：c276: 沒有手機的下課時間

a009: 解碼器

a065: 提款卡密碼

d124: 3的倍数

3的倍數判別法：各個數字和為3的倍數。

a882: B. 我灰灰的橡皮鴨是個恐怖的危機

b516: 凱撒密碼-商競103

e505: 12602 - Nice Licence Plates

取絕對值函式：abs()

g006: 密碼備忘錄 (Password)

以陣列儲存字母出現的次數(字母-'A'為索引值)。
因為最多100個字母，表示次數最大為100，由100->1檢查陣列中是否有這個次數，如果有則輸出(char)(索引值+'A')

六、函式(遞迴)

1. 自定函式宣告語法

回傳值的型態 函式名稱(變數型態 參數1，變數型態 參數2，...)
{
    程式碼
    return 回傳值或運算式;
}

EX_6_1：a623: 3. Combination

將n!寫成函式，在主程式呼叫3次。
$C (n, k) = \frac{n!}{(n - k)! * k!}$ ，例如C(4,2)=6。

EX_6_2：d237: 質數合

以質數函式測試是否需加此數。
TLE如何解決
- long long sum=2;
  for(int i=3;i<=2000000;i+=2)
- 如果一個數是合數，它的最小質因數會小於等於它的平方根。
- 因為成對出現的因數中，一個會
  $\leq \sqrt{n}$ ，而另一個會
  $\geq \sqrt{n}$ 。因此只要檢查
  $\leq \sqrt{n}$ 中是否有 n 的因數即可。
- 開根號用sqrt()，需含入 cmath 標頭檔。
不可直接輸出142913828922(超過int)。

a121: 質數又來囉

1不是質數。

b112: 5. 高中運動會。

寫一函式求兩數的最大公因數(輾轉相除法)。

f327: 刪除欄位。

寫一函式將輸入的字串轉成整數(26進位)，A為1，B為2，…，AA為27，AA為28，…。
s[i]-'A'+1

2. 傳值(call by value)、傳參考(call by reference)

EX_6_3：d491: 我也愛偶數 (swap 版)

將兩數交換寫成函式。
等差數列
((b-a)/2+1)/2*(a+b) 會錯誤，分子可能是奇數。


















void swap(int ~a, int ~b) // void 表示沒有回傳值
{
    int t;
    ~
    ~
    ~
    cout << "函式內："<< a << " " << b << endl;
}

int main()
{
    int a=1,b=2;
    cout << "交換前：" << a << " " << b << endl;
    swap(a,b);
    cout << "交換後：" << a << " " << b << endl;
   
    return 0;    
}

3. 遞迴

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

問題的答案，可從同類的子問題(規模更小)得到。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

在函式之中呼叫函式自己本身，要有終止條件，不然會無窮遞迴下去。

EX_6_4：95數學學測填充題G
用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形：

拼第95個圖需用到幾塊白色地磚。(478)















int f(int n)
{
    if ~          // if後只有一行，可省略{}
        ~
    else
        return ~
}

int main()
{
    int n;
    while(cin >> n)
        cout << f(n) << endl; // 5->28
    return 0;    
}

EX_6_5：a044: 空間切割

直線分割平面
- b_n=b_n-1+n，b₁=2
平面分割空間
- c_n=c_n-1+b_n-1，c₁=2

a623: 3. Combination

以遞迴改寫。
$C_{k}^{n} = C_{k}^{n - 1} + C_{k - 1}^{n - 1}$
$n == k | | k == 0$ 時，只有一種組合方式。

e357: 遞迴函數練習

c002: 10696 - f91

七、其它

1. 結構(struct)

// 自訂的資料型別 
struct 結構名稱
{
    資料型別 變數1;
    資料型別 變數2;
    ...
};

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

struct 定義的最後面要加分號！

EX_7_1：c316: 最遠點對！前傳

a130: 12015 - Google is Feeling Lucky

d809: 黑暗土地

以行列式算三角形面積，避免浮點數誤差。
取絕對值函式：abs()
要印出面積時再/2.0。

tags: 資訊科技

程式設計(使用C++、ZeroJudge)

零、評量、學習歷程

1. 評量方式

2. TOI推廣計畫-線上練習賽

3. APCS

4. 學習歷程檔案(修課記錄、課程學習成果)

5. 基礎教學網站

6. SoloLearn C++ Tutorial

7. 軟體

一、輸出與輸入、變數、運算式與運算子

1. 輸出與輸入

2. 變數型態

3. 變數宣告

4. 算數運算子

5. 關係運算子

6. 邏輯運算子

二、選擇

1. if 條件式語法

2. if~else 語法

3. 巢狀 if 語法

4. 多重選擇 if~else if~else 語法

三、迴圈

1. for 迴圈語法

2. 巢狀迴圈語法

3. while 迴圈語法

4. do..while 迴圈語法

四、陣列

1. 陣列宣告

2. 二維陣列

五、字串(字元陣列)

1. 字串宣告

2. 字串相關操作 演算法筆記

六、函式(遞迴)

1. 自定函式宣告語法

2. 傳值(call by value)、傳參考(call by reference)

3. 遞迴

七、其它

1. 結構(struct)

tags: `資訊科技`

2. 字串相關操作演算法筆記