---
# System prepended metadata

title: 電科社進階組練習題

---

# 陣列練習題目與解答
C++程式碼由社長提供
Python由教學:羅浚原、甘育銘提供
命名跟寫法可能有些醜ww
程式可以有很多解法，僅供參考
## [a022 迴文](https://zerojudge.tw/ShowProblem?problemid=a022)
### 題解:

將字串反轉後和原本比較，就能知道字串是否為回文
所以目標是將字串反轉

```
   aabca
-> acbaa
```
反轉的方式是用 `(n-1) - 索引值`的能得到相反的索引
| Index       | 0   | 1   | 2   | 3   | 4   |
| ----------- | --- | --- | --- | --- |:--- |
| n -1 -index | 4   | 3   | 2   | 1   | 0   |


C++:
```Cpp=
#include <iostream>
using namespace std;

int main() {
    
    string s;
    cin >> s;
    
    bool ans = true;
    for(int i=0;i<s.length();i++){
        if(s[i] != s[ s.length()-1 -i ]){
            ans = false;
        }
    }
    //for(int i=0;i<s.length()/2;i++){
    //    if(s[i] != s[ s.length()-1 -i ]){
    //        ans = false;
    //    }
    //}
        
    if(ans){
        cout << "yes" << endl;
    }else{
        cout << "no" << endl;
    }
    return 0;
    //補充三元運算# cout << 判斷? "True" : "False" << endl;
}
```
Python:
```python=
s=input()
n = len(s)
for i in range(n // 2):
    if s[i] != s[n - i - 1]:
        return False
return True

#更簡單的寫法
a=input()
b="".join(reversed(a))
if a==b:
  print("yes")
else:
  print("no")
#更更簡單的寫法
s=input()
if(s==s[::-1])：
  print("yes")
else：
  print("no")
# 補充三元運算： print("yes" if s == s[::-1] else "no")
# print( "True" if 判斷 else "False" )

```
## [g275 APCS1.七言對聯](https://zerojudge.tw/ShowProblem?problemid=g275)
### 題解:
先將輸入儲存成陣列，兩個一維or一個二維都可，這邊先用一維
分別對題目的三個規則寫判斷式
要注意題目判斷式是判斷`沒有違規`
而判斷`有違規`就輸出比較好寫
所以判斷語句要相反 ( != -> == ; and -> or)
C++:
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        int l1[7] = {0};
        int l2[7] = {0};
        for (int j = 0; j < 7; j++){
            cin >> l1[j];
        }
        for (int j = 0; j < 7; j++){
            cin >> l2[j];
        }
        string s = "";
        if( l1[1] == l1[3] || l1[1] != l1[5] || l2[1] == l2[3] || l2[1] != l2[5] ){
            s += "A";
        }
        if ( l1[6] != 1  || l2[6] != 0 ){
            s += "B";
        }
        if(l1[1] == l2[1] || l1[3] == l2[3] || l1[5] == l2[5] ){
            s += "C";
        }

        if(s.empty()){
            s = "None";
        }
        cout << s << endl;
    }
    
}
```
Python:
```python=
n = int(input())
for _ in range(n):
    l1 = list(map(int, input().split()))
    l2 = list(map(int, input().split()))
    s = ""
    if l1[1] == l1[3] or l1[1] != l1[5] or l2[1] == l2[3] or l2[1] != l2[5]:
        s += "A"
    if l1[6] != 1 or l2[6] != 0:
        s += "B"
    if l1[1] == l2[1] or l1[3] == l2[3] or l1[5] == l2[5]:
        s += "C"
    if not s:
        s = "None"
    print(s)

