# 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要交換以外，哪一個移到哪一格也很重要
由圖可知旋轉(正操作)後，「列座標」會變成「行座標」，
而「行座標」會變成「列座標」，但是順序要前後交換
簡而言之原本座標$(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";
}
}
```
Sign in with Wallet
Connect another wallet