---
# System prepended metadata

title: 上課筆記哈

---

上課筆記哈
===
* 重要！
[實作備戰手冊](https://hackmd.io/XVrXL2UUSo2DG5_nXHm0yA?view)
[觀念題大綱](https://hackmd.io/@algoseacow/apps-written)
[觀念題考古題](https://hackmd.io/@apcser/B1N5GYEto) 
[Python to C++](https://hackmd.io/@APCS-is-hard/SJbA0hX5A)
[TOC]

2024/6/1
---

1. `in` 在 `list` 是 $O(n)$, `set, dict` 是 $O(1)$
2. list.append() 不算改值 (assignment =), 不用global
3. 大寫 `List` 在 python 3.7 後有額外的意義 (typing)，不要用這個名字。
4. `None` 的用法 (初始值建議為 `None`)
5. Counting Table 的用法 (用在 visit / mark)
6. 交錯字串 用 stack 的作法
7. list comprehension: `l = [i for i in total if s % i == 0]`
8. `twoA, twoB, twoC = list(map(int,input().split(" ")))`
9. 估算你code的時間複雜度，帶最大的數字進去，超過 10^8 表示 TLE。
    * $O(n^2)$, $n \le 10^4 \rightarrow (10^4)^2 = 10^8$ 非常勉強可以過
    * $O(n \log n)$ $n \le 2 \times 10^6$ 可以過



```python
s = "aaaAAbbCCCC"

# L[[str, counting]]
def f(s):
    L = []
    for c in s:
        if not L or L[-1][0] != c:
            L.append([c, 1])
        else:
            L[-1][1] += 1
    return L

out = f(s)
out2 = [c for i, c in out]
print(f(out2))

for i in range(len(out2)):

    cur_len = out2[i][0] * out2[i][1]
    # TODO
    if out2[i-1][0] > out2[i][0]:
        cur_len += out2[i][0]
```

### Counting Sort

```python
table = [0] * 10
for num in nums:
    table[num] += 1

# 0, 0, 2, 3, 5, 5
# [2, 0, 1, 1, 0, 2, 0, ...]
nums2 = []
for i in range(10):
    for j in range(i):
        nums2.append(i)
```

### [贏家預測](https://zerojudge.tw/ShowProblem?problemid=h082)
```python
n, m = map(int, input().split())
S, T, I = [list(map(int, input().split())) for _ in range(3)]
I = [[i-1, 0] for i in I]
# print(n, m)
# print(S, T, I)

C = [0] * n
round_idx = 0
while len(I) != 1:
    round_idx += 1
    I2_win, I2_lose = [], []
    for i in range(0, len(I), 2):
        if i+1 == len(I):
            break
        win = i if S[I[i][0]] * T[I[i][0]] >= S[I[i+1][0]] * T[I[i+1][0]] else i+1
        lose = i if win == i+1 else i+1
        who_win, who_lose = I[win][0], I[lose][0]
        a, b, c, d = S[who_win], T[who_win], S[who_lose], T[who_lose]
        S[who_win] += c * d // (2 * b)
        T[who_win] += c * d // (2 * a)
        S[who_lose] += S[who_lose] // 2
        T[who_lose] += T[who_lose] // 2
        I[lose][1] += 1
        # print(win, lose, who_win, who_lose)
        I2_win.append(I[win])
        if I[lose][1] < m:
            I2_lose.append(I[lose])
        C[who_lose] += 1
    # print(I2_win, I2_lose)
    I = I2_win + ([I[-1]] if len(I) % 2 == 1 else []) + I2_lose
    # print(round_idx, S, T, I, C)
print(I[0][0]+1)
```

### 回家作業

* [人口遷移](https://zerojudge.tw/ShowProblem?problemid=f313)
* [數字龍捲風](https://zerojudge.tw/ShowProblem?problemid=c292)
* 還有補上次的作業
* [遞迴投影片](https://slides.com/arvinliu/recur2)



2024/6/8
---

### 單調對列

有個裸題在這 https://zerojudge.tw/ShowProblem?problemid=a146

給定一個陣列 `ary` 以及整數 `k`，求出一個這樣子的陣列:
`min(ary[0:k]), min(ary[1:k+1]), min(ary[2:k+2]) ... min(ary[-k:])`

```python
from collections import deque
ary = [1, 4, 1, 7, 5, 8, 7, 6]
N = len(ary)
k = 5

# 滑動視窗 Sliding Window
# 單調隊列 
Q = deque([(ary[i], i) for i in range(k)])
print(Q)

output = [min(Q)]
for i in range(k, len(ary)):
    if Q and Q[0][1] == i-k:
        print("Pop Left:", Q[0])
        Q.popleft()
    while Q and Q[-1][0] >= ary[i]:
        print("Pop Right", Q[-1])
        Q.pop()
    Q.append((ary[i], i))
    print("Add", Q[-1])
    print(Q)
    output.append(Q[0])
print(output)
```

### defaultdict
* defaultdict: 在你\[不存在的值\] 的時候，他會幫你設定預設值。
```python
# Sliding Window 滑動視窗 找區間內數字種數 + defaultdict
from collections import defaultdict
typecnt = 0
D = defaultdict(lambda: 0)
while True:
    inp, oup = None, None

    D[inp] += 1

    if D[inp] == 1:
        typecnt += 1

    D[oup] -= 1
    if D[oup] == 0:
        typecnt -= 1
```

### dict.get()
* `get()`: 在索引不存在的值的時候，會有預設回傳值 (不改動原本的dict)
```python
D = {1:7}
print(D.get(1, 5))
print(D)
```

### lambda function

* lambda: 匿名函數，一種不用寫名字的函數。
```python
def f(x): y=x**2; return y
f = lambda x:x+1
print(f(1))
print(f(2))
print(f(3))
print(f(4))
# def initial():
#     return 0
```

### 猜拳
* 猜拳的另一種解法
```python
D = {
    "02": 1,
    "25": 1,
    "50": 1,
    "05": 0,
    "52": 0,
    "20": 0
}

def result(r, p):
    return D[r+p]

for p in ["02", "25", "50", "05", "20", "52"]:
    print(p, result(p[0], p[1]))
```


### 回家作業

~~Q2-6 連續線段長度 過了~~
~~Q2-8 洗牌 過了~~
~~Q2-9 人口遷移 (上次的作業) 過了~~

雷射測試 TLE了

[誰先晚餐] (https://hackmd.io/HzeNd62dQEaNCsBvXEge2w)
[pq邂逅] (https://zerojudge.tw/ShowProblem?problemid=a565)

---
Q2-10 機器人走棋盤
Q2-12 最小矩陣距離
~~Q2-11 矩陣轉換 過了~~
Q3-9 DF-Expression


2024/6/15
---

### m934 合併成本 (ad-hoc)
```python=
def rec(l):
    # return minumal answer
    n = len(l)
    if n == 1:
        return 0
    ans = float('inf')
    for i in range(n-1):
        # [i, i+1]
        new_l = l[:i] + [l[i] + l[i+1]] +l[i+2:]
        new_cost = abs(l[i] - l[i+1])
        ans = min(ans, new_cost + rec(new_l))
    return ans
print(rec([3,-1,2,5]))
print(rec([-5, 3, 0, -4, 3, -2]))
print(rec([-1,-6,6,-8,7,0,-9]))
```



### m373 投資遊戲 (20%)

```python
# 枚舉 (enumerate)

# input()
# l = list(map(int, input().split()))
# n = len(l)
l = [3, 1, -7, 3, -2, 10, -5, 2, 2]
n = len(l)

# O(n^2)
ans = 0
for L in range(n):
    cur = []
    S = 0
    for R in range(L, n):
        cur.append(l[R])
        S += l[R]
        ans = max(ans, S)
        # print(cur, S)
print(ans)

# O(n log n) O(n)

# prefix sum / 前綴和
l2 = [0]
cur_min = 0
ans = 0
for i in l:
    l2.append(l2[-1] + i)
    ans = max(ans, l2[-1] - cur_min)
    print(f"For {l2[-1]}, min = {cur_min}")
    cur_min = min(cur_min, l2[-1])
print(l2)
print(ans)
```


### m932 蜜蜂觀察 

```python=
n, m, k = map(int, input().split())
hexhouse = [input() for i in range(n)]

x, y = n-1, 0
d = [[-1, 0], [0, 1], [1, 1], [1, 0], [0, -1], [-1, -1]]
out = []
for ki in map(int, input().split()):
    nx, ny = x+d[ki][0], y+d[ki][1]
    if 0 <= nx < n and 0 <= ny < m:
        x, y = nx, ny
    out.append(hexhouse[x][y])

print(''.join(out))
print(len(set(out)))
```


### m372 搬家
* DFS = Depth First Search 深度優先搜尋法
> BFS = Breadth First Search 廣度優先搜尋法
```python=
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
mat = [ list(input().strip()) for _ in range(n)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
D = {
    'F':[dirs[3], dirs[1]],
    'H':[dirs[3], dirs[2]],
    '7':[dirs[2], dirs[1]],
    'I':[dirs[1], dirs[0]],
    'X':[dirs[3], dirs[1], dirs[2], dirs[0]],
    'L':[dirs[3], dirs[0]],
    'J':[dirs[2], dirs[0]],
    '0':[],
}

def dfs(x, y):
    if mat[x][y] == '0':
        return 0
    # print(x, y)
    tmp = mat[x][y]
    mat[x][y] = '0'
    ans = 1
    for dx, dy in D[tmp]:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        # print("N", nx, ny, mat[nx][ny], D[mat[nx][ny]])
        if (-dx, -dy) in D[mat[nx][ny]]:
            ans += dfs(nx, ny)
    return ans

print(max(dfs(i,j) for i in range(n) for j in range(m)))
```

```python=
n, m = map(int, input().split())
mat = [ list(input().strip()) for _ in range(n)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
D = {
    'F':[dirs[3], dirs[1]],
    'H':[dirs[3], dirs[2]],
    '7':[dirs[2], dirs[1]],
    'I':[dirs[1], dirs[0]],
    'X':[dirs[3], dirs[1], dirs[2], dirs[0]],
    'L':[dirs[3], dirs[0]],
    'J':[dirs[2], dirs[0]],
    '0':[],
}

ans = 0
for sx in range(n):
    for sy in range(m):
        cnt = 0
        Q = [(sx, sy)]
        while Q:
            x, y = Q.pop()
            if mat[x][y] == '0':
                continue
            cnt += 1
            for dx, dy in D[mat[x][y]]:
                nx, ny = x + dx, y + dy
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue
                # print("N", nx, ny, mat[nx][ny], D[mat[nx][ny]])
                if (-dx, -dy) in D[mat[nx][ny]]:
                    Q.append((nx, ny))
            mat[x][y] = '0'
        ans = max(ans, cnt)
print(ans)

```

### 幸運數字 g277
$B$ 是 $A$ 的前綴和 / prefix sum
$B[0] = A[0]$
$B[1] = A[0] + A[1]$
$B[2] = A[0] + A[1] + A[2]$
$B[r] = A[0] + A[1] + A[2] ... + A[r]$

Find a function $f$ s.t. $f(l, r) = A[l] + A[l+1] ... A[r]$ 
```python
if l > 0: B[r] - B[l-1]
if l == 0: B[r]
```

```python
import sys
sys.setrecursionlimit(int(4e5))
input()
l = list(map(int, input().split()))
l2 = [(x, i) for i, x in enumerate(l)]
l2.sort(reverse=True)
prefix_sum = [0]
for x in l:
    prefix_sum.append(prefix_sum[-1] + x)

def interval_sum(L, R):
    return prefix_sum[R+1] - prefix_sum[L]

def rec(L, R):
    if L == R:
        return l[L]
    while l2[-1][1] < L or l2[-1][1] > R:
        l2.pop()
    m = l2[-1][1]
    if interval_sum(L,m-1) > interval_sum(m+1, R):
        return rec(L, m-1)
    else:
        return rec(m+1, R)
print(rec(0, len(l)-1))
```


2024/6/22
---

#### Generator
```python=
def G(nums):
    for i in range(len(nums)):
        print("YEILD")
        yield (i, nums[i])

for (k, v) in list(G(nums)):
    print(f"GET {k, v}")
```


### 雙指針 - twosum
```python=
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        L = sorted((v, k) for k, v in enumerate(nums))
        right = len(L)-1
        for left in range(len(L)):
            while left != right and L[left][0] + L[right][0] > target:
                right -= 1
            if left != right and L[left][0] + L[right][0] == target:
                return [L[left][1], L[right][1]]
```

```python=
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for k, v in enumerate(nums):
            if target-v in d:
                return [d[target-v], k]
            d[v] = k
```


### o079 最佳選擇
```python=

l = [1, 5, 2, 2, 9, 3, 5, 8]
k = 22


S = sum(l)

L = []
# R = {}
Lsum = 0
Lpar = 0
for i in l:
    Lsum += i
    Lpar += 1 if (i % 2) else -1
    L.append((Lsum, Lpar))


R = []
# R = {}
Rsum = 0
Rpar = 0
for i in l[::-1]:
    Rsum += i
    Rpar += 1 if (i % 2) else -1
    R.append((Rsum, Rpar))
R = R[::-1]
print(L)
print(R)
# [(1, 1), (6, 2), (8, 1), (10, 0), (19, 1), (22, 2), (27, 3), (35, 2)]
# [(35, 2), (34, 1), (29, 0), (27, 1), (25, 2), (16, 1), (13, 0), (8, -1)]
```



2024/7/13
---

### 動態規劃 I
[DP 投影片](https://slides.com/arvinliu/dp)

* **Fibonacci Sequence
[d212. 東東爬階梯](https://zerojudge.tw/ShowProblem?problemid=d212)**
完成
第一次看到的輸入格式
* **[d134. 00369 - Combinations](https://zerojudge.tw/ShowProblem?problemid=d134)**
完成
* 經典 0/1 背包問題 [a587. 祖靈好孝順 ˋˇˊ](https://zerojudge.tw/ShowProblem?problemid=a587)
用python TLE了
```python=
from functools import  lru_cache
@lru_cache(300000)
def f(n, w):
    if n == 0:
        return 0
    
    if w >= W[n]:
        return max(f(n-1, w-W[n])+V[n] ,f(n-1, w))
    return f(n-1, w)

N = int(input())
W = [0]
V = [0]
for i in range(N):
    w, v = list(map(int, input().split()))
    W.append(w)
    V.append(v)
limit = int(input())

print(f(N, limit))
```
* Coding Bar
    * 第三週 動態規劃 I
    * **Q2 - 費氏數列_memo** 完成
    * ~~Q7 - 找零錢_memo~~

2024/7/20
---

### DP 的複雜度

```
# 1. 狀態數量 -> O(nW)
# 2. 轉移複雜度 -> O(1)
# -> O(nW) * O(1) = O(nW)
```
幾乎所有DP的複雜度都是 O(狀態數) * O(轉移複雜度)。
* 考慮轉移的時候，把所有遞迴全都當成 $O(1)$ 看就好了。
### 作業
* codingbar
    * 動態規劃 I
        * Q5 費氏數列 迭代 完成
        * Q7 找零錢_memo 完成
            * 狀態1D/轉移1D -> O(N^2) problem
        * Q8 找零錢_dp-迭代 完成
        * Q10 - Q14 觀念題 完成
    * 動態規劃 II
        * Q6 吃到飽 (無限背包問題) 完成
        * Q9 限量搶購 (有限背包問題) 完成
            * 2D/0D DP 
        * Q19 卡牌遊戲 (先寫完前面再寫，用遞迴暴力搜尋就可以了) 完成



2024/7/27
---

### 動態規劃 II
[DP 投影片](https://slides.com/arvinliu/dp)

### lru_cache
Top-down 記憶化的另一個寫法 (你很熟再用)

```python=
from functools import lru_cache

# Wrapper 

# MAX_SIZE = 最大的空間
@lru_cache(MAX_SIZE)
def f()...
```


### deque = stack + queue
Stack/Queue

|Stack|List|
|-|-|
|pop()| `List.pop() / del List[-1]`|
|push()| `List.append()`|

* Queue 其實官方有資料結構，但他比一般的queue複雜很多。 (具體來說就是多了 multi-thread 處理的一些東西)
    * [Queue](https://docs.python.org/zh-tw/3/library/queue.html#queue.Queue.get) -> `from queue import Queue`

* deque的念法念作 "deck"，不念 "de-queue":
    * `dequeue` (從queue/stack裡面拿出來，約等於 get()) != `deque` 

* deque 用法
    * 從後面 pop: `deque.pop()` ，也就是 Stack pop 
    * 從後面 push: `deque.append(x)`，也就是 Stack / Queue push
    * 從前面 pop: `deque.popleft()`，也就是 Queue pop
    * 從前面 push: `deque.appendleft(x)`，也就是...沒有就是

```python=
>>> from collections import deque
>>> Q = deque()
>>> Q.append(5)
>>> Q
deque([5])
>>> Q.appendleft(7)
>>> Q
deque([7, 5])
>>> Q.popleft()
7
>>> Q.pop()
5
>>>
```

### 合併排序 merge sort
> merge sort 有最佳子結構 (可以從小排序陣列變成大排序陣列)，但沒有重複子問題。

![image](https://hackmd.io/_uploads/HJr6qxzFC.png)

* 如何實作？先考慮一個小問題：
如何把兩個排序好的序列，變成一個排序好的序列？

考慮完後用遞迴寫出來就可以了。

```python=
A = deque([1,3,4,7])
B = deque([2,5,6,8])
C = []

while A and B:
    if not B or (A and A[0] < B[0]):
        C.append(A.popleft())
    else:
        C.append(B.popleft())

##############################################
# 寫成一個函數，變成完整的merge_sort 就會變這樣 #
##############################################

from collections import deque
def merge_sort(ary, L, R):
    # 包含 L 不包含 R
    if L + 1 >= R:
        # 空的，或者只有一個數字，不做事
        return 
        
    M = (L + R) // 2
    # 拆一半sort
    merge_sort(ary, L, M)
    merge_sort(ary, M, R)
    # 合起來
    A = deque(ary[L:M])
    B = deque(ary[M:R])
    for c_idx in range(L, R):
        if not B or (A and A[0] < B[0]):
            ary[c_idx] = A.popleft()
        else:
            ary[c_idx] = B.popleft()

```

#### 時間複雜度
每一次都會把陣列拆成兩半，總共會拆成 O(\log N)層
每一層的每個數字都會排序，所以每層加總複雜度 O(N)
O(log N) 層 * 每層複雜度 O(N) = O(N \log N)

### 作業
* codingbar
    * 動態規劃 I:
        * ~~(優先5) (找零錢變種) 作業1: 福袋小工 卡住了 (TLE) -> 記憶化過了~~
        * ~~(優先6) (找零錢變種) 作業2: 籃球得分 完成~~
    * 動態規劃 II:
        * ~~(優先1) **吃到飽 / 背包問題  -> bottom-up -> 轉成一維陣列的形式。** 成功~~
        * ~~(優先2) 經典LCS Q17 - 最長共同子序列(Longest Common Subsequence) 成功~~
        * ~~(優先7) Q20 - 採買零食 卡住了~~
* zerojudge
    * (優先8) 還原LCS (文章版本) [00531 - Compromise](https://zerojudge.tw/ShowProblem?problemid=e682) 為什麼WA，明明範例過了啊｡ﾟ(ﾟ´ω`ﾟ)ﾟ｡
        * 循環測資 -> 如果TLE就假裝它是好的
    * (優先4) 三個字串的LCS [a252. Another LCS](https://zerojudge.tw/ShowProblem?problemid=a252) TLE ->改成Bottom up就過了
        * Bottom-up -> 滾動法
    * (優先3) 經典LCS [c001. 10405 - Longest Common Subsequence](https://zerojudge.tw/ShowProblem?problemid=c001)
* 八選五個作業



2024/8/3
---

### List Comprehension

* 開一個二維陣列 (N\*M)
    * `[[None] * M for _ in range(N)]`
* 為什麼 `[[None]*M]*N` 不能這樣寫?
    * 因為 `list` 只會複製地址。改了其中一排，其他牌也會跟著改動。

```python=
>>> L = [3, 1, 4, 7]
>>> A = L
>>> A[0] = 7
>>> L
[7, 1, 4, 7]
>>> L = x
>>> # ===========================
>>> L = 7
>>> A = L
>>> A = 5
>>> L
7
>>> L = "ABC"
>>> L[0] = "x"
<Type Error>
>>> # ===========================
>>> L = "ABBCC"
>>> M = 3
>>> N = 2
>>> mat = [[0] * M] * N
>>> mat[0][0] = 1
>>> mat
[[1, 0, 0], [1, 0, 0]]
```

### args, kwargs


#### 正常使用時

```python=
>>> L1 = [1, 3, 5]
>>> L2 = [2, 4, 6]
>>> (a, b, c), (d, e, f) = L1, L2
>>> a, b, c, d, e, f = *L1, *L2
>>>
>>> list(zip(L1, L2))
[(1, 2), (3, 4), (5, 6)]
>>> L = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
>>> list(zip(*L))
[(0, 3, 6), (1, 4, 7), (2, 5, 8)]
```

```
W = [...]
V = [...]

for i in range(len(W)):
  w, v = W[i], V[i]
  
for i, (w, v) in enumerate(zip(W, V)):
```
* zip, enumerate

#### 函數呼叫時
* `*`(List) 可以展開，例如在 Function 內。
* `**`(Dict) 在Function內可以根據函數的參數展開。
```python=
>>> def f(a, b, c):
...   print(f"a={a} b={b} c={c}")
...
>>> f(1, 0, 3)
a=1 b=0 c=3
>>> L = [2, 3, 7]
>>> f(L[0], L[1], L[2])
a=2 b=3 c=7
>>> f(*L)
a=2 b=3 c=7
>>> D = {'a': "Im a", 'c': None, 'b': 'BBB'}
>>> f(**D)
a=Im a b=BBB c=None
>>>
>>> L = [7, 9]
>>> f(5, L[0], L[1])
a=5 b=7 c=9
>>> f(5, *L)
a=5 b=7 c=9
```

#### 函數生成時

```python=
>>> def f(*L): return [i*2 for i in L]
>>> f(3, 7, 2)
[6, 14, 4]
>>> # =====================================
>>> def f(x=2, *L): return [i*x for i in L]
>>> f(3, 7, 2)
[21, 6]
```



### 作業

#### Leetcode
1. ~~[LIS](https://leetcode.com/problems/longest-increasing-subsequence/)~~
2. ~~[LIS 的數量](https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/)~~
3. ~~[股票買賣I](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/) - 可以不用 DP~~
4. ~~[Max Subarray](https://leetcode.com/problems/maximum-subarray/description/) - 可以不用 DP~~
5. ~~[String Balancing](https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/description/) - 可以不用 DP~~
6. ~~[股票買賣II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)~~
7. https://leetcode.com/problems/longest-ideal-subsequence/description/

#### Sudoku
>  hint: https://slides.com/arvinliu/recur2#/23
1. ~~[判斷數獨是否合法](https://leetcode.com/problems/valid-sudoku/description/)~~
2. [解數獨](https://leetcode.com/problems/sudoku-solver/description/)

* 想想看 最多閃耀星星路 (營隊後再講)


2024/8/11
---
https://hackmd.io/vYSWLE3WTEiLeqgJwlTSAg

2024/9/14
---

動態規劃 III: https://slides.com/arvinliu/dp

### 作業

上課的四題用 python 寫

* Critical Mass (zj a388)
* 4. 合併成本 (zj m394)
* 4. 美食博覽會 (zj g278)
* [Minimum Substring Partition](https://leetcode.com/problems/minimum-substring-partition-of-equal-character-frequency/description/) (Leetcode 3144)


* 4 (扣掉病毒優化) 選2

推薦你寫 刪除邊界 / 投資遊戲
* 刪除邊界的zj消失了QQ 所以你選個做吧，可以寫寫看勇者修練
<div id="write">
<table>
	<thead>
		<tr>
			<th><span>題目名稱</span></th>
			<th><span>來源</span></th>
			<th><span>備註</span></th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=e465" target="_blank">置物櫃分配</a></td>
			<td>APCS 2018 / 10 - 4</td>
			<td>類背包問題</td>
		</tr>
		<tr>
			<td><a href="https://jmj.cmgsh.tp.edu.tw/ShowProblem?problemid=d090" target="_blank">刪除邊界</a></td>
			<td>APCS 2019 / 10 - 4</td>
			<td>zj 連結消失了</td>
		</tr>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=m373" target="_blank">投資遊戲</a></td>
			<td>APCS 2023 / 10 - 4</td>
			<td>&nbsp;</td>
		</tr>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=i402" target="_blank">內積</a></td>
			<td>APCS 2022 / 06 - 4</td>
			<td>&nbsp;</td>
		</tr>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=f608" target="_blank">飛黃騰達</a></td>
			<td>APCS 2021 / 01 - 4</td>
			<td>LIS 二分搜版本</td>
		</tr>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=f314" target="_blank">勇者修練</a></td>
			<td>APCS 2020 / 10 - 3</td>
			<td>&nbsp;</td>
		</tr>
		<tr>
			<td><a href="https://zerojudge.tw/ShowProblem?problemid=f582" target="_blank">病毒演化</a></td>
			<td>APCS 2020 / 07 - 4</td>
			<td>樹DP</td>
		</tr>
		<tr>
			<td><a href="https://leetcode.com/problems/burst-balloons/description/" target="_blank">burst-balloons</a></td>
			<td>Leetcode 312</td>
			<td>合併成本類似題</td>
		</tr>
	</tbody>
</table>
</div>


2024/9/21
---

* [圖論投影片](https://slides.com/arvinliu/graph#/3)

* 繼續複習 DP。
    * 推薦你寫置物櫃分配。

* 把我們上課的題目也寫一下

* ~~DSU:~~
    * https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/
    * Hint 1: N個電腦，最少需要幾條線，才可以連起所有電腦
        * N - 1
    * Hint 2: DSU，應該可以知道哪些**線是冗的**。
    * Hint 3: 如果你有 K 個 disjoint set (這 K 個群彼此不互通)，你需要多少線讓這K個群全都互通？
        * K - 1
* ~~BFS:~~
    * https://zerojudge.tw/ShowProblem?problemid=b059
    * Hint: 八方位擴散，但是擴散有條件限制，還有需要判斷有沒出界
    * 除此之外，就是很單純的 BFS


2024/9/28
---


```python=
# x = [0] * 100
# y = [0] * 100
# 這種寫法，x, y 是分散

# 把分散的變數包在一起：
#    定義一個型態長什麼樣子
class Dot:
    # __ dunder = double under (雙個底線)
    # init : initialization 初始化
    # 初始化該做什麼事情 - 建構子 (Constructor)
    def __init__(self, x=0, y=0, z=0):
        print("HI")
        # 我們希望 Dot 有三個屬性：x, y, z
        # self: 這個物件自己
        self.x = x
        self.y = y
        self.z = z

    # 定義 class 的函數
    def eq_id(self, other):
        return id(self) == id(other) 

    # 運算子多載 (Operator Overloading): 覆寫原本 == 的定義
    # 為什麼是覆寫？因為原本的 == 是比對兩個物件的 id
    # eq = equal
    def __eq__(self, other):
        return (self.x, self.y, self.z) == (other.x, other.y, other.z)
    
# . 表示 "的"
dot1 = Dot(5, 6, 8)
print(dot1.x, dot1.y, dot1.z)
dot2 = Dot(5, 6, 8)
print("__eq__:", dot1 == dot2)
# 函數的使用也是跟一般的變數一樣
print("Eqid 1, 2:", dot1.eq_id(dot2))
print("Eqid 1, 1:", dot1.eq_id(dot1))

print(dot1.x, dot1.y, dot1.z)
print(dot2.x, dot2.y, dot2.z)
```


```python=
class myList:
    def __init__(self, l):
        self.l = l[:]

    # 如果不寫，那麼hash table會比較hash一樣後判斷是不是真的eq
    # 這時就會是比較 id()，這樣就會不一樣。    
    def __eq__(self, other):
        return str(self.l) == str(other.l)

    def __hash__(self):
        return hash(str(self.l))
    
A = myList([1, 2, 3])
B = myList([1, 2])
d = dict()
d[A] = 1
d[B] = 2
B.l.append(3)
print(B in d)
d[B] = 3
print(d)
```

### 作業

#### 複習地方

* **複習 class，可以查其他教學** 非常重要！！！
* 複習 Hash table 可以你想複習再複習。
* **複習 BFS / DFS**，但是 UCS / backtracking 可以你想複習再複習。

#### 程式題目
* 動態規劃：上課題目 (美食博覽會) / 置物櫃分配。
![image](https://hackmd.io/_uploads/ByoKObS0A.png)
* 還有上課的練習題 (~~倒油漆~~，數獨，sliding puzzle)

#### 動動腦想想看
![image](https://hackmd.io/_uploads/rkRw_-rC0.png)
![image](https://hackmd.io/_uploads/SJJYubSAC.png)

#### 順位

1. 複習 -> Number of Islands -> 其他
    * ~~BFS~~
    * ~~DFS~~
    * ~~DSU~~


2024/10/5
---

* [Linux 講義連結](https://drive.google.com/drive/folders/1Mo9S63ohCLF8L1KQAhcYgwsULJcwQ2y2)
* [CTF 網站](https://www.ivan-smd.site/)



2024/10/12
---

### 作業

#### 上課題目
~~Find if Path Exists in Graph (Leetcode 1971)~~
* 可以用 DSU / DFS / BFS 寫
~~Is Graph Bipartite? (Leetcode 785)~~
 * 可以試著用 DSU 寫

#### 作業
* 圖論: [Clone Graph](https://leetcode.com/problems/clone-graph/description/
)
    * 遍歷複製 (使用 BFS / DFS 都可以) 看完別人的DFS解答才知道題目的Node類別要怎麼用

* 動態規劃: 
    1. ~~[Unique Paths](https://leetcode.com/problems/unique-paths/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM)~~
    2. ~~[Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM)~~
    3. ~~[One and Zero](https://leetcode.com/problems/ones-and-zeroes/description/?form=MG0AV3)~~
        * 題目意思: 請選出最多個集合，使得集合的 0 不超過 n 個， 1 不超過 m 個。回傳最多的個數即可，不用構造。
* 第二題練習:
    1. ~~[矩陣總和](https://zerojudge.tw/ShowProblem?problemid=h027)~~
    2. ~~[特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732)~~
    3. ~~[運貨站](https://zerojudge.tw/ShowProblem?problemid=j123)~~
        * 體感很麻煩，需要想怎麼簡化題目

* 寫多少算多少，如果你有時間練習

2024/10/19
===

* 實作備戰手冊: https://hackmd.io/XVrXL2UUSo2DG5_nXHm0yA

* 觀念題的常客：
    * 二分搜: https://slides.com/arvinliu/binary-search#/5
    * 二進制轉換: https://slides.com/arvinliu/apcs-loop#/7/1
        * 可以查一下二進轉十進位
    * GCD: https://slides.com/arvinliu/recur2#/9
    * 位元運算:
    ```python
    >>> bin(17)[2:].rjust(10, '0')
    '0000010001'
    >>> bin(20)[2:].rjust(10, '0')
    '0000010100'
    >>> bin(17 & 20)[2:].rjust(10, '0')
    '0000010000'
    >>> bin(17 | 20)[2:].rjust(10, '0')
    '0000010101'
    #xor
    >>> bin(17 ^ 20)[2:].rjust(10, '0')
    '0000000101'
    >>> 17^20
    5
    ```


* 別人統整的觀念題大綱
  https://hackmd.io/@algoseacow/apps-written
* 考前看一下考古題 
  https://hackmd.io/@apcser/B1N5GYEto
  
  
 2024/10/26
 ===
 
#### 作業：
* ~~[https://zerojudge.tw/ShowProblem?problemid=f608]~~(飛黃騰達, LIS + 二分搜, bisect 優化)參考別人的才寫出來
* [https://zerojudge.tw/ShowProblem?problemid=o713](連鎖反應, BFS + 對答案二分搜) #TLE
* ~~[https://zerojudge.tw/ShowProblem?problemid=o714]~~(搭到終點, DP on DAG + 離散化 + 區間和)最後想不到還是去看了別人的code
* ~~[https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/?envType=problem-list-v2&envId=topological-sort](提示: 拓樸排序/順序) Memory Limit Exceeded~~
* ~~[https://zerojudge.tw/ShowProblem?problemid=m372] (BFS找最大連通塊) #NA 35%~~
* 著重複習拓樸，class
### 數值離散化

```python=
l = [0, 4, 0, 3, 5, 4, 6, 6, 7, 9]
l = sorted(list(set(l)))
d = {x:i for i, x in enumerate(l)}

print(l)
print(d)
```

```python=
n, m, p = map(int,input().split())
s, t = list(map(int,input().split())), list(map(int,input().split()))

#車班根據終點排序，就會出現單調性，即可更新區間和
buses = sorted(list(zip(t, s)))#[(4, 0), (6, 0), (6, 4), (7, 3), (9, 5)]註:(終站, 起站)
l = s+t
l = sorted(list(set(l)))
d = {x:i for i, x in enumerate(l)}
prefix_sum = [1]+[0]*(len(l)-1)

for end, start in buses:
    end = d[end]
    start = d[start]
    #同餘定理
    prefix_sum[end] = (prefix_sum[end]%p + sum(prefix_sum[start:end])%p) % p

print(prefix_sum[d[m]])

```



 2024/11/2
 ===


#### 作業

https://www.csie.ntu.edu.tw/~sprout/algo2023/homework/hand02.pdf

* 上次的作業:
    * 圖論: 自己 debug 想想看 visit 要加在哪以及它的機制
        * 想想看DP的記憶化
    * 搭到終點: prefix_sum

來不及寫了
* ~~動態規劃(區間和) : [內積](https://zerojudge.tw/ShowProblem?problemid=i402)~~
* 動態規劃: [刪除邊界](https://jmj.cmgsh.tp.edu.tw/ShowProblem?problemid=d090)
* https://leetcode.com/problems/count-the-number-of-square-free-subsets/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM



 2024/11/9
 ===
 
 ```python
 #TLE
from collections import deque
import sys
#輸入
m, n, q = map(int,sys.stdin.readline().split())
graph = []
for i in range(m):
    temp = list(map(int, sys.stdin.readline().split()))
    if -2 in temp:
        start_x = i
        start_y = temp.index(-2)
    graph.append(temp)



def bfs(start_r):
    Q = deque([(start_x, start_y, start_r)])
    visit = [[None]*n for _ in range(m)]
    visit[start_x][start_y] = start_r
    count = 1
    while Q:
        print(Q)
        x, y, r = Q.popleft()
        
        if r > 0:
            for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                nx, ny = x+dx, y+dy
                if not(0<=nx<m and 0<=ny<n):
                    continue
                if graph[nx][ny] == -1:
                    continue

                if visit[nx][ny] != None:
                    if r-1 > visit[nx][ny]: 
                        Q.append((nx, ny, r-1))
                        visit[nx][ny] = r-1
                else:
                    Q.append((nx, ny, max(r-1, graph[nx][ny])))
                    visit[nx][ny] = max(r-1, graph[nx][ny])
                    count += 1
        
    return count < q

'''
print(bfs(500))
'''
#二分搜
left = 0
right = n*m

while left<right:
    mid = (left+right)//2
    if(bfs(mid)):
        left = mid+1
    else:
        right = mid

print(left)
```

#### DFS / BFS on Tree

```python=
    from collections import deque
class Tree:
    def __init__(self, data, l, r):
        self.data = data
        self.l = l
        self.r = r

root = Tree('A', 
            Tree('B',
                 Tree('D',None,None),
                 Tree('F',None,None)),
            Tree('E',
                 Tree('C',None,None),
                 Tree('G',None,None)))
# DFS
def rec(root):
    if root:
        print(root.data)
        rec(root.l)
        rec(root.r)
rec(root)

# BFS
Q = deque([root])
while Q:
    tree = Q.popleft()
    print(tree.data)
    if tree.l:
        Q.append(tree.l)
    if tree.r:
        Q.append(tree.r)

```

#### 上課練習

* [Same Tree](https://leetcode.com/problems/same-tree/description/?envType=problem-list-v2&envId=tree)
* [Depth of a Binary Tree](
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=problem-list-v2&envId=tree)

#### 作業

* ~~上課練習沒做的題目 (BST 兩題 + 樹的直徑)~~
* 上禮拜的DP選一題來寫
    * ~~動態規劃: [刪除邊界](https://jmj.cmgsh.tp.edu.tw/ShowProblem?problemid=d090)~~
    * https://leetcode.com/problems/count-the-number-of-square-free-subsets/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM

* ~~[血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)~~


2024/11/16
===

* 拓樸 - DFS / 環檢測
* 分治

#### 作業

* ~~[All path on DAG](https://leetcode.com/problems/all-paths-from-source-to-target/description/)~~
* ~~上面的兩題 (刪除邊界 血緣關係)~~
* 複習圖論


* 看一下 $f(n) = 2 f(\frac{n}{2}) + c \cdot  n$ [投影片位置](https://slides.com/arvinliu/recur3#/15/9/0)
    * 其他就慢慢來


2024/11/23 - 分治
===

[遞迴投影片，分治在後半段](https://slides.com/arvinliu/recur3/#/18/1)

* ~~[g277. 3. 幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277)~~
* ~~[f314. 3. 勇者修練](https://zerojudge.tw/ShowProblem?problemid=f314)~~
* [f315. 4. 低地距離](https://zerojudge.tw/ShowProblem?problemid=f315)
    * 如果你不會寫，這是我寫的[解析](https://hackmd.io/@APCS-is-hard/HJocdfoNI/%2FMGbEHktbS0e9AYVOSFnWtA)
* ~~https://leetcode.com/problems/minimum-path-sum/~~
* 想想看幼稚園那題
    * 給定一個數列 A，你可以交換A中任兩相鄰數。
    請問最少交換幾次才可使數列滿足「遞增」或「遞減」或「先遞增再遞減」？

2024/11/30 - 分治
===

投影片: https://slides.com/arvinliu/greedy

## 幸運數字: 尋找排序後的index

```python=
import random

A = list(range(8))
random.shuffle(A)
A = [(x, i) for i, x in enumerate(A)]
A.sort(reverse=True)
print(A)

A.pop() # 拿出最小值
```

## 幼稚園 O(n^2)

```python=
n = input()
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)):
    L_inv = sum( (x>A[i]) for x in A[:i])
    R_inv = sum( (x>A[i]) for x in A[i:])
    ans += min(L_inv, R_inv)
```

## 作業

* ~~勇者修練，`DP[n][m][d]`, d = 0 表示往下，1表示往右，2表示往左，這樣子遞迴會怎麼寫呢？~~
* 之前的分治 
    * 幼稚園 + ~~低地距離~~ + ~~幸運數字~~
* 上課寫的題目:
    * ~~最大區間和~~
    * ~~三角形~~
    * ~~誰先晚餐~~
* ~~想想看用誰先晚餐的推法 (甚麼樣的狀況 1234 會比 1324 好?) 推出 物品堆疊 (APCS 4) (用手寫證明或想的就好)~~
* 超級洗衣機的掃描線要怎麼做 (用想的就好) 想不出來啊
* ~~優先做貪心，還有誰先晚餐的證明要好好看~~


勇者修練
記憶體區段錯誤！ Segmentation fault (core dumped)
```python
import sys
sys.setrecursionlimit(int(100000))


n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))
dp = [[[None]*m for _ in range(n)] for _ in range(3)]


def rec(i, j, d):
    if i == n or j<0 or j==m:
        return 0
    if i == -1:
        return max(rec(i, j+1, d), rec(i+1, j, 2))
    if dp[d][i][j] != None:
        return dp[d][i][j]
    
    if d == 0:
        ans =  max(rec(i, j+1, d), rec(i+1, j, 2))
    elif d == 1:
        ans = max(rec(i, j-1, d), rec(i+1, j, 2))
    else:
        ans =  max(rec(i, j+1, 0), rec(i, j-1, 1), rec(i+1, j, 2))

    dp[d][i][j] = ans + grid[i][j]
    return dp[d][i][j]

print(rec(-1, 0, 0))
```

幸運數字 95%，也是記憶體區段錯誤！ Segmentation fault (core dumped)
```python
import sys
sys.setrecursionlimit(10**6)

n = int(input())
nums = list(map(int, sys.stdin.readline().split()))
prefix = [0]
s = 0
for i in nums:
    s += i
    prefix.append(s)

m = [(x, i) for i, x in enumerate(nums)]
m.sort(reverse=True)

def rec(l, r):
    if l+1 == r:
        return nums[l]
    #找最小
    min_num = m.pop()[1] 
    while not(l <= min_num < r):
        min_num = m.pop()[1]

    #區間和
    if prefix[r]-prefix[min_num+1] >= prefix[min_num]-prefix[l]:
        return rec(min_num+1, r)
    else:
        return rec(l, min_num)

print(rec(0, n))
```


* 改成用stack模擬遞迴:
* 幸運數字
```python=
n = int(input())
nums = list(map(int, input().split()))
prefix = [0]
s = 0
for i in nums:
    s += i
    prefix.append(s)

m = [(x, i) for i, x in enumerate(nums)]
m.sort(reverse=True)

L = [(0, n)]
while L:
    l, r = L.pop()
    if l+1 == r:
        print(nums[l])
        break
    #找最小
    min_num = m.pop()[1] 
    while not(l <= min_num < r):
        min_num = m.pop()[1]

    #區間和
    if prefix[r]-prefix[min_num+1] >= prefix[min_num]-prefix[l]:
        L.append((min_num+1, r))
    else:
        L.append((l, min_num))

```
* 勇者修練:
避免遞迴過深導致RE，再呼叫之前call 一些 function，讓它該把記憶化的記憶化。
這樣就可以避免 RE。只是怎麼call這個function就要想一下，我試了也很久才過
![image](https://hackmd.io/_uploads/S1M7IQqQJg.png)

```python=
import sys
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))
dp = [[[None]*m for _ in range(n)] for _ in range(3)]


def rec(i, j, d):
    if i == n or j<0 or j==m:
        return 0
    if i == -1:
        return max(rec(i, j+1, d), rec(i+1, j, 2))
    if dp[d][i][j] != None:
        return dp[d][i][j]
    if d == 0:
        ans = max(rec(i, j+1, d), rec(i+1, j, 2))
    elif d == 1:
        ans = max(rec(i, j-1, d), rec(i+1, j, 2))
    else:
        ans = max(rec(i, j+1, 0), rec(i, j-1, 1), rec(i+1, j, 2))

    dp[d][i][j] = ans + grid[i][j]
    return dp[d][i][j]

for i in range(n, -1, -1):
    for d in range(3):
        rec(i, 0, d)
        rec(i, m, d)
print(rec(-1, 0, 0))


# for i in range(n, -1, -1):
#     for j in range(m, -1, -1):
#         for d in range(3):
#             rec(i, j, d)
# TLE
```


## 遞迴過深的可能

1. DP
    * Bottom-up 寫法
    * 提前跑一些 fucntion ，用記憶化避免遞迴過深
2. 分治 (一般的遞迴)
    * 每一次只會 call 一個的情況：
        * 用 stack 模擬遞迴
        * 用 while 寫
    * 每一次可能會 call 兩個以上：
        * 這種情況通常不會過深
3. DFS
    * 改用 BFS 寫
    * 看好不好用 stack 模擬

* 如果遞迴深度超過 10000，就要小心記憶體可能會噴掉


12/7 - 貪心 II
===


* 低地距離 - 直接算的版本

```python=
import bisect

def main():
    n = int(input())
    tmp = list(map(int, input().split()))
    visit = set()
    ary = []
    for x in tmp:
        if x in visit:
            ary.append((x, 1))
        else:
            visit.add(x)
            ary.append((x, 0))

    # L
    def rec(L, R):
        if L+1 == R:
            return 0
        M = (L + R) // 2
        ans = rec(L, M) + rec(M, R)
        r = M
        tmp = []
        for l in range(L, M):
            while r < R and ary[r] < ary[l]: 
                tmp.append(ary[r])
                r += 1
            tmp.append(ary[l])
            cnt = r - M
            if ary[l][1] == 0:
                ans += cnt
            else:
                ans -= cnt
        while r < R:
            tmp.append(ary[r])
            r += 1
        ary[L:R] = tmp
        return ans

    print(rec(0, len(ary)))

main()
```

* 低地距離 - 算出每個點的逆序數對的版本

```python=
import bisect

def main():
    n = int(input())
    tmp = list(map(int, input().split()))
    visit = set()
    ary = []
    for i, x in enumerate(tmp):
        if x in visit:
            ary.append((x, 1, i))
        else:
            visit.add(x)
            ary.append((x, 0, i))
    cnt = [0] * (2*n)
    # L
    def rec(L, R):
        if L+1 == R:
            return 
        M = (L + R) // 2
        rec(L, M)
        rec(M, R)
        r = M
        tmp = []
        for l in range(L, M):
            while r < R and ary[r] < ary[l]: 
                tmp.append(ary[r])
                r += 1
            tmp.append(ary[l])
            cnt[ary[l][2]] += r - M
        while r < R:
            tmp.append(ary[r])
            r += 1
        ary[L:R] = tmp
    rec(0, len(ary))
    ans = 0
    for (_, who, i) in ary:
        if who == 0:
            ans += cnt[i]
        else:
            ans -= cnt[i]
    print(ans)
main()

```

* cmp_to_key : 可以直接比對兩個物品

```python=
n = int(input())
w = list(map(int,input().split()))
f = list(map(int,input().split()))
l = [(w, f) for w,f in zip(w, f) if f]
def cmp(A, B):
	if A[0] * B[1] > A[1] * B[0]:
		return 1
	elif A[0] * B[1] < A[1] * B[0]:
		return -1
	else:
		return 0
from functools import cmp_to_key
l.sort(key=cmp_to_key(cmp))

ans, prefix = 0, 0
for wi, fi in l:
	ans += prefix * fi
	prefix += wi
print(ans)
```

## 作業
* 上課題目
    * ~~[生產線, APCS 2021/11 - 3, zj g597](https://zerojudge.tw/ShowProblem?problemid=g597)~~
    * ~~[超級洗衣機](https://leetcode.com/problems/super-washing-machines)~~
    * ~~[基地台, APCS 2017/03 - 4, zj g597](https://zerojudge.tw/ShowProblem?problemid=c575)~~
    * ~~[誰先晚餐, NPSC 2005 高中決賽 PA](https://tioj.ck.tp.edu.tw/problems/1072)~~
    * ~~[Add All](https://zerojudge.tw/ShowProblem?problemid=d221)~~
    * ~~[加油站問題](https://leetcode.com/problems/gas-station)~~
    * ~~[IPO](https://leetcode.com/problems/ipo)~~
* DP 兩題
    * ~~[找硬幣問題 II，求幾種找法](https://leetcode.com/problems/coin-change-ii/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM)~~
    * ~~[Target Sum](https://leetcode.com/problems/target-sum/description/?envType=problem-list-v2&envId=dynamic-programming&difficulty=MEDIUM)~~
* 題目很多，可以先做上課題目，寫完了再練 DP 就好



12/14 - 貪心 III
===

* 數學很難但加油~~ 盡量去熟悉這種變數操作

* 上課題目
    * ~~[不相交區間](https://leetcode.com/problems/non-overlapping-intervals/description/)~~
    * ~~[湖畔大樓](https://zerojudge.tw/ShowProblem?problemid=e877)~~
        ~~* DP 也寫寫看~~
        * ~~貪心解當然也是~~
    * ~~[Assign Cookie](https://leetcode.com/problems/assign-cookies/description/)~~
    * [Pizza](https://leetcode.com/problems/pizza-with-3n-slices/description/)
        * ~~DP 解就可以了~~
* 作業 (有時間再寫，複習這次上課內容比較重要)
    * ~~[機器出租, APCS 2023/1 - 4](https://zerojudge.tw/ShowProblem?problemid=j608)~~
    * ~~[Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/description/?envType=problem-list-v2&envId=greedy&difficulty=HARD)~~
* 可以做每日題目喔~


1/11
==

* ~~https://zerojudge.tw/ShowProblem?problemid=q184~~


1/18
===
* 題目很多，所以盡量寫就好 :) 越多練習就越熟練
* ~~https://leetcode.com/problems/remove-k-digits/description/~~
* ~~https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=problem-list-v2&envId=sliding-window~~
* ~~https://leetcode.com/problems/minimum-consecutive-cards-to-pick-up/description/?envType=problem-list-v2&envId=sliding-window~~
* ~~https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/~~
* ~~https://zerojudge.tw/ShowProblem?problemid=q183~~
* ~~https://leetcode.com/problems/count-ways-to-build-good-strings~~
* ~~https://leetcode.com/problems/subarray-sum-equals-k/description/?envType=problem-list-v2&envId=prefix-sum~~
* https://leetcode.com/problems/sliding-window-median/description/?envType=problem-list-v2&envId=sliding-window
    * Median-heap: 
        * 如何維護一堆數字的中位數呢？
            * 讓 n/2 大的作 min-heap (heapq)
            * 讓 n/2 小的作 max-heap (heapq，但是取負號)
            * 中位數就會是這兩個top的平均，如果size是偶數。(是基數就看哪邊比較大，就是它的top)
            * 加入:
                * 看他要加在哪一遍 (看兩邊heap的[0]就知道了) $O(1)$
                * 如果加入會壞平衡，那就平衡一下 (最多只會需要平衡一次) $O(\log n)$
            * 刪除:
                * 採取 Laze Deletion (因為 Online Deletion 需要知道 heap 的原理)，把要刪掉的直接記在裡面 
                * 開一個dict表示這是"假裝被刪的" (要開dict，因為有重複的次數) $O(1)$
                * 看 heap 的 [0] 是不是在這個"假裝被刪的"裡面。如果有，那麼就直接pop掉 $O(\log n) \times 最多有幾個刪掉$
                * 但這樣會導致size會不平均，所以你必須額外紀錄左右兩邊實際上到底有幾個 $O(1)$
    * sliding window 每次加一個刪一個維護median-heap $O(1)$，共$O(n)$次
    * 整體 $O(n \log n)$

* 這是我的code 經過一些挖空 (挖空的code 寫了TODO)，你可以參考一下 (你可以改動我code的順序，只要你可以AC都是OK的)

```python
class MedianHeap:
    def __init__(self):
        # 比較小的堆 (self.L) / 比較大的堆 (self.R)
        self.L, self.R = [], []
        # nL: self.L 實際有多少 (不考慮 lazy 刪除)
        # nR: self.R 實際有多少 (不考慮 lazy 刪除)
        self.nL, self.nR = 0, 0
        # 標記有幾個點要刪除
        self.lazy = defaultdict(int)

    def pop_lazy(self):
        # 如果兩個堆的上面是在 lazy 刪除的，那麼移除他，
        # 直到上面不是為止。
        while self.R and self.lazy[self.R[0]] > 0:
            x = heappop(self.R)
            self.lazy[x] -= 1
        while self.L and self.lazy[-self.L[0]] > 0:
            x = -heappop(self.L)
            self.lazy[x] -= 1

    def balance(self):
        # 平衡兩個堆的大小
        while True:
            # 如果這輪沒有任何元素移動，那麼就跳掉。
            has_move = False
            # 處理 pop_lazy
            self.pop_lazy()

            while self.nL > self.nR + 1:
                # TODO: 左邊太胖，平衡一下
                has_move = True
                
            while self.nR > self.nL + 1:
                # TODO: 右邊太胖，平衡一下
                has_move = True

            if not has_move:
                return 
                
    def add(self, x):
        # TODO: 增加 x
        pass

    def delete(self, x):
        # 刪除 x，但事先標記。如果大堆有 x 那麼把 nR -=1 表示實際右邊已經少一個        
        self.balance()
        self.lazy[x] += 1
        if self.R and x >= self.R[0]:
            self.nR -= 1
        else:
            self.nL -= 1

    def get(self):
        # 先平衡
        self.balance()
        if self.nR == self.nL:
            # TODO: 找中位數
            pass
        elif self.nR > self.nL:
            # TODO: 找中位數
        else:
            # TODO: 找中位數

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        heap = MedianHeap()
        D = deque()
        ans = []
        for x in nums:
            # TODO: 做滑動視窗
        return ans
        
```
* 這題如果你想要參考別人寫的答案，那麼找他有寫 "Lazy" 的。因為不是 Lazy 的做法原理你沒學過 (當然自學也OK)。

2025/2/15
===

* `itertools.chain(A, B, C...)` 將 A, B, C 合併起來變成一個大List。
```
>>> A = [1, 2, 3]
>>> B = [4, 5, 6]
>>> C = [7, 8, 9]
>>> from itertools import chain
>>> chain(A, B, C)
<itertools.chain object at 0x000002413B27FE20>
>>> list(chain(A, B, C))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> D = [A, B, C]
>>> list(chain(D))
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> list(chain(*D))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>
```
* 為甚麼這樣做？因為 `A += B`是一個 $O(n)$ 的操作，在($|A| = n, |B| = m$ 的情況下)
    * 如果要合併多個list 就會使用 chain。
    * 忘記語法的話會使用 `A.extend(B)`，他的複雜度是 $O(m)$


```python
from collections import defaultdict
from itertools import chain
from typing import List
import sys
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self, winner:int, t:int, nxt:int) -> 'Node':
        self.t:int = t
        self.winner:int = winner
        self.nxt:List = nxt

def main() -> None:
    n, m = map(int, input().split())
    D = defaultdict(list)
    for t in range(m):
        x, y = map(int, input().split())
        # f give medals to x
        D[x].append(Node(x, t, D[y]))
        D[y] = []
    ans = [0] * (n+1) 
    def dfs(root:Node, table:dict, t, cur_max):
        table[root.winner] += t - root.t
        cur_max = max(cur_max, (table[root.winner], -root.winner))
        ans[-cur_max[1]] += 1
        for nxt in root.nxt:
            dfs(nxt, table, root.t, cur_max)
        # Recover
        table[root.winner] -= t - root.t

    root = Node(n, m, chain(*D.values()))
    dfs(root, defaultdict(int), m, (0, -n))
    print(*ans[:-1])

main()

```

* 作業: 
* EGOI padelPrize (就上面那題) 實作
* TOI 歷屆
    * ~~2024 PA. [6174 (black hole number)](https://tioj.ck.tp.edu.tw/problems/2361)~~
    * 2024 PB. [奇巧方塊 (odd square)](https://tioj.ck.tp.edu.tw/problems/2362)
    * 2024 PC. [大步小步向前走 (steps)](https://tioj.ck.tp.edu.tw/problems/2363)
        * Hint: ||DP + 回溯||
        * 可以考慮小測資就好。大測資再說。
    * ~~2022 PA. [2246 . A. 迷宮入口](https://tioj.ck.tp.edu.tw/problems/2246)~~
        * Hint : 不能直接報搜所有點，總共會有 $O(10^{12})$ 個點。
            * 仔細想一下，有可能的點只會在圖騰的周圍 (具體來說就是半徑為 r 內的格子點)，這樣最多只會有 $n \times r^2\times \frac{\pi}{4}$ 個點，大約 $190000$ 個點左右。
            * 接下來如果再繼續裸做 (對每個有可能的點搜尋 $r^2$) 還會在乘上 $r^2$。應該還是會TLE。有沒有更優雅的方法處理這塊呢？
    * 2022 PB. [2247 . B. 打鍵盤](https://tioj.ck.tp.edu.tw/problems/2247)
        * Hint: DP解。定義 $DP[n][a][b] = 左手放在 a 上 右手放在 b 上，打到第 n 個字的最短時間$
        * 這題可以看出TOI的尿性，就是題目很搞，把鍵盤Key上去很浪費時間但沒辦法。
    * 2022 PC. [2248 . C. 共享自行車](https://tioj.ck.tp.edu.tw/problems/2248)
        * Hint: 可以用 dfs 的方法解，作法類似Greedy的超級洗衣機的感覺，但是是在樹上。
        * Hint2: 如果不會用 dfs，那麼 Kahn's Algorithm 也是個方法 (拓樸)，但比較難寫
    * 2022 PD. [2249 . D. 2022](https://tioj.ck.tp.edu.tw/problems/2249)
        * 數學題，看看就好，有想法再寫
    * 2022 PE. [2250 . E. 間諜](https://tioj.ck.tp.edu.tw/problems/2250)
        * 寫暴力搜尋就好 (Backtracking)，這題AC**應該是**要用構造解


3/8
===

* ~~https://leetcode.com/problems/maximize-win-from-two-segments/description/~~
    自己寫的Memory Limit Exceeded，最後去看解答了
* ~~https://leetcode.com/problems/regular-expression-matching/description/~~
~~* (LCA) https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/~~
    * 自己寫寫看倍增搜
---
我下週段考完再寫~
撿回你圖論的記憶
* ~~https://leetcode.com/problems/possible-bipartition/description/?envType=problem-list-v2&envId=graph~~
    * 二分圖判別
* ~~https://leetcode.com/problems/number-of-provinces/description/?envType=problem-list-v2&envId=graph~~
    * BFS / DFS / Disjoint Set
* https://leetcode.com/problems/redundant-connection-ii/description/?envType=problem-list-v2&envId=graph
* ~~https://leetcode.com/problems/sum-of-distances-in-tree/description/~~
    * DFS
* https://leetcode.com/problems/time-taken-to-mark-all-nodes/description/?envType=problem-list-v2&envId=graph

3/15
===
* 區間選擇類的三題
    * 盡量每個寫法都試過一遍
* [投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
* 上次的題目


3/22
===
* [你的ZJ帳號](https://zerojudge.tw/UserStatistic?id=274032)

歷年APCS補完計畫:
* [互補CP](https://zerojudge.tw/ShowProblem?problemid=e288) TLE不知道更快的做法
```python
from collections import defaultdict
m, n = map(int, input().split())

table = defaultdict(int)
lt = set()
for i in range(n):
    tmp = "".join(sorted(set(input())))
    table[tmp] += 1
    lt.add(tmp)
lt = list(lt)

for i in range(len(lt)):
    a = lt[i]
    for j in range(i+1, len(lt)):
        b = lt[j]
        if not set(a)&set(b) and len(a)+len(b)==m:
            ans += table[a]*table[b]
print(ans)
```
* ~~[圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581)~~
* ~~[支點切割](https://zerojudge.tw/ShowProblem?problemid=f638) WA不知道錯哪裡~~
```python
n, K = map(int, input().split())
p = list(map(int, input().split()))
prefix = [0]*n
prefix[0] = p[0]
for i in range(1, n):
    prefix[i] = prefix[i-1] + p[i]
ans = 0

def rec(left, right, k):
    #判斷能不能切
    if k==K or right-left<2:
        return
    global ans
    #初始化
    temp = 0
    count = 1
    for i in range(left+1, right+1):
        temp += p[i]*count
        count += 1

    #找最佳切點
    m = (float("inf"), 1)
    for i in range(left+1, right):
        temp -= prefix[right] - (prefix[left-1] if left else 0)
        m = min(m, (abs(temp), i))
    ans += p[m[1]]

    #切下去
    rec(left, m[1]-1, k+1)
    rec(m[1]+1, right, k+1)

rec(0, n-1, 0)
print(ans)
```
* ~~[函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)~~
    * 要馬用 stack 要馬用 遞迴
```python=
S = input().split()
idx = 0
# 從 idx 往後看的運算式數值是多少
def rec():
    global idx
    if S[idx] == 'f':
        idx += 1
        x = rec()
        return 2*x - 3
    elif S[idx] == 'g':
        idx += 1
        x = rec()
        y = rec()
        return 2*x + y - 7
    elif S[idx] == 'h':
        idx += 1
        x = rec()
        y = rec()
        z = rec()
        return 3*x - 2*y + z
    else:
        val = int(S[idx])
        idx += 1
        return val

print(rec())
```
* ~~[牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)~~
* ~~[先加後乘與函數](https://zerojudge.tw/ShowProblem?problemid=j607)~~

```python=
S = input()
idx = 0
def get_number():
    global idx
    if S[idx].isdigit():
        cur_digit = 0
        while idx < len(S) and S[idx].isdigit():
            cur_digit = cur_digit * 10 + int(S[idx])
            idx += 1
        return cur_digit
    elif S[idx] == 'f':
        idx += 1
        assert S[idx] == '('
        idx += 1
        L = []
        while True:
            L.append(rec())
            if S[idx] == ',':
                idx += 1
            elif S[idx] == ')':
                idx += 1
                break
            else:
                assert False
        return max(L) - min(L)      
    else:
        print("Error")


def rec():
    global idx

    ans = 1
    tmp = get_number()
    while idx < len(S):
        if S[idx] == '+':
            idx += 1
            tmp += get_number()
        elif S[idx] == '*':
            idx += 1
            ans *= tmp
            tmp = get_number()
        else:
            break
    return ans * tmp
print(rec())
```

* 逃課做法，但zj不給用
```python
import re
S = input()
S = re.sub(r'(\d+)', r'A(\1)', S)
S = S.replace('+', 'B')
S = S.replace('*', '+')
S = S.replace('B', '*')

def f(*L):
    return max(L) - min(L)

class A:
    def __init__(self, x):
        self.x = x
    def __add__(self, other):
        return A(self.x * other.x)
    def __sub__(self, other):
        return A(self.x - other.x)
    def __mul__(self, other):
        return A(self.x + other.x)
    def __lt__(self, other):
        return self.x < other.x
exec(f"print(({S}).x)")
```

3/29
===

* https://www.csie.ntu.edu.tw/~yvchen/f108-ada/doc/ada19-hw1.pdf
    * 第六題 (分治+greedy)
    * 第七題 (DP)
        * 1. 一塊連著的方塊，O(1)得知有沒有解
        * 2. 一塊連著的方塊，O(log N) 告訴我怎麼翻
            * (分治 / 遞迴)
        * 3. 證明一個方塊往左碰到下個方塊的距離是 d1, 往右是d2，那麼這個方塊翻完後的狀態最多只有 O(d1 + d2) 種
        * 4. DP 告訴我這個盤面有沒有解
            * 每個盤面初始有 n 個方塊，每個方塊有其位置跟長度
* Split Array Largest Sum 看到 O(n^2k) 就好了
* 區間分割的兩題 (平衡字串 + 切回文)


4/12
===
*  ~~[石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)~~ 簡單！我一次就AC了
*  ~~[DF-Expression](https://zerojudge.tw/ShowProblem?problemid=f637)~~ 跟上一題一樣簡單
* ~~[投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)~~
* ~~[貨物分配](https://zerojudge.tw/ShowProblem?problemid=h029)~~
* [數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083) 我想不到，但是有看懂別人的解答
    * 少數的字串題

4/19
===
* ~~[樹狀圖分析](https://zerojudge.tw/ShowProblem?problemid=c463)~~
* ~~[傳送點](https://zerojudge.tw/ShowProblem?problemid=f166)~~
* ~~[蓋步道](https://zerojudge.tw/ShowProblem?problemid=j125)~~

4/26
===

* APCS練習題
    * ~~[開啟寶盒](https://zerojudge.tw/ShowProblem?problemid=k734)~~
    * ~~[連鎖反應](https://zerojudge.tw/ShowProblem?problemid=o713)~~
    * ~~[真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)~~
        * 目前大概兩種做法
            * DFS + 二分搜 我做的是這個
            * DSU + redo
    * ~~[合併成本](https://zerojudge.tw/ShowProblem?problemid=m934)~~
* DP上課練習題目
    * ~~[骨牌問題](https://leetcode.com/problems/domino-and-tromino-tiling/description/)~~
    * ~~[陣列分割](https://leetcode.com/problems/split-array-largest-sum/)~~
        * 可以跟著投影片試著寫寫看
* DP作業
    * [painting-a-grid-with-three-different-colors](https://leetcode.com/problems/painting-a-grid-with-three-different-colors/description/)
    * ~~[Partition Array for Maximum Sum](https://leetcode.com/problems/partition-array-for-maximum-sum/description/)~~

5/10
===

* https://slides.com/arvinliu2/net_intro#/1/5/1


### Git

#### 初始化與複製
- `git init`  
  在目前資料夾建立一個新的 Git 儲存庫（Repository）。
- <span style="color:red">`git clone <repo-url>`  
  將遠端儲存庫完整複製到本機。</span>

#### 工作區與暫存區
- <span style="color:red">`git status`  
    顯示目前工作區與暫存區的狀態變更。</span>
    ![image](https://hackmd.io/_uploads/BJ_wvE7blg.png)
    * U: untracked file: 表示這個檔案整個是新的。
    * M: modified: 表示這個檔案被修改過。

- <span style="color:red">`git add <file>`  
  將檔案變更加入到暫存區（stage）。</span>
- `git reset <file>`  
  將暫存區的指定檔案變更移出，不影響工作區。
- `git reset --hard HEAD`
  放棄本地所有修改，回到上一個commit點

#### 提交（Commit）
- <span style="color:red">`git commit -m "描述訊息"`  
  將暫存區的變更提交到本地分支，並附上說明訊息。</span>
- `git commit --amend`  
  修改最後一次提交的說明或內容（慎用於已推送的提交）。

#### 查看歷史
- `git log`  
  查看提交歷史列表。
- `git log --oneline --graph --all`  
  以簡潔一行與圖形化方式顯示所有分支歷史。

#### 分支管理
- `git branch`  
  列出本地所有分支，當前所在分支前會標 `*`。
- `git branch <new-branch>`  
  建立新分支（不會自動切換）。
- `git checkout <branch>`  
  切換到指定分支。
- `git checkout -b <new-branch>`  
  建立並切換到新分支。

#### 合併與重整
- `git merge <branch>`  
  將指定分支合併到目前分支。
- `git rebase <branch>`  
  以指定分支為基底，重放當前分支的提交歷史。

#### 遠端操作
- `git remote -v`  
  顯示設定的遠端儲存庫名稱與 URL。
- <span style="color:red">`git push <remote> <branch>`  
    推送本地分支到遠端儲存庫。</span>
- <span style="color:red">`git pull <remote> <branch>`  
  從遠端拉取並合併最新變更到本地。</span>

#### 其他實用指令
- `git diff`  
  顯示工作區或暫存區與最後一次提交的差異。
- `git stash`  
  臨時存放工作區未提交的變更，以便切換分支。
- `git stash pop`  
  取回並套用最近一次 stash 的變更。
- `git revert <commit>`  
  產生一個新的提交，用來反向還原指定提交的變更。


    
5/17
===
    
    
## File IO

1. 告訴電腦你要對哪個檔案進行操作
    * `open(FILE_PATH, MODE)`
    * `MODE = "r", "w", "a", "rb", "wb"`
2. 可以對這個變數進行 write / read。
3. 用完的話，告訴電腦你不要用了
    * close
    
```python=
fout = open("tmp.txt", "w")
fout.write("HI")
fout.close()

fin = open("tmp.txt", "r")
s = fin.read()
print(s)
fin.close()

# With: 會幫你自動 close
with open("tmp.txt", "w") as fout:
    fout.write("HI")

with open("tmp.txt", "r") as fin:
    print(fin.read())
```

## 作業    
* Zerojudge 等題目 push 上去 稍微寫一下，讓readme 不要那麼單薄
* ~~Sudoku-Puzzle - Readme 寫一下~~
* Simple 16-Puzzle - 按照 Sudoku 一樣創出這樣子的project

    