```

## [d673 No Problem](https://zerojudge.tw/ShowProblem?problemid=d673)
### 題解:
測資有多筆，所以要在最外層寫while來收測資，並記錄 Case:`X`
儲存所剩下的題目數量

```
判斷:
如果 剩下的問題數 大於 當前月份所需，代表:D，所剩題目數 -= 當前需求
如果 剩下的問題數 小於 當前月份所需，代表:( 
```

```mermaid
flowchart TD
    X@{ shape: stadium, label: "程式開始" } --> A
    A@{ shape: rounded, label: "i = 0" } --> B{判斷目前月份所需}
    B -->|剩下問題數 >= 目前月份所需| C[輸出 :D]
    B -->|剩下問題數 < 目前月份所需| D["輸出 :("]
    C --> E[所剩題目數 -= 目前需求]
    D --> F["i += 1"]
    E --> F
    F{"i < 12"} -->|True| B
    F -->|False| G@{ shape: stadium, label: "程式結束" }
```
#### 法一:
迴圈每個月時
先剩下題目數 += **上**個月產生的題目
後判斷
#### 法二:
先判斷
後剩下題目數 += **這**個月產生的題目

> 補充:
> 由於計算需求是 當前剩下題目、上個月產生題目、當前消耗題目
> 所以可以在輸入消耗時同時進行運算
> 可節省再寫一次for迴圈的時間

:::spoiler C++
```cpp=
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int s; //所剩下的題目數量
    int case_num = 1;
    while (cin >> s)
    {
        if (s < 0)
            break;
        cout << "Case " << case_num++ << ":" << "\n";
        int problem[12],need;
        for (int i = 0; i < 12; i++)
            cin >> problem[i];
        for (int i = 0; i < 12; i++)
        {
            cin >> need;
            if (i>0){
                s += problem[i-1];
            }
            if (s >= need){
                cout << "No problem! :D" << endl;
                s -= need;
            }
            else
                cout << "No problem. :(" << endl;
        }
    }
    return 0;
}
```
:::
Python:
```python=
t = 0
while True:
    try:
        first = int(input())
        if first < 0 :
            break
        t+= 1

        q = list(map(int,input().split()))

        n = list(map(int, input().split()))
        canuse = first
        print(f"Case {t}:")
        for i in range(12):
            if canuse >= n[i]:
                print("No problem! :D")
                if n[i] > 0:
                    canuse -= n[i]
            else:
                print("No problem. :(")

            canuse += q[i]
                
    except:
        break

```

## [b367 翻轉世界](https://zerojudge.tw/ShowProblem?problemid=b367)
上課沒講到的題目
### 題解:
從題目範例可以知道
左上轉到右下
中上轉到中下
右上轉到左下
可以發現，當矩陣用二維陣列`[i][j]`表示時
`新[n-1 - i][n-1 - j] = 舊[i][j] `
`n-1 - i` 的原理和回文相同

C++:
```cpp=
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while(n--){
        int N,M;
        cin >> N >> M;
        int board[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                cin >> board[i][j];
            }
        }
        bool ans = true;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if (board[i][j] != board[N-1-i][M-1-j] ){
                    ans = false;
                }
            }
        }
        if (ans) cout << "go forward" << endl;
        else cout << "keep defending" << endl;
        
    }
    return 0;
}
```
Python:
```python=
t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    ans = True
    for i in range(n):
        for j in range(m):
            if board[i][j] != board[n - 1 - i][m - 1 - j]:
                ans = False
                break
        if not ans:
            break
    print("go forward" if ans else "keep defending")
```


## [b965 2016 APCS 2.矩陣翻轉 (較難)](https://zerojudge.tw/ShowProblem?problemid=b965)

標籤: 模擬、二維陣列

注意題目敘述為**從結果反推回初始，不要做反了**

建立函式來分別處理 旋轉、翻轉

上課時把 i 跟 j 搞反了sorry~
### 題解
#### **旋轉**:
![image](https://hackmd.io/_uploads/SkE1bSR0gx.png)
遇到複雜的陣列轉換
* 先把索引值畫出來
* 一次看一排來處理
* 觀察i跟j有什麼規律

以下為翻轉規律
```
新[i][j] = 舊[j][c-1 - i]
```
**怎麼知道的呢?**
首先先認知我們要兩層for迴圈才能變換二維陣列
所以有i (0~r-1) ,j (0~c-1)
舉例這些情況
i = 0 , j = 0,1,2
i = 1 , j = 0,1,2
可以把圖片中寫出的[][]中數字帶換成i跟j
當i=0時(圖中左邊畫底線情況)
0,1,2很直覺知道是j
而有一排都是1，可以觀察到他是相反於i的數字(就是 c-1 - i)
**怎麼知道他是相反於i ?**
想想i=1時他會變什麼
就是 [0][0]、[1][0]、[2][0] ，是0，也是相反於i

有規律之後就能轉換了
最後最後記得把 r跟c 交換，原因由圖片能看出


#### **翻轉**:
翻轉比旋轉簡單多了
和前面想法一樣，試著自己想看看吧
![image](https://hackmd.io/_uploads/B1McBSAAle.png)

C++:
```cpp=
#include <bits/stdc++.h>
using namespace std;

//  旋轉
vector<vector<int>> A (vector<vector<int>> b,int r,int c){
    vector<vector<int>> a(c,vector<int>(r,0));
    for (int i = 0; i < c; i++)
    {
        for (int j = 0; j < r; j++)
        {
            a[i][j] = b[j][c-1-i];
        }
    }
    return a;
}
// 翻轉
vector<vector<int>> B (vector<vector<int>> b,int r,int c){
    vector<vector<int>> a(r,vector<int>(c,0));
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            a[i][j] = b[r-1-i][j];
        }
    }
    return a;
}

