---
# System prepended metadata

title: 108學年度進階班期中考考題題解

---

{%hackmd theme-dark %}

# 108學年度進階班期中考考題題解

## 競賽用hello world
這題寫不出來請重修初階班
```cpp=
#include<iostream>
int main(){
    std::cout<<"hello, world";
    return 0;
}
```

## pika chu~~~
這一題是水題，不過要注意的是就是最後一筆測資
$>50M$，所以要用IO優化才不會TLE
```cpp=
#define endl '\n'
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
}
```
## 爬樹爬爬爬
這一題的標準解法是在class node裡面多一個變數來維護樹高
再用我在題目敘述裡給的
$\begin{cases}葉子的高=1\\葉子以外的節點的高是 max(左子樹高,右子樹高)+1\end{cases}$
來做更新
```cpp=
class node{
public:
	int k,h;//h為高度
	node *l,*r;
	node(const int& x):k(x),h(0){
		l=r=nullptr;
	}
};
int update(node* cur){
	if(!cur) return 0;
	else return cur->h=max(update(cur->l),update(cur->r))+1;
}
```

## a186 短還要更短
壓字串的時候要注意以下幾點
1. 以#開頭的就直接輸出整行
2. 如果在開頭不是\#的一行中有空白$\begin{cases}空白的前後如果都是英文字母或數字就不能省\\其中有一個是符號就可以省\end{cases}$
3. "或'裡的東西都不能丟
```cpp=
if(str.front()=='#'){
    cout<<str;getline(cin,str);
    c=0;cout<<str<<endl;
}else{
    cout<<(isalnum(c)&&isalnum(str.front())?" ":(c=='_'||str.front()=='_'?" ":""))<<str;
    c=str.back();
    if(str.back()=='\''||str.back()=='\"')
        while(cin.get(c),cout<<c,c!='\''&&c!='\"')
            if(c=='\\'){cin>>c,cout<<c;}
}
```

## 挖石油發大財
這一題基本上就是按照推入 BST 元素的方法搜尋已存在的元素
就是目標小於當下節點的值時往左找，大於時往右找
但如果預定路線遇到 nullptr 時就代表沒有該元素

照著以上思維可以拿到 (NA 60%)
(NA 80%) 要加I/O優化
```cpp=

```