# TOI 2021 入營考 題目整理

## A. 原始人排序

給 $N$ 個數字 $a_1 \sim a_N$，把所有數字按照二進制 $1$ 的個數排序，如果相同就按照出現順序排序。

- $N \le 1000$
- $0 \le a_i < 2^{10}$
- $[40]$ $N \le 7$
- $[60]$ 無額外限制

[Input Format]
N
a_1 a_2 ... a_N

[Output Format]
ans_1 ans_2 ... ans_N

## B. 掃地機器人

ref: [TIOJ 1399](https://tioj.ck.tp.edu.tw/problems/1399)

有 $N$ 間房間，在第 $i$ 間房間總共待了 $t$ 秒可以獲得 $\displaystyle \sum_{x=0}^{t-1}{\max(0, a_i - b_i x)}$ 的分數。

一開始你在房間 $1$，在房間 $i$ 跟 $(i+1)$ 之間移動需要花費 $c_i$ 秒，同一間房間可以重複獲得分數，求經過 $T$ 秒之後的分數最大值。

- $N \le 1000$
- $T \le 10^9$
- $0 \le a_i, b_i, c_i \le 10^9$
- $[30]$ $T \le 1000$
- $[70]$ 無額外限制

[Input Format]
N T
c_1 c_2 ... c_{N-1}
a_1 a_2 ... a_N
b_1 b_2 ... b_N

[Output Format]
ans

## C. 粉刷護欄

給你長度為 $N$ 的序列 $\langle a \rangle, \langle b \rangle$，其中 $a_i$ 互不相同，$b_i$ 也互不相同，且 $a$ 跟 $b$ 在經過排序後會相同。

現在有 $N$ 根棍子，編號為 $i$ 的棍子會連著上下編號為 $i$ 的數字。請你求出一個大小最大的序列 $\mathcal{S} = \{p_1, p_2, \dots, p_{|\mathcal{S}|}\}$ 使在 $\langle a \rangle$ 和 $\langle b \rangle$ 中數字為 $p_i$ 的位置嚴格遞增。

也就是說，如果讓 $a'_i$ 跟 $b'_i$ 表示數字 $i$ 在 $\langle a \rangle, \langle b \rangle$ 的位置，那你選出的序列 $\mathcal{S}$ 需要滿足所有 $p_i$ 都有在 $\langle a \rangle$ 和 $\langle b \rangle$ 出現過，且須符合 $a'_{p_1} < a'_{p_2} < \dots < a'_{p_{|\mathcal{S}|}}$ 跟 $b'_{p_1} < b'_{p_2} < \dots < b'_{p_{|\mathcal{S}|}}$。

如果有多組解請輸出使 $\mathcal{S}$ 字典序最大的一組。

- $N \le 2 \times 10^5$
- $0 \le a_i, b_i \le 10^9$
- $[22]$ $N \le 10$
- $[33]$ $N \le 100$
- $[45]$ 無額外限制

[Input Format]
N
a_1 a_2 ... a_N
b_1 b_2 ... b_N

[Output Format]
p_1 p_2 ... p_{|S|}

[Sample Input 1]
10
1 3 9 5 4 6 8 2 18 10
3 1 4 5 9 2 10 6 8 18

[Sample Output 1]
5
3 9 6 8 18

## D. 乘車時間

有一棵樹狀的鐵路圖，點數為 $N$。每條邊 $(u,v)$ 會雙向發車，題目會給你 $u \rightarrow v$ 及 $v \rightarrow u$ 第一班車的時間為 $0$ 點 $a_i$ 及 $0$ 點 $b_i$ 分和班距 $p_i$ 跟開到另一個端點的時間 $w_i$，且 $a_i, b_i < p_i$。兩邊的第一班車發車時間不一定相同，不過班距跟行駛時間都會相同。

另外，若你在時間 $t$ 到達車站，你只能搭時間在 $(t+1)$ 之後的車（轉車需要花 $1$ 單位時間）。

接著有 $Q$ 筆詢問，求在時間 $h_i$ 時 $m_i$ 分從 $x_i$ 出發最快多久可以到達 $y_i$。

- $N \le 5 \times 10^4$
- $Q \le 2 \times 10^5$
- $1 \le u_i, v_i, x_i, y_i \le N$，$u_i \ne v_i$，$x_i \ne y_i$
- $0 \le a_i, b_i < p_i \le 6$
- $1 \le w_i \le 1000$
- $0 \le h_i \le 23$，$0 \le m_i \le 59$
- $[16]$ $N \le 500$
- $[31]$ $p_i = 1$
- $[37]$ $u_i = i,\ v_i = i+1$（樹的形狀為一條鏈）
- $[16]$ 無額外限制

[Input Format]
N Q
u_1 v_1 w_1 a_1 b_1 p_1
u_2 v_2 w_2 a_2 b_2 p_2
...
u_{N-1} v_{N-1} w_{N-1} a_{N-1} b_{N-1} p_{N-1}
h_1 m_1 x_1 y_1
h_2 m_2 x_2 y_2
...
h_Q m_Q x_Q y_Q

[Output Format]
ans_1
ans_2
...
ans_Q

## E. 密室逃脫

ref: [UVa 11383](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2378)

給 $N \times N$ 的方格，$(i, j)$ 上面的數字是 $a_{i,j}$，每次可以選一個 row 或 column 全部減一，求能把所有數字變成 $\le 0$ 的最少操作次數，並給出任意一組解。

- $N \le 500$
- $0 \le a_{i,j} \le 2 \times 10^6$
- $[20]$ $N \le 20,\ a_{i,j} = \{0, 1\}$
- $[40]$ $N \le 70,\ a_{i,j} = \{0, 1\}$
- $[35]$ $N \le 70$
- $[5]$ 無額外限制
- 輸出格式正確並且輸出正確的最少操作數可以得到該子題 $40\%$ 的分數

[Input Format]
N
a_{1,1} a_{1,1} ... a_{1,N}
a_{1,1} a_{2,1} ... a_{2,N}
...
a_{N,1} a_{N,1} ... a_{N,N}

[Output Format]
ans
r_1 r_2 ... r_N
c_1 c_2 ... c_N

## Scoreboard

:::spoiler Scoreboard
https://cms.tfcis.org/dumprank/rank/toi2021/
:::

## 解說

:::spoiler Editorial
by 學長: https://www.nekoio.net/toi-primary-2021/
（如果題解有部分被卡掉請調整視窗寬度）
:::