---
tags: 2021WinterTraining
---
# 2021寒訓

[TOC]

## Computational Geometry (1/20)
[投影片](/@jakao/2021winterTraining1)
[上課影片](https://youtu.be/z1S_iDiebVE)
>投影片2.9頁 code內容修改 29行 top>=2改成top>=t

:::spoiler 題單
#### 凸包
[ZJ b596: Less is better](https://zerojudge.tw/ShowProblem?problemid=b596)
[ACLOJ: Fish nets](http://140.121.197.14:100/problem/fnet)
#### 旋轉卡尺
[ZJ b288: 夏季大三角](https://zerojudge.tw/ShowProblem?problemid=b288)
[ZJ e747: Largest Quadrilateral](https://zerojudge.tw/ShowProblem?problemid=e747)
#### 掃描線
[TIOJ 1224: 矩形覆蓋面積計算](https://tioj.ck.tp.edu.tw/problems/1224)
[CF gym101982F: Rectangles](https://codeforces.com/gym/101982/problem/F)
:::

## Graph Theory(Tree)(1/27)

[投影片](/@jakao/2021winterTraining2)
[上課影片](https://youtu.be/PHjpBvsUjuY)
:::spoiler 題單
#### 最近共同祖先(Lowest Common Ancestor)
[ZJ d767: 血緣關係](https://zerojudge.tw/ShowProblem?problemid=d767)
[CF 519E: A and B and Lecture Rooms](https://codeforces.com/problemset/problem/519/E)
[CF gym102021A: Attack on Alpha-Zet](https://codeforces.com/gym/102021/problem/A)
[ZJ c495: 次小生成樹](https://zerojudge.tw/ShowProblem?problemid=c495)
[CF gym101810: M. Greedy Pirate ](https://codeforces.com/gym/101810/problem/M)
#### 樹壓平
[CF 877E: Danil and a Part-time Job](https://codeforces.com/problemset/problem/877/E)
[CF 620E: New Year Tree](https://codeforces.com/contest/620/problem/E)
#### 樹鏈剖分(Heavy Light Decomposition)
[ZJ b327: 學姊日談](https://zerojudge.tw/ShowProblem?problemid=b327)
[ZJ b322: 樹形鎖頭](https://zerojudge.tw/ShowProblem?problemid=b322)
[CF 1254D: Tree Queries](https://codeforces.com/contest/1254/problem/D)
:::

## Graph Theory(MST, shortest path)(2/4)
[投影片](https://hackmd.io/@jakao/2021winterTraining3)
[上課影片](https://youtu.be/TAoZ9qQFdRY)
:::spoiler 題單
#### minimum spanning tree
[ZJ a129: 最小生成樹](https://zerojudge.tw/ShowProblem?problemid=a129)
[CF 1468J: Road Reform](https://codeforces.com/contest/1468/problem/J)
[CF 1095F: Make It Connected](https://codeforces.com/contest/1095/problem/F)
[CF gym100803F: There is No Alternative
](https://codeforces.com/gym/100803/problem/F)
#### dijkstra
[DDJ a308: Plan A Temporary Habitat](http://203.64.191.163/ShowProblem?problemid=a308)
[ZJ e297: PD. Demand(居民的請求)](https://zerojudge.tw/ShowProblem?problemid=e297)
[CF 938D: Buy a Ticket](https://codeforces.com/contest/938/problem/D)
#### floyd warshall
[CF 1202B: You Are Given a Decimal String...](https://codeforces.com/contest/1202/problem/B)
[CF 25C: Roads in Berland](https://codeforces.com/contest/25/problem/C)
#### SPFA
[UVa 558: Wormholes](https://vjudge.net/problem/UVA-558)
:::

## Advanced Data Structures(2/20)
[投影片](https://hackmd.io/@jakao/2021winterTraining4)
[上課影片](https://youtu.be/b3DbWXFKw5o)
>上課影片前十分鐘忘記錄影，請見諒><
:::spoiler 題單
#### Treap
[ZJ d788: 排名順序](https://zerojudge.tw/ShowProblem?problemid=d788)
[ZJ b491: 史蒂芙的政務工作](https://zerojudge.tw/ShowProblem?problemid=b491)
[ZJ b771: 46. Play with Words](https://zerojudge.tw/ShowProblem?problemid=b771)
[ZJ b770: 47. Play with Words, Too.](https://zerojudge.tw/ShowProblem?problemid=b770)
[CF 899F: Letters Removing](https://codeforces.com/contest/899/problem/F)
[CF 1181D: Irrigation](https://codeforces.com/contest/1181/problem/D)
#### 分塊
[ZJ d539: 區間 MAX](https://zerojudge.tw/ShowProblem?problemid=d539)
#### 莫隊
[SPOJ DQUERY: D-query](https://www.spoj.com/problems/DQUERY/)
[ZJ b417: 區間眾數](https://zerojudge.tw/ShowProblem?problemid=b417)
[ZJ e732: A Simple RMQ Problem](https://zerojudge.tw/ShowProblem?problemid=e732)
[CF 86D: Powerful array](https://codeforces.com/contest/86/problem/D)
#### 可持久化
[ZJ a331: K-th Number](https://zerojudge.tw/ShowProblem?problemid=a331)(可持久化線段樹，也可用分塊，treap做做看)
[ZJ b412: 【記憶中】之記憶中的并查集](https://zerojudge.tw/ShowProblem?problemid=b412)(可持久化並查集)
[ZJ b405: 【記憶中】之記憶中的序列](https://zerojudge.tw/ShowProblem?problemid=b405)(可持久化treap)
[可持久化線段樹題單](https://codeforces.com/blog/entry/56880)(有興趣的可以自己去戳戳看)
:::