---
# System prepended metadata

title: APCS 2016  3月
tags: [C++, APCS(題解)]

---

# P1 [成績指標](https://zerojudge.tw/ShowProblem?problemid=b964)
## 題目
一次考試中，於所有及格學生中獲取最低分數者最為幸運，反之，於所有不及格同學中，獲取最高分數者，可以說是最為不幸，而此二種分數，可以視為成績指標。

請你設計一支程式，讀入全班成績(人數不固定)，請對所有分數進行排序，並分別找出不及格中最高分數，以及及格中最低分數。

當找不到最低及格分數，表示對於本次考試而言，這是一個不幸之班級，此時請你印出「worst case」；反之，當找不到最高不及格分數時，請你印出「best case」。

( 註：假設及格分數為 60 )。 
## 解析
我只需要宣告一個陣列，將所有元素置入後sort，求最接近的只需要用一個迴圈歷遍尋找所需的兩個元素即可。
## 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define a6isweak ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define pr pair<int,int>
int main() {
    a6isweak;
    int n;
    cin>>n;
    int a[20];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    cout<<endl;
    int best=-1,worst=-1;//因為題目題目保證分數範圍
    for(int i=0;i<n;i++)
    {
        if(a[i]>=60)
        {
            best=a[i];
            break;//因為已經排序，所以找到的第一個必然是最小的
        }
        else
            worst=a[i];
    }
    if(worst==-1)
        cout<<"best case"<<endl;
    else
        cout<<worst<<endl;
    if(best==-1)
        cout<<"worst case"<<endl;
    else
        cout<<best<<endl;

}
```
# P2 [矩陣轉換](https://zerojudge.tw/ShowProblem?problemid=b965)
## 題目
矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row) ，直排稱為行 (column) ，其中以 X_ij 來表示 矩陣X 中的第 i 列第 j 行的元素。
如圖一， X_32 = 6 。

我們可以對矩陣定義兩種操作如下：
　　翻轉：即第一列與最後一列交換、第二列與倒數第二列交換、… 依此類推。
　　旋轉：將矩陣以順時針方向轉 90 度。

如圖一， 矩陣X 翻轉後可得到 Y ，將 矩陣Y 再旋轉後可得到 Z 。
![image](https://hackmd.io/_uploads/BJP8uvnPa.png)
一個 矩陣A 可以經過一連串的旋轉與翻轉操作後，轉換成 新矩陣B 。
如圖二， A 經過翻轉與兩次旋轉後，可以得到 B 。

給定 矩陣B 和一連串的操作，請算出 ==**原始的**== 矩陣A 。
![image](https://hackmd.io/_uploads/ryKduP2vT.png)
## 解析&程式碼
:::warning
基本的EOF結尾和二維陣列讀入我不會討論，如果有問題請翻翻書或是看我的講義
:::
我的作法是把翻轉和旋轉分開寫一個執行式
由上到下開始解釋
turn是翻轉
![image](https://hackmd.io/_uploads/S1zyNwhw6.png)
:::warning
因為m-y是y+1(陣列位置從0開始)
所以要記得減掉1

如果無法理解可以y=0,1,2.\.\.\.\.\.帶入試試看就會理解
:::
```cpp=
void turn()
{
    for(int j=0;j<c;j++)
    {
        for(int i=0;i<r/2;i++)
        {
            swap(a[i][j],a[r-i-1][j]);
        }
    }
}
```
:::warning
因為c++的除法會捨去小數部分，所以奇數的正中間那一欄不會也不需要交換
:::
難度較大的是旋轉，需要不錯的想像力
![image](https://hackmd.io/_uploads/Sy6l8P2v6.png)

我老實講，我會想到這個作法可以說是通靈出來的，超級剛好。
不過其實有一點訣竅:
因為一開始我想的是先完成旋轉，再想辦法調數字，而他跟正確答案之間只有差距一個

**如果你問我說題目不是要求順時針旋轉嗎?
請你回去看題目我幫你高亮粗體的那三個字**

```cpp=
void rev()
{
    int d[20][20]={};
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            d[j][i]=a[i][j];
        }
    }
    memset(a,0,sizeof(a));//把a變成全部都是0
    swap(r,c);//因為翻轉會把長度寬度互換
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            a[i][j]=d[i][j];
        }
    }
    turn();
}
```
:::danger
因為我用了turn()
所以這個必須寫在下面，否則會報錯:[turn()未宣告]
:::
最後回來到main()
我用一個did陣列來表示他對陣列做了什麼，如同我們小學學的驗算一樣，我們必須把行為倒轉過來，才可以回到原本的樣子，再把該做做好
```cpp=
    int did[20];
    for(int i=0;i<m;i++)
        cin>>did[i];
    reverse(did,did+m);
    for(int i=0;i<m;i++)
    {
       if(did[i]==1)
           turn();
       else
           rev();
    }
