---
# System prepended metadata

title: APCS 2016年03月題解
tags: [APCS]

---

# APCS 2016年03月題解
## 第一題 成績指標
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=b964
### 解套
N/A
### 題目分析
這題大概分成兩個部分，分別是排序及找到符合題目要求的數字

排序的地方我是直接用內建排序解決，不過考慮到測資大小泡沫排序之類的也會過
(不要暴力排序甚麼都好說)

第二部分我是假設最高不及格分數為-1，最低及格分數為101(剛好都超出可能範圍)
接著就一一遍歷，如果不及格就與最高不及格分數取最大值，反之就與最低及格分數取最小值，
最後輸出即可
另外如果兩個數字最後跟初始值一樣代表沒有不及格/及格的人，就改成輸出best case/worst case

時間複雜度$O(nlogn)$
### 解題流程
輸入$→$排序$→$遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,mxfail=-1,mnpass=101;
vector<int>v;
```
n同題述，mxfail為最高不及格分數，mnpass為最低及格分數，v存分數
#### 輸入、排序
```cpp=6
cin>>n;
v.assign(n,0);
for(int i=0;i<n;i++)cin>>v[i];
sort(v.begin(),v.end());
```
#### 輸出、決定數字
```cpp=10
for(int i:v){
    cout<<i<<" ";
    if(i<60)mxfail=max(mxfail,i);
    else mnpass=min(mnpass,i);
}
cout<<"\n";
if(mxfail==-1)cout<<"best case\n";
else cout<<mxfail<<"\n";
if(mnpass==101)cout<<"worst case";
else cout<<mnpass;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,mxfail=-1,mnpass=101;
vector<int>v;
int main(){
    cin>>n;
    v.assign(n,0);
    for(int i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end());
    for(int i:v){
        cout<<i<<" ";
        if(i<60)mxfail=max(mxfail,i);
        else mnpass=min(mnpass,i);
    }
    cout<<"\n";
    if(mxfail==-1)cout<<"best case\n";
    else cout<<mxfail<<"\n";
    if(mnpass==101)cout<<"worst case";
    else cout<<mnpass;
}
```
## 第二題 矩陣轉換
### 題目敘述 
https://zerojudge.tw/ShowProblem?problemid=b965
### 解套
N/A
### 題目分析
這題乍看下有些複雜，可能會覺得很多東西不知道要怎麼處理，像是要怎麼做反操作，或是長寬改變要怎麼處理之類的，以下會一一解釋
我假設當前有r行c列，陣列名arr

1. 要注意是反操作
最一開始要注意的是題目給的是「操作完的矩陣」，要求的是「原始矩陣」，所以所有操作都要反著做，而且操作順序也要相反
2. 如何處理長寬交換問題
我的作法是直接把長跟寬都開到最大，交換長寬時就真的交換r跟c，就能避免比較複雜的操作
3. 兩種操作的反操作
翻轉的反操作依然是翻轉，只要以中間一列為中心交換列就好
至於旋轉的反操作比較複雜，因為原操作是向右旋轉，所以反操作要向左旋轉
除了r跟c要交換以外，哪一個移到哪一格也很重要
![](https://hackmd.io/_uploads/H1Cq4gMv2.png)
由圖可知旋轉(正操作)後，「列座標」會變成「行座標」，
而「行座標」會變成「列座標」，但是順序要前後交換
簡而言之原本座標$(i,j)$會變成$(c-1-j,i)$
若要反操作就是$(i,j)$變成$(j,r-1-i)$
4. 如何操作
我開一個大小跟arr一樣的陣列tmp，要操作時先把arr複製到tmp，
再用tmp當基準回推arr

喔對然後這題是多筆測資

這樣操作完就能得到原本的陣列了
時間複雜度$O(rcm)$
### 解題流程
輸入$→$倒著處理操作$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int r,c,m,arr[10][10],tmp[10][10];
vector<int>ops;
```
ops存操作，其他同題述/前述
#### 輸入
```cpp=6
while(cin>>r>>c>>m){
    for(int i=0;i<r;i++)for(int j=0;j<c;j++)cin>>arr[i][j];
    ops.assign(m,0);
    for(int i=0;i<m;i++)cin>>ops[i];
```
第8行先把ops變成需要的大小
#### 倒著操作
```cpp=10
    while(ops.size()){
        if(ops.back()==1){
            for(int i=0;i<r/2;i++)for(int j=0;j<c;j++){
                swap(arr[i][j],arr[r-i-1][j]);
            }
        }
        else{
            for(int i=0;i<r;i++)for(int j=0;j<c;j++)tmp[i][j]=arr[i][j];
            swap(r,c);
            for(int i=0;i<r;i++)for(int j=0;j<c;j++){
                arr[i][j]=tmp[j][r-1-i];
            }
        }
        ops.pop_back();
    }
```
處理方式同前述
翻轉就真的一個一個swap(第12-14行)

