上課筆記哈
===
* 重要！
[實作備戰手冊](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 有最佳子結構 (可以從小排序陣列變成大排序陣列)，但沒有重複子問題。
* 如何實作？先考慮一個小問題：
如何把兩個排序好的序列，變成一個排序好的序列？
考慮完後用遞迴寫出來就可以了。
```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> </td>
</tr>
<tr>
<td><a href="https://zerojudge.tw/ShowProblem?problemid=i402" target="_blank">內積</a></td>
<td>APCS 2022 / 06 - 4</td>
<td> </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> </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 可以你想複習再複習。
#### 程式題目
* 動態規劃：上課題目 (美食博覽會) / 置物櫃分配。
* 還有上課的練習題 (~~倒油漆~~，數獨，sliding puzzle)
#### 動動腦想想看
#### 順位
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就要想一下，我試了也很久才過
```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>
* 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
Sign in with Wallet
Connect another wallet