```
把所有程式碼統整好，得到答案
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define a6isweak ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"//"\n"效率較好
int r,c,m;
int a[20][20];
void turn()
{
    for(int j=0;j<c;j++)
    {
        for(int i=0;i<r/2;i++)
        {
            swap(a[i][j],a[r-i-1][j]);
        }
    }
}
void rev()
{
    int d[20][20]={};
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            d[j][i]=a[i][j];
        }
    }
    memset(a,0,sizeof(a));//把a變成全部都是0
    swap(r,c);//因為翻轉會把長度寬度互換
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            a[i][j]=d[i][j];
        }
    }
    turn();
}
int main() {
    a6isweak;
    while(cin>>r>>c>>m)
    {
            for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
                cin>>a[i][j];
        }
        int did[20];
        for(int i=0;i<m;i++)
            cin>>did[i];
        reverse(did,did+m);
        for(int i=0;i<m;i++)
        {
            if(did[i]==1)
                turn();
            else
                rev();
        }
        cout<<r<<' '<<c<<endl;
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                cout<<a[i][j];
                if(j!=c-1)//嚴格比對，所以不留行尾空白
                    cout<<' ';
            }
            cout<<endl;
        }
    }
}
```
:::spoiler 使用rev()和turn()的意義?
可以使得程式碼的可讀性變好，讓更多人看懂到底在幹嘛
:::
:::spoiler 陣列先開好大小的意義?
可以使得RE(Runtime Error)的機會大幅下降，保證不會因為index超過而程式壞掉
:::
# P3 
# [線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966)
# [線段覆蓋長度 測資加強版](https://zerojudge.tw/ShowProblem?problemid=f855)
## 題目
給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。

$例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。$
![image](https://hackmd.io/_uploads/HkZyymyua.png)
## 解析
這題其實就是排程問題，把線段長度看成是一個工作(*如果看成會議可能會更好*)，但工作可中途加入，找到最長的工作時間(對 我們現在是萬惡的資本方)，這題用了priority_queue，但其實只需要用pair開一個陣列下去sort也可以，時間複雜度都是$O(nlogn)$*(pq常數較大，但這題沒有那麼緊，$O(n^2)$應該也會過)*
## 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define a6isweak ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define pr pair<int,int>
int main() {
    a6isweak;
    int n;
    cin>>n;
    priority_queue<pr,vector<pr>,greater<pr>> pq;
    for(int i=0;i<n;i++)
    {
        int b,e;
        cin>>b>>e;
        pq.push({b,e});
    }
    int sum=0,edt=pq.top().second,bgt=pq.top().first;
    pq.pop();
    while(!pq.empty())
    {
        if(pq.top().second<=edt)
        {
            pq.pop();
        }
        else if(pq.top().first<edt)
        {
            edt=pq.top().second;
        }
        else
        {
            sum+=edt-bgt;
            bgt=pq.top().first;
            edt=pq.top().second;
        }
    }
    sum+=edt-bgt;
    cout<<sum<<"\n";
}

```
因為有排序，保證開始時間遞增，所以當結束時間比現在的小的話，那麼就是個無效的工作，第一個if就是要剃除無效的工作，elseif是指如果下一個工作開始時間小於結束時間，那麼就等這個做完繼續做下去，else是指中間有空閒時間休息，那我先把前面的工作時長做結算，再開始下一個工作。
# P4 
# [血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
## 定理
由任意點出發，與其最遠的點，必為一個樹直徑的其中一端。
## 解析&程式碼
我這裡使用的是DFS，事實上，BFS也是可行的。
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005];
bool visit[100005];
int maxd=-1,c;
void dfs(int p,int d)
{
    visit[p]=true;
    if(maxd<d)
    {
        maxd=d;
        c=p;
    }
    for(auto it:v[p])
    {
        if(visit[it])
            continue;
        dfs(it,d+1);
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int b,e;
        cin>>b>>e;
        v[b].push_back(e);
        v[e].push_back(b);
    }
    memset(visit,0,sizeof(visit));
    dfs(0,0);
    memset(visit,0,sizeof(visit));
    dfs(c,0);
    cout<<maxd<<endl;
}

```