淘課計畫 - HackMD

# 淘課計畫 --- ## 一些好東西 ### part 2 ---- * 常用STL介紹 * sort進階用法 * 解題想法 ---- #### 固定輸出小數後位數 #### cout<<fixed<<setprecision(位數); --- ## 常用STL介紹 ---- ## vector #### 超好用陣列 ---- ## vector #### 常用語法 ---- ## 宣告與初始化 ```cpp= #include <vector>//記得讀入標頭檔 vector<int> v1;//宣告一個名為v1 的陣列 vector<int> v2(5);//宣告一個名為v2 且長度為5 的陣列 vector<int> v3(100,5); //宣告一個名為v3 長度為5 個元素初始值為100 的陣列 ``` ---- ## 常用操作 ```cpp= v[2]=3;//直接賦值 v.size(); // v 的長度 v.clear(); // 清空 v v.push_back(n); // 放 n 在 v 後面 v.pop_back(n); // 刪除 v 的最後一個元素 reverse(v.begin(),v.end()); //將陣列中的元素反轉 v.begin(); v.end(); // v 的 iterator ``` ---- ## v.size() ### code ```cpp= vector<int> v(100); cout<<v.size(); ``` ### 輸出 ```cpp= 100 ``` ---- ## 遍歷vector ```cpp= vector<int> v; for(int i=0;i<10;i++)v.push_back(i); for(int i=0;i<10;i++)cout<<v[i]<<" "; cout<<endl; for(auto i=v.begin();i!=v.end();i++)cout<<*i<<" "; ``` ---- ## reverse ### code ```cpp= vector<int> v; for(int i=0;i<10;i++)v.push_back(i); for(int i=0;i<10;i++)cout<<v[i]<<" "; cout<<endl; reverse(v.begin(),v.end()); for(int i=0;i<10;i++)cout<<v[i]<<" "; ``` ### 輸出 ```cpp= 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 ``` ---- ## reverse #### 也可以反轉一部分 ### code ```cpp= vector<int> v; for(int i=0;i<10;i++)v.push_back(i); for(int i=0;i<10;i++)cout<<v[i]<<" "; cout<<endl; reverse(v.begin(),v.begin()+5); for(int i=0;i<10;i++)cout<<v[i]<<" "; ``` ### 輸出 ```cpp= 0 1 2 3 4 5 6 7 8 9 4 3 2 1 0 5 6 7 8 9 ``` ---- ## pair ---- ## pair #### 適合用來儲存兩個一組的資料 #### 例如(身高,體重) 、 ( x , y ) ---- ## pair #### 常用語法 ```cpp= #include <utility>//記得標頭檔 pair<int,int> pii;//宣告 pair<int, string> pis(10, "Hey");//初始化 pii.first; pii.second; // 分別回傳 pii 的第 0 項跟第 1 項 ``` ---- #### 那存三個東西要怎麼辦 ---- #### ~~可以用兩個pair解決~~ ```cpp= pair<int,pair<int,int>> piii;//宣告 piii.first;//第一個元素 piii.second.first;//第二個元素 piii.second.second;//第三個元素 ``` ---- ## set ---- ## set ### 集合 ---- ## set #### 常用語法 ```cpp= #include <set>//記得標頭檔 set<int> st;//宣告 st.insert(n); // 在 st 中放入 n st.erase(n); // 把 n 從 st 中移除 st.clear(); // 清空 s st.size(); // s 的大小 st.find(n); // 找 n 的 iterator st.count(n); // 找 n 在 s 中的數量 st.begin(); st.end(); // 找 st 的 iterator ``` ---- ## 遍歷set ```cpp= set<int> st; for(int i=10;i>=0;i--)st.insert(i); st.insert(32); st.insert(22); for(auto i=st.begin();i!=st.end();i++)cout<<*i<<" "; ``` ## 輸出 ```cpp= 0 1 2 3 4 5 6 7 8 9 22 32 ``` ---- ## map ---- ## map #### 可以快速查詢的資料結構 ---- ## map #### 常用語法 ```cpp= #include <map> map<int, string> mp; // <key, value> mp[1] = "hello"; mp[5] = "world"; // 賦值 mp.clear(); // 清空 mp.find(n)); // 回傳 key = n 的 iterator mp.count(n); // 回傳 key = n 的個數 mp.begin(); mp.end(); // 找 mp 的 iterator ``` ---- ## code ```cpp= mp[1] = "hello"; mp[5] = "world"; cout<<mp[1]; ``` ## 輸出 ```cpp= hello ``` ---- ## 遍歷map ```cpp= map <int,int> mp; for(int i=10;i>=0;i--)mp[i]=10-i; for(auto i=mp.begin();i!=mp.end();i++) cout<<(*i).first<<" "<<(*i).second<<endl; ``` ## 輸出 ```cpp= 0 10 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 10 0 ``` --- ## sort進階用法 ---- #### 沒錯 sort 又來了 #### 這次介紹的是進階用法 #### sort(起始位置,終止位置,自訂函式) ---- #### 先複習sort基本用法 #### sort(起始位置,終止位置) ```cpp= int arr[10]={2,3,4,6,5,0,8,7,1,9}; sort(arr,arr+10); for(int i=0;i<10;i++)cout<<arr[i]<<" "; ``` ---- #### 那如果要從大排到小怎麼辦 ---- #### 自訂函式 ```cpp= bool cmp((資料型態) a,(資料型態) b){ return a > b; } ``` ---- ## code ```cpp= bool cmp(int a,int b){ return a > b; } int arr[10]={2,3,4,6,5,0,8,7,1,9}; sort(arr,arr+10,cmp); for(int i=0;i<10;i++)cout<<arr[i]<<" "; ``` #### 輸出 ```cpp= 9 8 7 6 5 4 3 2 1 0 ``` ---- #### 也可以完成一些比較複雜的排序 #### 例如:可以被5整除的數>不能被5整除的數 ---- ## code ```cpp= bool cmp(int a,int b){ return b%5==0; } int arr[10]={21,35,40,63,85,5,0,13,72,91}; sort(arr,arr+10,cmp); for(int i=0;i<10;i++)cout<<arr[i]<<" "; ``` #### 輸出 ```cpp= 21 63 13 72 91 0 5 85 40 35 ``` ---- ## 想一下! #### 如果排序要求更複雜 #### 要求符合以下兩點要怎麼做 #### 1,偶數排奇數前面 #### 2,大數排小數前面 ---- #### code :::spoiler ```cpp= bool cmp(int a,int b){ if(a%2==b%2)return a > b; return(a%2<b%2); } signed main(){ int arr[10]={2,3,4,6,8,5,0,1,7,9}; sort(arr,arr+10,cmp); for(int i=0;i<10;i++)cout<<arr[i]<<" "; return 0; } ``` ::: #### 輸出 ``` 8 6 4 2 0 9 7 5 3 1 ``` --- ## 解題想法 #### 練習連結 https://vjudge.net/contest/616246#overview --- ## problem A ---- ## 題意 #### 有一個發瘋的老頭在亂上課 XX平 #### 他說的話剛會往鍵盤左偏兩格。 #### 輸入規則: 1. 不會有 Enter shift 之類的指令 2. 不會q,a,z...無法左移的字母 3. 都是小寫字母 ---- ## hint 1 #### else if可以過 #### 鍵盤上的數字列也會用到 --- ## problem B ---- ## 題意 #### 輸入一行句子，用ascii碼輸出字元出現頻率 #### 輸出順序由出現次數少的優先輸出 #### 若出現次數相同則由ascii碼大的優先輸出 ---- ## hint 1 #### 可以用pair把字母與次數連結 ---- ## hint 2 #### 在sort它 ---- ## hint 2 #### 記得用getline讀入整句 --- ## problem C ---- ## 題意 #### 給繞地球的兩個衛星 #### 分別求弧長與直線距離 #### 輸出固定小數後6位 #### tip1 : 180 deg = 1 PI, 1 deg = 60min #### tip2 : PI in c++ *M_PI* ---- ## hint 1 #### 記得用double #### 角度超過180記得要換邊 --- ## problem D ---- ## 題意 #### 給 n 個整數與整數 m 做排序 #### 排序順序如下 : 1. 按照 mod m 由小到大 2. 餘數相等則奇數在偶數前面 3. 如果同為奇數則由大到小 4. 如果同為偶數則由小到大 ---- ## hint 1 #### 用自訂cmp sort它 --- ## problem E ---- ## 題意 #### 有需要可以看中文 #### https://zerojudge.tw/ShowProblem?problemid=e605 ---- ## hint 1 #### 注意輸出格式 --- ## problem F ---- ## 題意 #### 用它給規則把數字表示出來 ---- ## hint 1 #### 補充測資與輸出 #### input ```cpp= 460000409000 467000408900 467800456780 100000000000000 999999999999999 0 ``` #### output ```cpp 1. 46 hajar kuti 4 lakh 9 hajar 2. 46 hajar 7 shata kuti 4 lakh 8 hajar 9 shata 3. 46 hajar 7 shata 80 kuti 4 lakh 56 hajar 7 shata 80 4. 1 kuti kuti 5. 9 kuti 99 lakh 99 hajar 9 shata 99 kuti 99 lakh 99 hajar 9 shata 99 6. 0 ```