On The Road

題目原文 題目說明 第一行輸入幾筆資料，第二行輸入此資料共幾片(n) 雪花，接下來 n 行代表雪花編號。 輸出可裝出最多不同雪花的數目 (需連續)。 思路 假設共 5 片雪花，編號分別是 4 1 4 2 3 5，從第一個 4 開始取，接下來是 1 和 4，碰到 4 時因為與第一個 4 編號相同，所以記下此次最多取出相異雪花數目為 2；接下來從 1 開始取，依序是 4 2 3 5，記下此次最多可取出相異數目為 5 ，並且每次取出數目時都與 max 比大小，最後傳回最大值即可。 #include<iostream> using namespace std; int check(int[], int); int main() { int t, n; scanf("%d", &t); while(t--) { scanf("%d", &n); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); int ans; ans = check(arr, n); printf("%d\n", ans); } } int check(int arr[], int n) { int max = 0; int count = 0; int stop = -1; for(int i = 0; i < n; i++) { for(int j = stop + 1; j < i; j++) { if(arr[j] == arr[i]) { stop = j; // 利用 stop 記住 i = stop + 1; // 往下一個移動 if(count > max) max = count; count = 0; } } count++; } if(count > max) return count; else return max; }

題目原文 題目說明 輸入一段文章，輸出每一單字，並按字典序排列。 思路 一個單字一個單字去讀，若遇到像 andy's 這種詞，須將其切割為 andy 和 s 兩個單字， 讀完丟入 set (會自動依字典序排列)，再利用迭代器輸出即可。 #include<iostream> #include<cctype> #include<cstring> #include<sstream> #include<set> using namespace std; set<string> dict; int main() { string input; while(cin >> input) { for(int i = 0; i < input.length(); i++) { if(isalpha(input[i])) input[i] = tolower(input[i]); else input[i] = ' '; // 非字母轉成空白字元 (ex. andy's 變 andy s) } stringstream ss; // 拿來切割 (ex. andy s 變兩個字串) ss << input; string output; while(ss >> output) dict.insert(output); // 會自動由小到大排 } set<string>::iterator it; for(it = dict.begin(); it != dict.end(); it++) cout << *it << endl; return 0; }

題目原文 題目說明 第一行輸入兩個數字 N 和 Q，分別代表：有 N 個大理石和查找 Q 個數。 接下來的 N 行代表大理石所寫上的數，由小到大依序排列，最後求題目所問某數在哪個位置。 思路 利用 algorithm 裡的 sort 進行排序，再利用 lower_bound 查找出位置。 lower_bound ：用來找出第一個大於或等於某數的位置。 #include<cstdio> #include<algorithm> using namespace std; const int maxn = 10000; int main() { int n, q, arr[maxn], count = 0; while(scanf("%d %d", &n, &q) == 2 && n) { printf("CASE# %d:\n", ++count); for(int i = 0; i < n; i++) scanf("%d", &arr[i]); sort(arr, arr+n); while(q--) { int num; // 要搜尋的數 scanf("%d", &num); int pos = lower_bound(arr, arr+n, num) - arr; // 用 lower_bound 查找 num 的位置 if(arr[pos] == num) printf("%d found at %d\n", num, pos+1); else printf("%d not found\n", num); } } }

題目原文 題目說明 只有兩種顏色，且相鄰兩點需不同色，若可以達成，則輸出 BICOLORABLE，反之輸出 NOT BICOLORABLE。 思路 首先以 vector 建立表格來儲存與某節點相鄰的其他節點，以 queue 來儲存節點走訪的順序。 建立好連通表後，開始走訪，走訪做兩種事情：著色和檢查是否同色，可隨機從某點開始(以下程式碼以 n1 當第一個節點)，將其 push 進 queue 裡並著上顏色，塗完顏色後以 current 記住後 pop 出去， 接著開始替相鄰節點(由連通表依序取出)著色，若相鄰節點尚未著色，則 push 到 queue 裡，當作下一個要走訪的 current，並著上與當前 current 相反顏色；已著色則檢查是否與當前 current 同色，同色則可確定非 bicolorable。著完後色都沒問題即為 bicolorable。 簡言之， 1. 建連通表  2. 按連通表依序著色  3. 著色過程中檢查是否符合規定。 #include<cstdio> #include<vector> #include<queue> int main() { int node; while(scanf("%d", &node) && node) { int edge, n1, n2; int color[200] = {0}; bool check = true; std::vector<int> vec[205]; // 所在列數代表它是第幾個點 後面push進和它連接的點 std::queue<int> que; scanf("%d", &edge); for(int i = 0; i < edge; i++) { scanf("%d %d", &n1, &n2); vec[n1].push_back(n2); // 建連通表 記得兩邊互相連接 vec[n2].push_back(n1); } que.push(n1); color[n1]

說明 建構出以學生姓名和成績為節點的佇列。 思路 以鏈結串列建立佇列，概念大致和上一篇： 陣列實作串列  相同。 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct student { char name[20]; int score; struct student *next; }node; node *front = NULL; // 先都指向 NULL node *rear = NULL; int enqueue(char[], int); // 新增 int dequeue(); // 刪除 推第一個出來 int show(); int main(void) { int score, select; char name[20]; do { printf("請輸入 1. 新增 2. 刪除 3. 顯示 4. 結束: "); scanf("%d", &select); switch(select) { case 1: printf("請輸入姓名 成績: "); scanf("%s %d", &name, &score); enqueue(name, score); // 存進去 break; case 2: dequeue(); break; case 3: show(); break; } } while(select != 4); return 0; } int enqueue(char name[], int score) { node *newnode = (node *)malloc(sizeof(node)); newnode->score = score; strcpy(newnode->name, name); if(rear == NULL) fr

思路 以陣列來建立佇列，擁有兩個動作 — 加入和刪除，並且用 front 和 rear 分別指向佇列的前端和尾端。 一開始，front 和 rear 都預設為 -1，每加入一個元素，rear 的值 + 1；每刪除一個元素，front 的值 + 1。 以陣列建立的缺點是大小無法事先規劃。 #include<stdio.h> #include<stdlib.h> #define max 10 int queue[max] = {0}; int front = -1; int rear = -1; int main(void) { int value, select = 1; while(rear < max - 1 && select != 3) { printf("請輸入1. 存入數值 2. 取出數值 3. 結束: "); scanf("%d", &select); switch(select) { case 1: printf("請輸入數值: "); scanf("%d", &value); rear++; queue[rear] = value; break; case 2: // 取出 if(rear > front) { front++; printf("取出的值為 %d\n", queue[front]); queue[front] = 0; // 取完 } break; default: break; } } printf("輸出佇列中所有元素: "); if(rear == max - 1) printf("佇列已滿\n"); else if(front >= rear) printf("佇列已空\n"); else { while(rear &