# 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 。
一個 矩陣A 可以經過一連串的旋轉與翻轉操作後，轉換成 新矩陣B 。
如圖二， A 經過翻轉與兩次旋轉後，可以得到 B 。
給定 矩陣B 和一連串的操作，請算出 ==**原始的**== 矩陣A 。
## 解析&程式碼
:::warning
基本的EOF結尾和二維陣列讀入我不會討論，如果有問題請翻翻書或是看我的講義
:::
我的作法是把翻轉和旋轉分開寫一個執行式
由上到下開始解釋
turn是翻轉
:::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++的除法會捨去小數部分，所以奇數的正中間那一欄不會也不需要交換
:::
難度較大的是旋轉，需要不錯的想像力
我老實講，我會想到這個作法可以說是通靈出來的，超級剛好。
不過其實有一點訣竅:
因為一開始我想的是先完成旋轉，再想辦法調數字，而他跟正確答案之間只有差距一個
**如果你問我說題目不是要求順時針旋轉嗎?
請你回去看題目我幫你高亮粗體的那三個字**
```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 。$
## 解析
這題其實就是排程問題，把線段長度看成是一個工作(*如果看成會議可能會更好*)，但工作可中途加入，找到最長的工作時間(對 我們現在是萬惡的資本方)，這題用了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;
}
```
Sign in with Wallet
Connect another wallet