# TOI 2023 一階
## 03/13
### 戳了
- [x] TIOJ 1035

### 過了
#### TIOJ 1035
怪題，看到題目沒想法可以先試試暴力
好像有 fft 作法？

---
## 03/14
### 上課
* cycle
* degeneracy
* C3, C4, K4, Diamond
* 隨機塗色
* connectivity
* spanning forest

### 戳了
- [x] TIOJ 2038
- [x] TIOJ 1169
- [x] TIOJ 1171
- [ ] CF 1515G

### 過了
#### TIOJ 1169
動態開點，答案節點不要用指標

#### TIOJ 2038
從 degree 最小的開始拔，拔掉前整張圖的 degree 都大於等於當前拔的點

#### TIOJ 1171
複習，重心剖分

---

## 03/15
### 戳了
- [ ] CF 1515G

### vir
#### [JOISC 2022 D4](https://hackmd.io/HU-OY4AIR_WGiqtKM8GXdg#20230315-%E2%80%94-JOISC-2022-D4)

## 03/16
### 上課
* minimum path cover on DAG
* 每個點拆成入點跟出點，變成 bipartite
* 左邊那團在最大匹配外的點，會是每條 path 的終點，也就是 path 的數量
* 保證有解
* 維護題目的性質，變成小題目
* Dilworth's Theorom
* 在 DAG 上，最大的 antichain 等於 minimum path cover
* antichain 中的點無法互相比較（沒有人能走到其他人）
### 戳了
- [x] sprout OJ 795 (最近點對)
- [x] ABC 237 Ex
- [ ] CSA Sugarel in Love
- [ ] CF 1525F

### 過了
#### SproutOJ 795 (最近點對)
距離平方的時候要小心

#### ABC 237 Ex
Dilworth's Theorom
最大流記得當前弧優化

## 03/17
### 戳了
- [x] CSES Convex Hull

### 過了
#### CSES Convex Hull
先把點 sort，分成上下兩個凸包來蓋
由小到大 sort 是蓋下凸包，反過來是上凸包
維護一個 stack 如果今天新加入的點可以把之前的點幹掉，就 pop 掉之前的點
幹掉的條件是 cross ((新加的點 - top 的前一個), (top - top 的前一個)) <(=) 0
也就是往順時針方向轉，要不要等於是取決於凸包上可不可以有三點共線

## 03/18
### 耍廢一整天~

## 03/19
### [一模](https://hackmd.io/@Paul-Liao/Hkxta9Gxn)

## 03/20
### 戳了
- [x] CSES Grid Paths
- [x] IOI 2018 Combo
- [x] CF 1114F

### 過了
#### CSES Grid Paths
終於過了，但還是去看了解哈哈哈

主要的觀察是，如果一個方向走到不能走了，但左右都可以走，那整個 Grid 會被切成不連通的兩塊，所以就要 return

#### IOI 2018 Combo
有想到，但沒發現（？
我也不知道是怎樣，感覺遇到分 Case 的題目，要寫下來比較不容易耍笨。

#### CF 1114F
歐拉函數：
1. 跟 x 互質的數字個數
2. 積性函數 phi[a * b] = phi[a] * phi[b] 如果 gcd(a, b) = 1
3. 質因數分解，每個質因數會乘一次 (p - 1) 其他都是乘 p

## 03/21

### 戳了
- [x] 一堆 UVA
- [x] CSES Counting Bishops
- [x] 一模 B D

### 過了
#### 一模 D
用兩個根號大小的陣列，來 $O(1)$ 算 $a ^ b$

int a;
int pow1[500], pow2[500];
pow1[0] = pow2[0] = 1;
for (int i = 1; i <= 500; i++) pow1[i] = pow1[i -1] * a;
for (int i = 1; i <= 500; i++) pow2[i] = pow2[i - 1] * pow1[500];
int fpow(int b) {
    return pow2[b / 500] * pow1[b % 500];
}

## 03/22
### 戳了
- [x] CSES Counting Bishops
- [x] CSES Polygon Lattice Points

### 過了

#### CSES Counting Bishops
轉 45 度，DP

#### CSES Polygon Lattice Points
Pick's Theorem :
簡單多邊形的格子點定理
A = I + B / 2 - 1
A : 多邊形面積
I : 多邊形內格子點數量
B : 多邊形的邊上格子點數量

## 03/23
### 戳了
- [x] IOIC 幾何複製文

### 過了
#### IOIC 幾何複製文
旋轉掃描線，用 cross 來判
特判 有向角是 0 的、不同象限的

#### ABC 294G
輕重鏈剖分
https://atcoder.jp/contests/abc294/submissions/39964915

## 03/24
耍廢~