*陣列的妙用*

# *陣列的妙用* ###### tags: `C++` `陣列` `AA競程` > 此筆記由@Cheng0928編寫，請尊重作者**著作財產權** > 感謝[AA競程](https://aacpschool.com/)的教導 ## 特別感謝[AA競程](https://aacpschool.com/) 想學**C++基礎語法**？想要考**APCS滿級分**？甚至是**代表台灣參加資奧**？那你可要看好這邊了 ### 專為想增進實力的你！ AA競程教學內容**皆以資奧標準備課**，並非普通程式教育機構，致力**培養出優秀、實力強的學生！** ### 全職專業老師黃以文老師 (dreamoon) **擁有十分豐富的出題經驗(在各大 Online Judge 以及 NPSC, ICPC 區域賽預選賽)** 教學認真，**非上課時間也會協助你解決大大小小的程式問題** ### 十分完美的學習計畫 AA競程的每一期課程都有對應的後續課程，**不會出現學生想學老師卻沒能力教的情況！** ### 精選練習題集 AA競程收集了各大知名競程平台的優秀題目，並且分專題整理好了題單 **只要你有時間，就不怕沒題做！** --- 你！心動了嗎？還不趕快點下[連結](https://aacpschool.com/)報名下一期課程！ ## 本文課程主題 1. [用陣列儲存索引值資訊](https://hackmd.io/@Cheng0928/MagicalArray#%E7%94%A8%E9%99%A3%E5%88%97%E5%84%B2%E5%AD%98%E7%B4%A2%E5%BC%95%E5%80%BC%E8%B3%87%E8%A8%8A) 2. [用陣列儲存每個東西的位置](https://hackmd.io/@Cheng0928/MagicalArray#%E7%94%A8%E9%99%A3%E5%88%97%E5%84%B2%E5%AD%98%E6%AF%8F%E5%80%8B%E6%9D%B1%E8%A5%BF%E7%9A%84%E4%BD%8D%E7%BD%AE) 3. [用陣列打表](https://hackmd.io/@Cheng0928/MagicalArray#%E9%99%A3%E5%88%97%E6%89%93%E8%A1%A8) ## 用陣列儲存索引值資訊此技巧通常出現在 1. 需要計算某數字出現次數 2. 計數排序 example：cnt[x] 儲存 x 的資訊以下為例題 * [AA競程L0公開課題單 I. 計算數字個數](https://hackmd.io/@Cheng0928/MagicalArray#AA%E7%AB%B6%E7%A8%8BL0%E5%85%AC%E9%96%8B%E8%AA%B2%E9%A1%8C%E5%96%AE-I-%E8%A8%88%E7%AE%97%E6%95%B8%E5%AD%97%E5%80%8B%E6%95%B8) * [NHDK TPR#11 C. Gunjyo 與骰子](https://hackmd.io/@Cheng0928/MagicalArray#NHDK-TPR11-C-Gunjyo-%E8%88%87%E9%AA%B0%E5%AD%90) * [ABC 200 C - Ringo's Favorite Numbers 2](https://hackmd.io/@Cheng0928/MagicalArray#ABC-200-C---Ringo%E2%80%99s-Favorite-Numbers-2) * [ABC 152 D - Handstand 2](https://hackmd.io/@Cheng0928/MagicalArray#ABC-152-D---Handstand-2) ### [AA競程L0公開課題單 I. 計算數字個數](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/I) > 給你一個長度為 N (N <= 10 ^ 5) 個不超過 10 ^ 6 的 a 序列， > 有 Q 個詢問，每個詢問給你一個正整數 bi (1 <= bi <= 10 ^ 9) ， > 問你 bi 在 a 中出現幾次開一個大小為 1000001 名為 cnt 的陣列，每次輸入一個數字 ai 就 cnt[ai]++ ，這樣就可以計算ai在此序列中出現的次數了！ **此題還有一個重點， a 序列中的數字不超過 10^6 ，但是詢問的數字卻會達到 10^9** Tips * 當cin很多數字的時候，建議用`cin.tie(0); ios_base::sync_with_stdio(false);`來加快程式運行速度喔~ 我寫的AC程式碼 ```cpp #include <iostream> #define int long long using namespace std; int a[1000001]; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int n; cin >> n; for(int i=0;i<n;i++){ int num; cin >> num; a[num]++; } int q; cin >> q; for(int i=0;i<q;i++){ int num; cin >> num; if(num > 1000000){ cout << "0\n"; } else{ cout << a[num] << "\n"; } } return 0; } ``` ### [NHDK TPR#11 C. Gunjyo 與骰子](https://codeforces.com/group/H0qY3QmnOW/contest/333897/problem/C) > 有三顆 100 面骰，每個面有點數 1~100 ， > 我們想知道湊到 N 點共有幾種組合，不過可以選擇要將點數做相乘或相加。 > 假設骰出 {2,3,4} ，組合出的點數有 {2 + 3 + 4}, {2 ⋅ 3 + 4}, {2 + 3 ⋅ 4}, {2 ⋅ 3 ⋅ 4}。 **開三層迴圈來代表骰到的數字**，在迴圈內只要 * cnt[a + b + c]++ * cnt[a + b * c]++ * cnt[a * b + c]++ * cnt[a * b * c]++ 就算出**此骰子可組合出的點數出現幾次**啦！我寫的AC程式碼 ```cpp #include <iostream> #define int long long using namespace std; signed main() { int q,cnt[1000005] = {},n; scanf("%lld",&q); for(int a=1;a<=100;a++){ for(int b=1;b<=100;b++){ for(int c=1;c<=100;c++){ cnt[a+b+c]++; cnt[a*b+c]++; cnt[a+b*c]++; cnt[a*b*c]++; } } } for(int i=0;i<q;i++){ scanf("%lld",&n); printf("%lld\n",cnt[n]); } return 0; } ``` ### 延伸思考 1. [如果數字範圍是 -1000000 至 1000000 還能用類似的方法解嗎？](https://hackmd.io/@Cheng0928/MagicalArray#%E5%A6%82%E6%9E%9C%E6%95%B8%E5%AD%97%E7%AF%84%E5%9C%8D%E6%98%AF--1000000-%E8%87%B3-1000000-%E9%82%84%E8%83%BD%E7%94%A8%E9%A1%9E%E4%BC%BC%E7%9A%84%E6%96%B9%E6%B3%95%E8%A7%A3%E5%97%8E%EF%BC%9F) 2. [要能使用此方法，出現的數字最大和最小值差距最大能到多大？](https://hackmd.io/@Cheng0928/MagicalArray#%E8%A6%81%E8%83%BD%E4%BD%BF%E7%94%A8%E6%AD%A4%E6%96%B9%E6%B3%95%EF%BC%8C%E5%87%BA%E7%8F%BE%E7%9A%84%E6%95%B8%E5%AD%97%E6%9C%80%E5%A4%A7%E5%92%8C%E6%9C%80%E5%B0%8F%E5%80%BC%E5%B7%AE%E8%B7%9D%E6%9C%80%E5%A4%A7%E8%83%BD%E5%88%B0%E5%A4%9A%E5%A4%A7%EF%BC%9F) 3. [如果保證每個數字出現次數不超過 200 次，數字範圍能夠有多大，有簡單的方法能讓數字範圍更大嗎？](https://hackmd.io/@Cheng0928/MagicalArray#%E5%A6%82%E6%9E%9C%E4%BF%9D%E8%AD%89%E6%AF%8F%E5%80%8B%E6%95%B8%E5%AD%97%E5%87%BA%E7%8F%BE%E6%AC%A1%E6%95%B8%E4%B8%8D%E8%B6%85%E9%81%8E-200-%E6%AC%A1%EF%BC%8C%E6%95%B8%E5%AD%97%E7%AF%84%E5%9C%8D%E8%83%BD%E5%A4%A0%E6%9C%89%E5%A4%9A%E5%A4%A7%EF%BC%8C%E6%9C%89%E7%B0%A1%E5%96%AE%E7%9A%84%E6%96%B9%E6%B3%95%E8%83%BD%E8%AE%93%E6%95%B8%E5%AD%97%E7%AF%84%E5%9C%8D%E6%9B%B4%E5%A4%A7%E5%97%8E%EF%BC%9F) #### 如果數字範圍是 -1000000 至 1000000 還能用類似的方法解嗎？這個問題有兩種解法 1. 開兩個陣列，**一個儲存負數的資訊、一個儲存正整數的資訊** 2. 把數字平移，原本 cnt[i] 是儲存 i 的資訊，**改成 cnt[i] 儲存的是 i+1000000 的出現次數**就解決了，也就是說**在 i 的最大值與 i 的最小值相差不會過大的情況下可以直接平移數值來使用cnt的方法**喔~ --- #### 要能使用此方法，出現的數字最大和最小值差距最大能到多大？這和**記憶體使用量**有關，如果使用上題的第二種解法，我們的陣列需要開到 **`int cnt[ i 的最大值 - i 的最小值 + 1 ]`** 那我們會需要 **( i 的最大值 - i 的最小值 + 1 ) * 4 bytes(因 1 個 int 是 4 bytes)** [NHDK TPR#11 C. Gunjyo 與骰子](https://hackmd.io/@Cheng0928/MagicalArray#NHDK-TPR11-C-Gunjyo-%E8%88%87%E9%AA%B0%E5%AD%90)這題的記憶體限制就是256megabytes ![](https://i.imgur.com/Zw3ujTF.png) **256 MB = 256 * 2 ^ 20 bytes** 此題陣列最多可以開 **64 * 2 ^ 20** **此題就是要知道如何計算可用的記憶體** Tips：要使用此方法，數字範圍就不能超過約 6 * 10 ^ 7 --- #### 如果保證每個數字出現次數不超過 200 次，數字範圍能夠有多大，有簡單的方法能讓數字範圍更大嗎？其實只要**把 int cnt[x] 改成 unsigned char cnt[x]** 就好了！雖然 char 不是拿來存整數的，但它終究**可對應到 0~255** 且可做整數運算。如果我們把 int 改成 unsigned char 的話，**陣列中的每個東西只會使用 1 byte** ，這樣**陣列最大就可以開到 256 * 2 ^ 20** ，直接比原本增加了 4 倍的大小！ **這是一種節省記憶體的方式** --- ### [ABC 200 C - Ringo's Favorite Numbers 2](https://atcoder.jp/contests/abc200/tasks/abc200_c) 題目簡介(詳細請點標題連結) > 給你一個長度為 N (2 <= N <= 10 ^ 5) 的序列， > 請你從中找出兩個數字差為 200 倍數的有幾組這題你要發現**若某數和某數除以 200 的餘數相同，兩者的差必為 200 的倍數**(可自己證明看看) 所以說我們只要記錄某數除以 200 的餘數出現幾次，在去算組合就好了(組合算法：假設 a 數出現了 n 次，就會有 (n * (n - 1) ) / 2 種組合) 以下為我寫的AC程式碼 ```cpp #include <iostream> #define int long long using namespace std; int cnt[200]; int ans; signed main() { cin.tie(0);ios::sync_with_stdio(false); int n; cin >> n; for(int i=0;i<n;i++){ int num; cin >> num; cnt[num%200]++; } for(int i=0;i<200;i++){ ans+=(cnt[i] * (cnt[i] - 1)) / 2; } cout << ans; } ``` ### [ABC 152 D - Handstand 2](https://atcoder.jp/contests/abc152/tasks/abc152_d) 題目簡介(詳細請點標題連結) > 請你在 1 ~ N (1 <= N <= 2 * 10 ^ 5) 中找出 a, b 兩數 > a 的最大位數等於 b 最小位數並且 a 的最小位數等於 b 的最大位數共有幾種組合這題把數字轉換成字串會變得比較好做，只要去紀錄最大位數為 i ，最小位數為 j 的數出現幾次，再用 cnt[ i ][ j ] * cnt[ j ][ i ] 得到答案就好了以下為我寫的AC程式碼 ```cpp #include <iostream> #include <string> #define int long long using namespace std; int cnt[10][10]; signed main() { int n; cin >> n; for(int i = 1;i <= n;i++){ string s = to_string(i); cnt[s[0] - '0'][s.back() - '0']++; } int ans = 0; for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ ans+=cnt[i][j] * cnt[j][i]; } } cout << ans; return 0; } ``` ## 用陣列儲存每個東西的位置這東西我不知道怎麼解釋，所以就直接進入例題吧www 例題： * [ABC 250 C - Adjacent Swaps](https://hackmd.io/@Cheng0928/MagicalArray#ABC-250-C---Adjacent-Swaps) ### [ABC 250 C - Adjacent Swaps](https://atcoder.jp/contests/abc250/tasks/abc250_c) 題目簡介(詳細請點標題連結) > 有長度為 N (2 <= N <= 2 * 10 ^ 5) 的序列，序列初始值為 1, 2, 3 ... N， > 有 Q (1 <= Q <= 2 * 10 ^ 5) 個操作 xi，每個操作都會將數值 xi 和右邊的數值交換 > (若右邊沒有數值則和左邊的數值交換) 這題要開兩個陣列，**一個紀錄序列裡的數值，一個紀錄每個數值的位置** 也就是標題所說的，**用陣列儲存每個東西的位置** 以下為我寫的AC程式碼 ```cpp #include <iostream> #define int long long using namespace std; signed main() { int n, q; cin >> n >> q; int b[n+1], pos[n+1]; for(int i=1;i<=n;i++){ b[i] = i; pos[i] = i; } for(int i=0;i<q;i++){ int x; cin >> x; int pos_a, pos_b; int v0, v1; pos_a = pos[x]; pos_b = (pos[x] +1 > n ? n-1 : pos[x] +1); v0 = b[pos_a]; v1 = b[pos_b]; swap(b[pos_a], b[pos_b]); swap(pos[v0],pos[v1]); } for(int i=1;i<=n;i++){ cout << b[i] << ' '; } return 0; } ``` ## 陣列打表這個觀念很簡單，通常沒有規律的題目就是用這個方式例題 * [ABC 062 A - Grouping](https://hackmd.io/@Cheng0928/MagicalArray#ABC-062-A---Grouping) ### [ABC 062 A - Grouping](https://atcoder.jp/contests/abc062/tasks/abc062_a) 題目簡介(詳細請點標題連結) > 把 1 ~ 12 的數字分為三組 > group 1 : > 1, 3, 5, 7, 8, 12 > > group 2 : > 4, 6, 9, 11 > > group 3 : > 2 > 問你 x 和 y 是否在同一組可以看出**三組完全沒有任何規律**，那其實只要直接先把**每個數字在哪個組別存在一個陣列裡就好了** 以下為我寫的AC程式碼 ```cpp #include <iostream> using namespace std; int main() { int group[13]{ 0,1,3,1,2,1,2,1,1,2,1,2,1 }; int a,b; cin >> a >> b; cout << (group[a] == group[b] ? "Yes" : "No"); return 0; } ``` ## 個人學習心得我相信很多人也和我一樣，在學這章時，有些題目明明就是同樣的概念，卻想了半天才解出來，這可能是因為你還是很不確定**甚麼情況下要用甚麼概念、甚麼方式去解題**，像是[ABC 152 D - Handstand 2](https://hackmd.io/@Cheng0928/MagicalArray#ABC-152-D---Handstand-2)這題，我剛開始看到這題的時候完全不能理解要怎麼把[用陣列儲存索引值資訊](https://hackmd.io/@Cheng0928/MagicalArray#%E7%94%A8%E9%99%A3%E5%88%97%E5%84%B2%E5%AD%98%E7%B4%A2%E5%BC%95%E5%80%BC%E8%B3%87%E8%A8%8A)這個觀念套用在此題上，直到後來上課才發現可以把數值轉換成字串來解，這就代表我的解題經驗十分不足，這時AA競程的題單就派上用場了，讓我對於這章更加熟練，也希望各位讀者可以勤加練習。