## 迴圈
### 11/1 社課
----
今天會講很多迴圈和串列的題目，所以不熟的話一定要複習前面的內容
---
## 複習
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
如果整數 $1, 2, \ldots, n$ 的一個排列中，沒有任何相鄰元素的差為 $1$ ，那麼這個排列稱為漂亮的排列。
給定 $n$，若存在漂亮的排列，請輸出其中一個。
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
- 如果相鄰元素的差不能為 $1$ ，那就考慮相鄰元素的差為 $2$
- 把奇數全部放在一起，偶數也全部放在一起
- 要先放奇數還是偶數？
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
- 考慮 $n=4$
- 先放奇數， $1、3、2、4$ 會出問題
- 先放偶數， $2、4、1、3$ 不會出問題
- 先放偶數！
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
- $n=2$ 的情況排列只能是 $1、2$ 或 $2、1$ ，無解
- $n=3$ 考慮前兩個數，只能放 $1、3$ 或 $3、1$
- 但最後一個數字只能放 $2$ ，因此也無解
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
- 如果 $n=2$ 或 $n=3$ ，輸出`NO SOLUTION`
- 否則先輸出偶數再輸出奇數
----
### [CSES - Permutations](https://cses.fi/problemset/task/1070)
```python
n = int(input())
if n == 2 or n == 3:
print("NO SOLUTION")
else:
for i in range(2, n + 1, 2):
print(i, end = " ")
for i in range(1, n + 1, 2):
print(i, end = " ")
```
----
### [CSES - Trailing Zeros](https://cses.fi/problemset/task/1618)
計算階乘 $n!$ 中後綴零的數量。
----
### [CSES - Trailing Zeros](https://cses.fi/problemset/task/1618)
- 每個後綴零都來自一對 $2$ 和 $5$ 相乘
- $n!$ 中，因數 $2$ 的數量必定大於因數 $5$ 的數量
- 因數 $5$ 的數量就是後綴零的數量！
- 先數 $5^1$ 的倍數數量，再數 $5^2$ 的倍數數量，再數 $5^3$ 的倍數數量，依此類推
----
### [CSES - Trailing Zeros](https://cses.fi/problemset/task/1618)
```python
n, i, cnt = int(input()), 5, 0
while i <= n:
cnt += n // i
i *= 5
print(cnt)
```
----
### [Zerojudge - 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
判斷一個身分證字號是否是正常的號碼。
----
### [Zerojudge - 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
這是對的，但顯然正常作法不是這樣
```python
s = input()
check = 0
if s[0] == 'A':
check += 1
elif s[0] == 'B':
check += 10
elif s[0] == 'C':
check += 19
elif s[0] == 'D':
check += 28
elif s[0] == 'E':
check += 37
elif s[0] == 'F':
check += 46
elif s[0] == 'G':
check += 55
elif s[0] == 'H':
check += 64
elif s[0] == 'I':
check += 39
elif s[0] == 'J':
check += 73
elif s[0] == 'K':
check += 82
elif s[0] == 'L':
check += 2
elif s[0] == 'M':
check += 11
elif s[0] == 'N':
check += 20
elif s[0] == 'O':
check += 48
elif s[0] == 'P':
check += 29
elif s[0] == 'Q':
check += 38
elif s[0] == 'R':
check += 47
elif s[0] == 'S':
check += 56
elif s[0] == 'T':
check += 65
elif s[0] == 'U':
check += 74
elif s[0] == 'V':
check += 83
elif s[0] == 'W':
check += 21
elif s[0] == 'X':
check += 3
elif s[0] == 'Y':
check += 12
else:
check += 30
for i in range(1, 9):
check += (9 - i) * int(s[i])
check += int(s[9])
if check % 10 == 0:
print("real")
else:
print("fake")
```
----
### [Zerojudge - 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
先介紹 ACSII Code
----
### [Zerojudge - 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
- 在 Python 中可以用 `ord()` 將一個字元轉換成 ACSII Code ， `chr()` 將 ACSII Code 轉換成字元
- 把 ACSII Code 當成串列的索引！
----
### [Zerojudge - 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
```python
ind = [1, 10, 19, 28, 37, 46, 55, 64, 39, 73, 82, 2, 11, 20, 48, 29, 38, 47, 56, 65, 74, 83, 21, 3, 12, 30]
s = input()
check = 0
check += ind[ord(s[0]) - ord('A')]
for i in range(1, 9):
check += (9 - i) * int(s[i])
check += int(s[9])
if check % 10 == 0:
print("real")
else:
print("fake")
```
----
### 練習
Zerojudge - 四則運算
---
## stack
----
### stack
- 後入先出 (LIFO, Last In, First Out) 的資料結構
- 後加入stack的元素會先被移除
----
### stack
----
### stack
- Python 的串列有`append()`、`pop()`
- 串列其實可以當做 stack 用
----
### [Zerojudge - stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213)
```python
n = int(input())
stack = []
for i in range(n):
e = input()
if e.startswith("1"):
_, x = e.split()
stack.append(x)
elif e.startswith("2"):
if stack:
print(stack[-1])
else:
print(-1)
else:
if stack:
stack.pop()
```
----
### [Zerojudge - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
有一個車站，火車從右邊來、從左邊離開。判斷火車能否以一特定的排列方式在左邊的鐵軌上。
----
### [Zerojudge - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
- 車站就是一個 stack
- 直接模擬
----
### [Zerojudge - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
```python
while True:
n = int(input())
if n == 0:
break
while True:
a = list(map(int, input().split()))
if a[0] == 0:
break
cur = 0
stack = []
for i in range(1, n + 1):
stack.append(i)
while stack and stack[-1] == a[cur]:
stack.pop()
cur += 1
if not stack:
print("Yes")
else:
print("No")
print()
```
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
給定一個包含 $n$ 個整數的陣列，對於每個整數，找到其左側最近的較小值所在的位置，如果沒有則輸出 $0$
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
- 如果每一次都往左檢查直到找到較小值會太慢
- 可以觀察到在陣列中的任兩個數字，若左邊的數字大於右邊的數字，那麼右邊的數字以後的所有數字都不會以左邊的數字為答案
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
- 可以維護一個隊列，在一個數加入隊列前把所有大於等於該數的數字全部都刪除
- 得到答案後再把這個數加入隊列中，可以發現因為加入的數必定大於隊列裡面所有的數，因此這個隊列必定是遞增的，因此這個技巧被稱為「單調」隊列
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
- 因為隊列是遞增的，所以在插入一個數字前做刪除操作時只會從隊列的最後開始更改，插入數字時也是放到數字最尾端
- 可以用 stack 來實作，並維護其內容單調遞增
- 實作上要注意因為要輸出的是「位置」而不是「值」，因此在隊列中直接存元素所在的位置會方便許多，而隊列維護的內容為「其對應的值呈單調遞增」
----
### [CSES - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
```python
n = int(input())
a = list(map(int, input().split()))
stack = []
for i in range(n):
while stack and a[stack[-1]] >= a[i]:
stack.pop()
if stack:
print(stack[-1] + 1, end = " ")
else:
print(0, end = " ")
stack.append(i)
```
----
### 練習
[Zerojudge - 最大矩形](https://zerojudge.tw/ShowProblem?problemid=b123)
----
### [Zerojudge - 最大矩形](https://zerojudge.tw/ShowProblem?problemid=b123)
```
while True:
try:
m, n = map(int, input().split())
a = []
mx = 0
for i in range(m):
a.append(list(map(int, input().split())))
for i in range(1, m):
for j in range(n):
if a[i][j] == 1:
a[i][j] += a[i - 1][j]
for i in range(m):
lmin, rmin, sl, sr = [-1] * n, [n] * n, [], []
for j in range(n):
while sl and a[i][sl[-1]] >= a[i][j]:
sl.pop()
if sl:
lmin[j] = sl[-1]
sl.append(j)
for j in range(n - 1, -1, -1):
while sr and a[i][sr[-1]] >= a[i][j]:
sr.pop()
if sr:
rmin[j] = sr[-1]
sr.append(j)
for j in range(n):
mx = max(mx, (rmin[j] - lmin[j] - 1) * a[i][j]);
print(mx)
except:
break
```
{"title":"迴圈","contributors":"[{\"id\":\"3aeed4e7-1118-47e7-b0cc-18caea236427\",\"add\":8704,\"del\":412}]","description":"結果"}