int main(){

    int r,c,m;
    cin >> r >> c >> m;
    vector<vector<int>> b(r,vector<int>(c,0));
    int mks[m] = {0};

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> b[i][j];
        }
    }
    for (int i = 0; i < m; i++)
    {
        int mk;
        cin >> mks[i];
    }
    for (int i = m-1; i >=0; i--)
    {
        // cout << i << endl; 
        if (mks[i] == 0){
            b = A(b,r,c);
            int t = r;
            r = c;
            c = t;
        }
        else{
            b = B(b,r,c);
        }
    }
    cout << r << " " << c << endl;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cout << b[i][j];
            if (j != c-1){
                cout << " ";
            }
        }
        cout << endl;
    }
}
```
Python:
```python=
def flip(n):
    return n[::-1]
def spin(n):
    ri = len(n[0])
    ci = len(n)
    ni = [[0 for _ in range(ci)] for _ in range(ri)]
    for i in range(ci):
        for j in range(ri):
            ni[ri-1-j][i]= n[i][j]
    return ni


r, c, m = map(int, input().split())
n = []
for i in range(r):
    n.append(list(map(int, input().split())))
p = list(map(int, input().split()))
p = p[::-1]
for k in p:
    if k == 1:
        n = flip(n)
    else:
        n = spin(n)
print(len(n), len(n[0]))
for k in n:
    print(*k)
```


# 更多進階題(APCS三級分)
**有興趣自行練習**
## [k732. 2. 特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)
C++
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    int board[n][m] = {};
    vector<int> ans;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m;j++){
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            int sum_num = 0;

            for (int k = 0; k < n;k++){
                for (int l = 0; l < m;l++){
                    // cout << "    " << (abs(i - k) + abs(j - l)) << endl;
                    // cout <<"  " << board[i][j] << endl;
                    

                    if ((abs(i - k) + abs(j - l)) <= board[i][j])
                        sum_num += board[k][l];
                }
            }
            // cout << sum_num << endl;
            if (sum_num % 10 == board[i][j])
            {
                ans.push_back(i);
                ans.push_back(j);
            }
                // cout << i <<" "<< j << endl;
        }
    }
    cout << ans.size()/2 << endl;
    for (int i = 0; i < ans.size(); i += 2)
    {
        cout << ans[i] << " " << ans[i + 1] << endl;
    }
}
```

## [m932. 2. 蜜蜂觀察](https://zerojudge.tw/ShowProblem?problemid=m932)
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){

    int n, m, k;
    cin >> n >> m >> k;

    char l[n][m];
    for (int i = 0; i < n;i++){
        string t;
        cin >> t;
        for (int j = 0; j < m; j++)
        {
            l[i][j] = t[j];
        }
    }

    int x = 0, y = n - 1;
    set<char> type_set;

    for (int i = 0; i < k;i++){
        int a;
        cin >> a;

        if (a == 0){
            if (y-1>=0 && y-1 < n)
                y -= 1;
        }else if (a==1){
            if (x+1>=0 && x+1 < m)
                x += 1;
        }else if (a==2){
            if (x+1>=0 && x+1 < m && y+1>=0 && y+1 < n){
                x += 1;
                y += 1;
            }
        }else if (a==3){
            if (y+1>=0 && y+1 < n)
                y += 1;
        }else if (a==4){
            if (x-1>=0 && x-1 < m)
                x -= 1;
        }else if (a==5){
            if (x-1>=0 && x-1 < m && y-1>=0 && y-1 < n){
                x -= 1;
                y -= 1;
            }
        }
        cout << l[y][x];
        // cout << y << " " << x << endl;
        type_set.insert(l[y][x]);
    }

    cout << endl;
    cout << type_set.size() << endl;
}
```

## [o077. 2. 電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077 )
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){

    int n,m;
    cin >> n >> m;
    int list[n][m] = {0};
    int ans = 0;
    vector<pair<int,int>> anslist;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> list[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int s = 0;
            for (int a = 0; a < n; a++)
            {
                for (int b = 0; b < m; b++)
                {
                    int dis = abs(i-a) + abs(j-b);
                    if (dis <= list[i][j]){
                        s += list[a][b];
                    }
                }   
            }
            // cout << "log: "<< i << " "<<j << "   " <<s << endl; 
            if (s%10 == list[i][j]){
                ans ++;
                // cout << i << " " << j << endl;
                anslist.push_back(make_pair(i,j));
            }
            
        }
    }
    cout << ans << endl;
    sort(anslist.begin(),anslist.end());
    for(auto i : anslist){
        cout << i.first << " " <<i.second << endl; 
    }
    

}
```
