---
tags: Training
---
# 2021 NTOU summer training (beginner)
## [任何問題提問](https://forms.gle/xKAVwgY1euLV8whL9)
## 0729
* [上課影片](https://youtu.be/rAT617toV6E)
* [複雜度](https://hackmd.io/@Y68gNOsdTxGvsBZNTbpKqQ/HJfFfsh-B)
* [Standard Template Library](https://hackmd.io/@Y68gNOsdTxGvsBZNTbpKqQ/ryio2gTZS)
:::spoiler 題單
* stack
[ZJ b923](https://zerojudge.tw/ShowProblem?problemid=b923)
[ZJ c123](https://zerojudge.tw/ShowProblem?problemid=c123)
* map/set
[ZJ d492](https://zerojudge.tw/ShowProblem?problemid=d492)
[ZJ d885](https://zerojudge.tw/ShowProblem?problemid=d885)
[ZJ a091](https://zerojudge.tw/ShowProblem?problemid=a091)
* priority_queue
[ZJ b606](https://zerojudge.tw/ShowProblem?problemid=b606)
* sorting
[ZJ a528](https://zerojudge.tw/ShowProblem?problemid=a528)
* nth_element
[ZJ d476](https://zerojudge.tw/ShowProblem?problemid=d476)
:::
## 0804
* [上課影片](https://youtu.be/0WeUvhh3z1k)
* [DP](https://hackmd.io/@Y68gNOsdTxGvsBZNTbpKqQ/SJCIN4GMr#/)
:::spoiler 題單
[ZJ a133](https://zerojudge.tw/ShowProblem?problemid=a133)
[ZJ d784](https://zerojudge.tw/ShowProblem?problemid=d784)
[ZJ c112](https://zerojudge.tw/ShowProblem?problemid=c112)
[ZJ a144](https://zerojudge.tw/ShowProblem?problemid=a144)
[ZJ d378](https://zerojudge.tw/ShowProblem?problemid=d378)
[ZJ a587](https://zerojudge.tw/ShowProblem?problemid=a587)
[ZJ c001](https://zerojudge.tw/ShowProblem?problemid=c001)
:::
## 0811
* [上課影片](https://youtu.be/NKycp3HcP90)
* [greedy](https://hackmd.io/@giver/By_xYVtMr#/)
::: spoiler 題單
[Dandanjudge a071](http://203.64.191.163/ShowProblem?problemid=a071)
[Dandanjudge a073](http://203.64.191.163/ShowProblem?problemid=a073) 題目裡的[提示連結](https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html)是爛的
[Dandanjudge a074](http://203.64.191.163/ShowProblem?problemid=a074)
[Dandanjudge a075](http://203.64.191.163/ShowProblem?problemid=a075)
[Dandanjudge a076](http://203.64.191.163/ShowProblem?problemid=a076)
[Dandanjudge a078](http://203.64.191.163/ShowProblem?problemid=a078)
[Dandanjudge a079](http://203.64.191.163/ShowProblem?problemid=a079)
[Dandanjudge a080](http://203.64.191.163/ShowProblem?problemid=a080)
[Dandanjudge a081](http://203.64.191.163/ShowProblem?problemid=a081)
[Zerojudge b606](https://zerojudge.tw/ShowProblem?problemid=b606)
[Zerojudge b231](https://zerojudge.tw/ShowProblem?problemid=b231)
[Zerojudge c471](https://zerojudge.tw/ShowProblem?problemid=c471)
:::
## 0818
* [上課影片](https://youtu.be/TNk-JsfxZLA)
* [binary search](https://hackmd.io/@Y68gNOsdTxGvsBZNTbpKqQ/SkBLJSmQS#/)
:::spoiler 題單
* binary search
[Zerojudge d732](https://zerojudge.tw/ShowProblem?problemid=d732)
[Zerojudge c575](https://zerojudge.tw/ShowProblem?problemid=c575)
[Zerojudge c942](https://zerojudge.tw/ShowProblem?problemid=c942)
[Dandanjudge a120](http://203.64.191.163/ShowProblem?problemid=a120)
[Dandanjudge a121](http://203.64.191.163/ShowProblem?problemid=a121)
[Dandanjudge a122](http://203.64.191.163/ShowProblem?problemid=a122)
[Codeforces 1251D](https://codeforces.com/contest/1251/problem/D)
[Codeforces 1436C](https://codeforces.com/problemset/problem/1436/C)
* ternary search
[SPOJ KOPC12A](https://www.spoj.com/problems/KOPC12A/)
[Codeforces 578C](https://codeforces.com/contest/578/problem/C)
[Codeforces 1355E](https://codeforces.com/contest/1355/problem/E)
[Codeforces 1301B](https://codeforces.com/contest/1301/problem/B)
:::
## 0825
* [上課影片](https://youtu.be/A51xibuoIIE)
* [divide and conquer](https://hackmd.io/@Y68gNOsdTxGvsBZNTbpKqQ/rJLwuclVr#/)
* [最近點對教學](https://oi-wiki.org/geometry/nearest-points/)
:::spoiler 題單
[Zerojudge a233](https://zerojudge.tw/ShowProblem?problemid=a233)(實作merge sort)
[Zerojudge a233](https://zerojudge.tw/ShowProblem?problemid=a233)(實作quick sort)
[Zerojudge a638](https://zerojudge.tw/ShowProblem?problemid=a638)
[Zerojudge d542](https://zerojudge.tw/ShowProblem?problemid=d542)
[Codeforces gym 102569G](https://codeforces.com/gym/102569/problem/G)
[Codeforces 1111C](https://codeforces.com/contest/1111/problem/C)
[Codeforces 873D](https://codeforces.com/contest/873/problem/D)
:::
::: spoiler 最近點對sample code
```cpp=
// 最近點對
#include<bits/stdc++.h>
#define double long double
#define INF 1'000'000'000
#define MXN 3'000'005
using namespace std;
struct pt{
double x,y;
}arr[MXN],sorted_y[MXN];
struct cmp_x{
bool operator ()(const pt& lhs,const pt& rhs){
if(lhs.x != rhs.x) return lhs.x < rhs.x;
return lhs.y < rhs.y;
}
};
struct cmp_y{
bool operator ()(const pt& lhs,const pt& rhs){
if(lhs.y != rhs.y) return lhs.y < rhs.y;
return lhs.x < rhs.x;
}
};
int n;
double ans=INF;
pt Left[MXN],Right[MXN],tmp[MXN];
inline double dist(int i,int j){
return sqrt((arr[i].x-arr[j].x)*(arr[i].x-arr[j].x)+(arr[i].y-arr[j].y)*(arr[i].y-arr[j].y));
}
inline double dist(const pt& lhs,const pt& rhs){
return sqrt((lhs.x-rhs.x)*(lhs.x-rhs.x)+(lhs.y-rhs.y)*(lhs.y-rhs.y));
}
void merge(int l,int r){
int mid = (l+r)/2;
int l_num=0,r_num=0;
for(int i=l;i<=mid;i++){
if(abs(sorted_y[i].x-arr[mid].x)<ans){
Left[l_num] = sorted_y[i];
l_num++;
}
}
for(int i=mid+1;i<=r;i++){
if(abs(sorted_y[i].x-arr[mid].x)<ans){
Right[r_num] = sorted_y[i];
r_num++;
}
}
for(int i=0,j=0;i<l_num;i++){
while(j+1 < r_num && Left[i].y > Right[j].y){
j++;
}
for(int k=j;k<r_num && abs(Left[i].y-Right[k].y)<ans;k++){
ans = min(ans, dist(Left[i],Right[k]));
}
}
for(int i=0,j=0;i<r_num;i++){
while(j+1 < l_num && Right[i].y > Left[j].y){
j++;
}
for(int k=j;k<l_num && abs(Right[i].y-Left[k].y)<ans;k++){
ans = min(ans, dist(Right[i],Left[k]));
}
}
int l_id=l,r_id=mid+1,id=0; //merge sort
while(l_id<=mid && r_id<=r){
if(sorted_y[l_id].y < sorted_y[r_id].y){
tmp[id++] = sorted_y[l_id++];
}
else{
tmp[id++] = sorted_y[r_id++];
}
}
while(l_id<=mid) tmp[id++]=sorted_y[l_id++];
while(r_id<=r) tmp[id++]=sorted_y[r_id++];
for(int i=l;i<=r;i++) sorted_y[i] = tmp[i-l];
}
void closest_pair(int l,int r){
if(r-l<=3){
for(int i=l;i<=r;i++){
for(int j=i+1;j<=r;j++){
ans=min(ans,dist(i,j));
sort(sorted_y+l,sorted_y+r+1,cmp_y());
}
}
return;
}
int mid = (l+r)/2;
closest_pair(l,mid);
closest_pair(mid+1,r);
merge(l,r);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i].x>>arr[i].y;
sorted_y[i] = arr[i];
}
sort(arr,arr+n,cmp_x());
closest_pair(0,n-1);
cout<<fixed<<setprecision(4)<<ans<<endl;
return 0;
}
// merge sort 的 merge
vector<int> merge(vector<int> left,vector<int> right){
vector<int> ret;
int left_index=0;
int right_index=0;
while(left_index < left.size() && right_index < right.size()){
if(left[left_index] < right[right_index]){
ret.push_back(left[left_index]);
left_index++;
}
else{
ret.push_back(right[right_index]);
right_index++;
}
}
while(left_index < left.size()) ret.push_back(left[left_index++]);
while(right_index < right.size()) ret.push_back(right[right_index++]);
return ret;
}
```
:::
## 0831
* [上課影片](https://youtu.be/dtdCKpnABgo)
* [競賽技巧](https://hackmd.io/@jakao/cp_trick)
## 0901
* [上課影片](https://youtu.be/sAGm-ToOknk)
* [graph](https://hackmd.io/@giver/Sy4HuHENB#/)
:::spoiler 題單
[Zerojudge b108](https://zerojudge.tw/ShowProblem?problemid=b108)
[Zerojudge a584](https://zerojudge.tw/ShowProblem?problemid=a584)
[Zerojudge a586](https://zerojudge.tw/ShowProblem?problemid=a586)
[Zerojudge a290](https://zerojudge.tw/ShowProblem?problemid=a290)
[Zerojudge d768](https://zerojudge.tw/ShowProblem?problemid=d768)
[Zerojudge e584](https://zerojudge.tw/ShowProblem?problemid=e584)
[Zerojudge c124](https://zerojudge.tw/ShowProblem?problemid=c124)
[Zerojudge e699](https://zerojudge.tw/ShowProblem?problemid=e699)
:::
## 0908
* [上課影片](https://youtu.be/NSw039-4Iic)
* [tree](https://hackmd.io/@giver/BySfEFtVH#/)
* [union-find](https://hackmd.io/@jakao/disjoint_set)
:::spoiler 題單
[Zerojudge c463](https://zerojudge.tw/ShowProblem?problemid=c463)
[Zerojudge b517](https://zerojudge.tw/ShowProblem?problemid=b517)
[Zerojudge b518](https://zerojudge.tw/ShowProblem?problemid=b518)
[Dandanjudge a144](http://203.64.191.163/ShowProblem?problemid=a144)
[Dandanjudge a445](https://zerojudge.tw/ShowProblem?problemid=a445)
[Uva 11987](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3138)
:::
Sign in with Wallet
Connect another wallet