APCS 1/7(C++) - HackMD

# 教學用(程式碼僅供參考) # 第一題 https://zerojudge.tw/ShowProblem?problemid=m931 --- <details> <summary><span style="font-weight:bold;font-size:24px">提示:</span><span style="color:green;font-weight:bold; font-size:24px"></span></summary> $step1.$ 把兩數字存到a陣列跟b陣列，c陣列存平方和 $step2.$ c[i]=a[i]*a[i]+b[i]*b[i] $step3.$ 找到最大的c[i]值，刪掉他 $step4.$ 再找一次最大的c[i]值，同時記錄c的位置在哪(記錄i是多少) $step5.$ 輸出a[i]和b[i] </details> <details> <summary><span style="font-weight:bold;font-size:24px">範例(以example1為例):</span><span style="color:green;font-weight:bold; font-size:24px"></span></summary> <div style="display:inline-block; width:45%; margin-right:5%;"> **Step 1** | $a_i$ | 3 | 5 | 1 | | - | - | - | - | | $b_i$ | 1 | 2 | 4 | | total | 10 | 29 | 17 | </div> <div style="display:inline-block; width:45%;"> **Step 2** | $a_i$ | 3 | 5 | 1 | | ----- | --- | --- | --- | | $b_i$ | 1 | 2 | 4 | | total | 10 | <span style="font-weight:bold; font-size:20px;">29</span> | 17 | </div> <div style="display:inline-block; width:45%; margin-right:5%;"> **Step 3** | $a_i$ | 3 | 5 | 1 | | - | - | - | - | | $b_i$ | 1 | 2 | 4 | | total | 10 | <span style="font-weight:bold; font-size:20px;">~~29~~</span> | 17 | </div> <div style="display:inline-block; width:45%;"> **Step 4** | $a_i$ | 3 | 5 | 1 | | ----- | --- | --- | --- | | $b_i$ | 1 | 2 | 4 | | total | 10 | ~~29~~ | <span style="font-weight:bold; font-size:20px;">17</span> | </div> </details> --- <summary><span style="font-weight:bold;font-size:24px">array解(三個一維陣列) </span><span style="color:green;font-weight:bold; font-size:24px"> AC(2ms, 348KB)</span></summary> ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0); //IO優化 int n,mx=0,tmp=0; int a[100], b[100], c[100]; //三個一維陣列 cin>>n; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; c[i]=(a[i])*(a[i])+(b[i])*(b[i]); //計算平方和丟到c[i]裡 if(c[i]>mx) mx=c[i],tmp=i; } c[tmp]=0,mx=0,tmp=0; for(int i=0;i<n;i++){ if(c[i]>mx) mx=c[i],tmp=i; } cout<<a[tmp]<<" "<<b[tmp]; } ``` ## <summary><span style="font-weight:bold;font-size:24px">array解(二維陣列) </span><span style="color:green;font-weight:bold; font-size:24px"> AC(2ms, 356KB)</span></summary> ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0); //IO優化 int n,mx=0,tmp=0; int v[3][100]; //這邊選擇開二維陣列也可開三個一維 cin>>n; for(int i=0;i<n;i++){ cin>>v[0][i]>>v[1][i]; v[2][i]=(v[0][i])*(v[0][i])+(v[1][i])*(v[1][i]); //計算平方和丟到v[2][i]裡 if(v[2][i]>mx) mx=v[2][i],tmp=i; } v[2][tmp]=0,mx=0,tmp=0; for(int i=0;i<n;i++){ if(v[2][i]>mx) mx=v[2][i],tmp=i; } cout<<v[0][tmp]<<" "<<v[1][tmp]; } ``` ## <summary><span style="font-weight:bold;font-size:24px">vector解 </span><span style="color:green;font-weight:bold; font-size:24px"> AC(2ms, 364KB)</span></summary> ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0); int n,mx=0,tmp=0; vector<vector<int>> v; cin>>n; v.resize(3,vector<int>(n)); for(int i=0;i<n;i++){ cin>>v[0][i]>>v[1][i]; v[2][i]=(v[0][i])*(v[0][i])+(v[1][i])*(v[1][i]); if(v[2][i]>mx) mx=v[2][i],tmp=i; } v[2][tmp]=0,mx=0,tmp=0; for(int i=0;i<n;i++){ if(v[2][i]>mx) mx=v[2][i],tmp=i; } cout<<v[0][tmp]<<" "<<v[1][tmp]; } ``` --- # 第二題 https://zerojudge.tw/ShowProblem?problemid=m932 <details> <summary><span style="font-weight:bold;font-size:24px">提示:</span><span style="color:green;font-weight:bold; font-size:24px"></span></summary> 其實真正圖形長這樣 <div style="display:inline-block; width:45%; margin-right:5%;"> **移動路徑方向:** | 5 | 0 | X | | --- | --- | --- | | 4 | 中 | 1 | | X | 3 | 2 | </div> <div style="display:inline-block; width:45%;"> **對照:** <table style="width:400px;font-weight:bold"> <tr> <td>[x-1][y-1]</td> <td>[x-1][y]</td> <td>[x-1][y+1]</td> </tr> <tr> <td>[x][y-1]</td> <td>[x][y]</td> <td>[x][y+1]</td> </tr> <tr> <td>[x+1][y-1]</td> <td>[x+1][y]</td> <td>[x+1][y+1]</td> </tr> </table> </div> <div style="display:inline-block; width:45%; margin-right:5%;"> **完整圖形:** | 邊 | 邊| 邊 | 邊 | 邊 | | --- | -------- | --- | --- | --- | | 邊 | 5 | 0 | X | 邊 | | 邊 | 4 | | 1 | 邊 | | 邊 | X | 3 | 2 | 邊 | | 邊 | 邊 | 邊 | 邊 | 邊 | </div> </details> <details> <summary><span style="font-weight:bold;font-size:24px">範例(以example1為例):</span><span style="color:green;font-weight:bold; font-size:24px"></span></summary> **** <div style="float: left; width: 50%;"> <h2>INPUT</h2> <pre><code class="c++">2 4 5 TyuI ABaB 0 1 2 3 0 </code></pre> </div> <div style="float: right; width: 50%;"> <h2>OUTPUT</h2> <pre><code class="c++">Tyaau 4 </code></pre> </div> <div style="clear: both;"></div> **step1:** | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | | --- | --- | --- | --- | --- | --- | | 邊 | **T(step1)** | y | u | I | 邊 | | 邊 | A | B | a | B| 邊 | | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | **step2:** | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | | --- | --- | --- | --- | --- | --- | | 邊 | **T(step1)** | **y(step2)** | u | I | 邊 | | 邊 | A | B | a | B| 邊 | | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | **step3:** | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | | --- | --- | --- | --- | --- | --- | | 邊 | **T(step1)** | **y(step2)** | u | I | 邊 | | 邊 | A | B | **a(step3)** | B| 邊 | | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | **step4:** | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | | --- | --- | --- | --- | --- | --- | | 邊 | **T(step1)** | **y(step2)** | u | I | 邊 | | 邊 | A | B | **a(step3,step4)** | B| 邊 | | 邊 | 邊 | 邊 | ~~**邊(step4)**~~ | 邊 | 邊 | **step5:** | 邊 | 邊 | 邊 | 邊 | 邊 | 邊 | | --- | --- | --- | --- | --- | --- | | 邊 | **T(step1)** | **y(step2)** | **u(step5)** | I | 邊 | | 邊 | A | B | **a(step3,step4)** | B| 邊 | | 邊 | 邊 | 邊 | ~~**邊**~~ | 邊 | 邊 | </details> --- <summary><span style="font-weight:bold;font-size:24px">m932解答(一般vector解) </span><span style="color:green;font-weight:bold; font-size:24px">AC(2ms, 368KB)</span></summary> ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0); //IO優化 vector<vector<char>> v; bool t[123]={0}; //統計用陣列 (輸出第二行時用的到) int m,n,k,d; //m,n,k為題目敘述 d代表的是input最後一行的整數 string s; cin>>m>>n>>k; int nowx=m-1,nowy=0,cnt=0; //nowx,nowy記錄現在位置的x和y cnt記錄種類 v.resize(m,vector<char>(n)); //動態開記憶體 for(int i=0;i<m;i++){ //把string丟進char陣列裡 cin>>s; for(int j=0;j<n;j++){ v[i][j]=s[j]; } } for(int i=0;i<k;i++){ //先判斷現在往哪個方向再判斷if(沒超過邊界)就更新現在位置; cin>>d; if(d==0){ if((nowx-1)>=0) nowx--; } else if(d==1){ if((nowy+1)<n) nowy++; } else if(d==2){ if((nowx+1)<m&&(nowy+1)<n) nowx++,nowy++; } else if(d==3){ if((nowx+1)<m) nowx++; } else if(d==4){ if((nowy-1)>=0) nowy--; } else if(d==5){ if((nowx-1)>=0&&(nowy-1)>=0) nowx--,nowy--; } cout<<v[nowx][nowy]; t[(int)(v[nowx][nowy])]=1; //這邊使用ASCII 轉成int 丟到陣列 } for(int i='A';i<='Z';i++){ //跑陣列統計多少種類 if(t[i]==1) cnt++; } for(int i='a';i<='z';i++){ if(t[i]==1) cnt++; } cout<<"\n"<<cnt; } ``` ## <summary><span style="font-weight:bold;font-size:24px">m932解答(用unordered_set解) </span><span style="color:green;font-weight:bold; font-size:24px">AC(2ms, 356KB)</span></summary> ```cpp= #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0);cin.tie(0); int m,n,k; cin>>m>>n>>k; vector<vector<char>> v(m, vector<char>(n)); for (int i=0;i<m;++i) { for (int j=0;j<n;++j) { cin >> v[i][j]; } } int nowx = m - 1, nowy = 0; unordered_set<char> uniqueChars; for (int i = 0; i < k; ++i) { int d; cin >> d; if (d == 0 && nowx > 0) nowx--; else if (d == 1 && nowy < n - 1) nowy++; else if (d == 2 && nowx < m - 1 && nowy < n - 1) nowx++, nowy++; else if (d == 3 && nowx < m - 1) nowx++; else if (d == 4 && nowy > 0) nowy--; else if (d == 5 && nowx > 0 && nowy > 0) nowx--, nowy--; cout << v[nowx][nowy]; uniqueChars.insert(v[nowx][nowy]); } cout<<"\n"<<uniqueChars.size(); return 0; } ``` 偷偷宣傳一下個版:D 更多內容: https://chewu-0319.github.io/personal/ 有問題歡迎: [個人discord](https://discordapp.com/users/768889520280043561)