旋轉時先複製arr到tmp(第17行)
接著交換行列座標(第18行)
#### 輸出
```cpp=25
    cout<<r<<" "<<c<<"\n";
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++)cout<<arr[i][j]<<(j==c-1?"":" ");
        cout<<"\n";
    }
```
需要注意的是結尾沒有空白
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int r,c,m,arr[10][10],tmp[10][10];
vector<int>ops;
int main(){
    while(cin>>r>>c>>m){
        for(int i=0;i<r;i++)for(int j=0;j<c;j++)cin>>arr[i][j];
        ops.assign(m,0);
        for(int i=0;i<m;i++)cin>>ops[i];
        while(ops.size()){
            if(ops.back()==1){
                for(int i=0;i<r/2;i++)for(int j=0;j<c;j++){
                    swap(arr[i][j],arr[r-i-1][j]);
                }
            }
            else{
                for(int i=0;i<r;i++)for(int j=0;j<c;j++)tmp[i][j]=arr[i][j];
                swap(r,c);
                for(int i=0;i<r;i++)for(int j=0;j<c;j++){
                    arr[i][j]=tmp[j][r-1-i];
                }
            }
            ops.pop_back();
        }
        cout<<r<<" "<<c<<"\n";
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++)cout<<arr[i][j]<<(j==c-1?"":" ");
            cout<<"\n";
        }
    }
}
```
## 第三題 線段覆蓋長度
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=b966
### 解套
N/A
### 題目分析
很明顯地我們不能開一個陣列然後一個一個加最後在全部統計一遍

這題我的作法是用pair紀錄每個線段的開頭與結尾，然後再由小到大排序
這時候就會發現**有重疊的線段一定會連在一起**，於是我們就可以由前往後遍歷，看每個線段跟後面一個線段是否有重疊，如果沒有就直接更新答案，不然就把兩者合併成一個線段

實作上我是用deque$<$pair$>$，取名叫dq
當dq大小比1大時，不斷比較第一個與第二個線段，這時如果
1. 兩線段不重疊
直接把答案加上第一個線段的長度，然後把第一個線段pop掉
2. 兩線段重疊
用第一個線段的資訊更新第二個線段，然後把第一個線段pop掉

最後當只剩一個線段時直接更新答案

時間複雜度$O(nlogn)$
### 解題流程
輸入$→$排序$→$合併、計算$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
```
我就懶
#### 變數宣告
```cpp=5
int n,ans=0;
deque<pair<int,int>>dq;
```
n同題述，ans存答案，dq同前述
#### 輸入、排序
```cpp=8
cin>>n;
dq.assign(n,{});
for(int i=0;i<n;i++)cin>>dq[i].F>>dq[i].S;
sort(dq.begin(),dq.end());
```
第9行初始化dq
#### 合併線段、計算答案
```cpp=12
while(dq.size()){
    if(dq.size()==1){
        ans+=dq[0].S-dq[0].F;
        dq.pop_front();
    }
    else{
        if(dq[0].S>=dq[1].F){
            dq[1].F=min(dq[1].F,dq[0].F);
            dq[1].S=max(dq[0].S,dq[1].S);
            dq.pop_front();
        }
        else{
            ans+=dq[0].S-dq[0].F;
            dq.pop_front();
        }
    }
}
```
規則同前述
更新時開頭要最小，結尾要最大(第19、20行)
#### 輸出
```cpp=29
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n,ans=0;
deque<pair<int,int>>dq;
int main(){
    cin>>n;
    dq.assign(n,{});
    for(int i=0;i<n;i++)cin>>dq[i].F>>dq[i].S;
    sort(dq.begin(),dq.end());
    while(dq.size()){
        if(dq.size()==1){
            ans+=dq[0].S-dq[0].F;
            dq.pop_front();
        }
        else{
            if(dq[0].S>=dq[1].F){
                dq[1].F=min(dq[1].F,dq[0].F);
                dq[1].S=max(dq[0].S,dq[1].S);
                dq.pop_front();
            }
            else{
                ans+=dq[0].S-dq[0].F;
                dq.pop_front();
            }
        }
    }
    cout<<ans;
}
```
## 第四題 第4題 血緣關係
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=b967
### 解套
求樹直徑
### 題目分析
因為N個節點，N-1個邊，所這是一棵[樹](https://oi-wiki.org/graph/tree-basic/)
而題目問的是血緣關係最遠的兩個人距離多遠，也就是這棵樹的[樹直徑](https://oi-wiki.org/graph/tree-diameter/)
詳細的解釋可以看上面兩個連結，我用的是兩次dfs的方法

(喔對然後好像還可以從根dfs，然後存最遠與第二遠的距離再相加，應該會比較快)

如此時間複雜度$O(n)$
### 解題流程
輸入、存圖$→$兩次dfs$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,a,b,fardot,dep[100000];
vector<int>v[100000];
```
n,a,b同題述，fardot存最遠的點，dep存個點與起始點距離，v存圖(鄰接串列)
#### dfs函式宣告
```cpp=6
void dfs(int id){
    for(int i:v[id]){
        if(dep[i]==0){
            dep[i]=dep[id]+1;
            dfs(i);
        }
    }
    if(dep[id]>dep[fardot])fardot=id;
    return;
}
```
基本的dfs，只是多了跟新最遠點的第13行
#### 輸入優化
```cpp=16
ios::sync_with_stdio(0);
cin.tie(0);
```
本題多筆測資且輸入多，不加會TLE
#### 輸入、初始化、存圖
```cpp=18
while(cin>>n){
    for(int i=0;i<n;i++)v[i].clear();
    for(int i=0;i<n;i++)dep[i]=0;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
```
先清空圖(第19行)(因為有多筆測資，不能被前一筆數據干擾)
還要初始化距離(第20行)(理由同上)
接著就是輸入邊並存起來，因為我們會從隨便一個節點開始，所以要當無向邊看
#### 找樹直徑、輸出
```cpp=26
    fardot=0;
    dep[0]=1;
    dfs(0);
    int st=fardot;
    for(int i=0;i<n;i++)dep[i]=0;
    dep[st]=1;
    dfs(st);
    cout<<dep[fardot]-dep[st]<<"\n";
```
第一次dfs可以從隨便一個點開始，所以我選0
先把最遠點設為0，距離設為1，並從0開始dfs，就能得到離0最遠的一個點
接著把初始點st設為fardot，再重複一次上述操作，就能得到與st最遠的點
兩者距離相減就是答案
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,a,b,fardot,dep[100000];
vector<int>v[100000];
void dfs(int id){
    for(int i:v[id]){
        if(dep[i]==0){
            dep[i]=dep[id]+1;
            dfs(i);
        }
    }
    if(dep[id]>dep[fardot])fardot=id;
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n){
        for(int i=0;i<n;i++)v[i].clear();
        for(int i=0;i<n;i++)dep[i]=0;
        for(int i=0;i<n-1;i++){
            cin>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        fardot=0;
        dep[0]=1;
        dfs(0);
        int st=fardot;
        for(int i=0;i<n;i++)dep[i]=0;
        dep[st]=1;
        dfs(st);
        cout<<dep[fardot]-dep[st]<<"\n";
    }
}
```