<style> .reveal { font-size: 24px; } </style> # 競賽介紹 + 基礎 C++ 介紹 #### Rice --- ## 程式解題競賽(下午茶吃到飽大賽) 3 個人一組，使用一台電腦及一組鍵盤滑鼠進行解題。 比賽時間通常是 3hr ~ 5hr，題目數量為 7 ~ 15 題。 多數競賽會有點心，甚至有晚宴。 ---- ## 解題？ 一支筆 2 元，給你 10 元，你能買幾支？答案是 5 支。 程式競賽中，2 元和 10 元會是題目給你的「輸入」，5 是你的答案也就是「輸出」。 ---- ## 排名 先比解題數量再比累積解題時間，累積時間單位為分鐘，計算方式是上傳成功時間 + 錯誤次數 * 20，只計算正確的題目。 解題數量是最重要的。  ---- ## 有哪些競賽？ 1. 大學生的最終目標是 ACM-ICPC 的 World Final - 幾乎都是台清交的，所以我沒吃過 2. 參加資格是拿到 ACM-ICPC 的亞洲賽前 n 名(通常 n <= 2) - 有晚宴 3. 參加亞洲賽的資格來自 NCPC 或 TOPC - 前者初賽還好，決賽很好吃；後者是線上賽所以沒食物 記不起來沒關係，你想比賽就會有人幫你處理好 ---- ## 個人賽 都沒有食物QQ 1. 可以參加 CPE 練習 - 至少能 4 題，最好要有 6 題 2. Google Code Jam - Google 辦的比賽，時間不友善 3. Facebook Hacker Cup - Facebook 辦的比賽，時間更不友善 4. 各式各樣的線上賽 ---- ## 練習地 [ZeroJudge](https://zerojudge.tw/Problems) [TIOJ](https://tioj.ck.tp.edu.tw/) [CodeForces](http://codeforces.com/) [AtCoder](https://atcoder.jp/) [CodeChef](https://www.codechef.com/) [USACO](http://www.usaco.org/) --- ## 基礎 C++ 介紹 #### 不實作，請大家自行回家練習(會給題目) ---- ## 每個程式可以先照抄 ```cpp= #include<bits/stdc++.h> using namespace std; int main() { // 程式寫在裡面 } ``` --- ## 變數 ---- 一支筆 5 元，你想買 2 個，至少需要 10 元。 5、2、10 寫成 a, b, c，即可填入任意數字 a, b, c 在電腦中就是所謂的變數 ---- 至少需要的金額是從 a 和 b 來的 c = a * b ---- C++ 支援四則運算 c = a + b // + c = a - b // - a = a * b // × c = a / b // ÷ ---- 特別的運算：% c = a % b // 餘數 5 % 2 = 3 5 % 3 = 2 5 % 4 = 1 5 % 5 = 0 ---- 剛剛說的都是整數 除了 % 外小數也可以用 ---- int, long long // 整數 float, double // 小數 string // 字串 bool // 布林 ---- int a, b, c; string name = "顧客"; float rate = 0.7; c = a * b * rate; ---- string 支援 + 和 =，其他都不支援。 --- ## 輸入/輸出 ---- `cout << "程式社好好玩\n";` ---- `cout << "價錢 = " << c << "\n";` ---- ```cpp= int a, b; cin >> a >> b; cout << "價錢 = " << a * b << "\n"; ``` ---- 常見錯誤 ```cpp= cin >> a, b; cout << a, b << "\n"; ``` ---- 競賽題目通常都要換行 "\n" endl ---- ## 題目 - [ZeroJudge d483](https://zerojudge.tw/ShowProblem?problemid=d483) - [ZeroJudge a001](https://zerojudge.tw/ShowProblem?problemid=a001) - [ZeroJudge a002](https://zerojudge.tw/ShowProblem?problemid=a002) --- ## 判斷式 ---- 如果你現在在 9013，那你有聽到社課 ---- ```cpp= string pos; // 你現在在的地方 if (pos == "9013") { cout << "你有聽到社課\n"; } ``` ---- 其他人呢？ ---- ```cpp= if (pos == "9013") { cout << "你有聽到社課\n"; } else { cout << "你沒有聽到社課\n"; } ``` ---- 可是我們會有 hangout 直播啊！ ---- ```cpp= string pos; // 現在在的地方 bool inHangout; // 是否在 hangout 裡 if (pos == "9013") { cout << "你有聽到社課\n"; } else if (isHangout == true) { cout << "你有聽到社課\n"; } else { cout << "你沒有聽到社課\n"; } ``` ---- 可以合併起來嗎？ ---- ```cpp= if (pos == "9013" || isHangout == true) { cout << "你有聽到社課\n"; } else { cout << "你沒有聽到社課\n"; } ``` ---- 常見錯誤 現實的 = 是程式中的 == 或 || 打成 | 沒有 if 直接 else if - else if - else 打成 if - if - else ---- 麥當勞麥克雞塊分享餐每天 20:00 - 22:00 有買一送一 我們只輸入小時，分鐘預設為 00 問能否訂到買一送一的分享餐 ---- ```cpp= int hr; if (hr == 20) { // yes } else if (hr == 21) { // yes } else if (hr == 22) { // yes } else { // no } ``` ---- ```cpp= int hr; if (hr >= 20 && hr <= 22) { // yes } else { // no } ``` ---- 常見錯誤 20 <= hr <= 22 ---- ## 題目 - [ZeroJudge a799](https://zerojudge.tw/ShowProblem?problemid=a799) - [ZeroJudge a003](https://zerojudge.tw/ShowProblem?problemid=a003) - [ZeroJudge a004](https://zerojudge.tw/ShowProblem?problemid=a004) - [ZeroJudge a006](https://zerojudge.tw/ShowProblem?problemid=a006) - [ZeroJudge a263](https://zerojudge.tw/ShowProblem?problemid=a263) --- ## 迴圈 ---- 我今天如果吃 1 元的宵夜，明天就要吃 2 元的宵夜，後天吃 3 元的宵夜...，若我買不起，我就不吃宵夜了。 而我每天可以拿到 10 元的零用錢，現在我手上有 10 元，我可以吃幾天宵夜？ ---- 數學好像可以解？可以，但程式更方便 ---- ```cpp= int money = 10; int cost = 1; int day = 0; if (money >= cost) { // 如果可以重複執行就好了 money -= cost; money += 10; cost++; day++; } ``` ---- 真的可以重複執行！ while(); // 重複執行版的 if ---- ```cpp= int money = 10; int cost = 1; int day = 0; while (money >= cost) { money -= cost; money += 10; cost++; day++; } ``` ---- 一次社課有 10 個人，5 次社課後有幾個人？ 請在不使用 * 的情況解決這個問題 ---- ```cpp= int count = 0, index = 1; while(index <= 5) { count += 10; index++; } ``` ---- ```cpp= int count = 0; for(int index=1; index<=5; index++) { count += 10; } ``` ---- 通常只是要跑單純的次數，會用 i, j, k，從 0 ~ n-1 ```cpp= for(int i=0; i<5; i++) { } ``` ---- 請印一張九九乘法表 ---- 考慮 1 會 * (1, 2, 3, 4, ..., 9) 考慮 2 會 * (1, 2, 3, 4, ..., 9) ... 考慮 9 會 * (1, 2, 3, 4, ..., 9) ---- ```cpp= for(int i=1; i<=9; i++) { cout << 1 << "*" << i << "=" << 1 * i << " "; } ``` ---- 考慮的數字也能 for，把 1 * i 的 1 換掉就好 ---- ```cpp= for(int k=1; k<=9; k++) { for(int i=1; i<=9; i++) { cout << k << "*" << i << "=" << k * i << " "; } } ``` ---- 常見錯誤 while(); { } for(;) { } for(; int i=1;) { } for(int i=1; ; i++) {} ---- ZeroJudge 上的輸入 ```cpp= int a, b; while(cin >> a >> b) { // 有輸入才繼續 } ``` ---- ## 題目 - [ZeroJudge a244](https://zerojudge.tw/ShowProblem?problemid=a244) - [ZeroJudge d639](https://zerojudge.tw/ShowProblem?problemid=d649) - [ZeroJudge d498](https://zerojudge.tw/ShowProblem?problemid=d498) --- ## 陣列 ---- 這裡有 k 個人，輸入這 k 個人的名字。 ---- string a1, a2, a3, a4, ..., ak? ---- ```cpp= int k; cin >> k; string name[k]; cin >> name[0] >> name[1] >> ...; ``` ---- ```cpp= for(int i=0; i<k; i++) { cin >> name[i]; } ``` ---- string 裡面本身是陣列。 ```cpp= for(int i=0; i<name.length(); i++) { cout << name[i]; } ``` ---- 輸入 n 個人的名字，在每個名字的字中間插入空格後輸出。 ---- ```cpp= int n; string name[n]; for(int i=0; i<n; i++) cin >> name[i]; for(int i=0; i<n; i++) { cout << name[i][0]; for(int j=1; j<name[i].length(); j++) { cout << " " << name[i][j]; } cout << endl; } ``` ---- 輸入 n 個人的名字，從最後一個人的名字開始，反過來輸出每個名字的倒序。 ---- ```cpp= int n; string name[n]; for(int i=0; i<n; i++) cin >> name[i]; for(int i=n-1; i>=0; i--) { for(int j=name[i].length()-1; j>=0; j--) { cout << name[i][j] << " "; } cout << name[i][0] << endl; } ``` ---- 注意，其他型態也可以這樣用 ```cpp= int n, m; cin >> n >> m; int maps[n][m]; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin >> maps[i][j]; } } ``` ---- 常見錯誤 還沒給 n, m 就宣告陣列 從 1 開始想 超過 n 或 m ---- ## 題目 - [ZeroJudge a005](https://zerojudge.tw/ShowProblem?problemid=a005) - [ZeroJudge a009](https://zerojudge.tw/ShowProblem?problemid=a009) - 理論上 ZeroJudge 第一頁，除了 a017 外都可以做 - a042 和 a044 是數學題，可跳過沒關係 --- ## 其他 多練習，這些東西第一次寫一定會卡住，非常正常。 ---- 時間還很夠，我們多講一些細節 ---- 陣列不夠大，開 global int a[1000000]; int main() { } ---- 電腦儲存變數的方法 0/1 ---- 輸出空白+換行 ```cpp= for(int i=0; i<n; i++) cout << a[i] << " \n"[i==n-1]; ``` ---- function、recursive --- # END ## 有問題歡迎隨時在群組發問