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

有

$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$ 的序列

$⟨a⟩,⟨b⟩$，其中

$a_i$ 互不相同，

$b_i$ 也互不相同，且

$a$ 跟

$b$ 在經過排序後會相同。

現在有

$N$ 根棍子，編號為

$i$ 的棍子會連著上下編號為

$i$ 的數字。請你求出一個大小最大的序列

$\mathcal{S}=\{p_1,p_2,\dots ,p_{|\mathcal{S}|}\}$ 使在

$⟨a⟩$ 和

$⟨b⟩$ 中數字為

$p_i$ 的位置嚴格遞增。

也就是說，如果讓

$a_i^{\prime }$ 跟

$b_i^{\prime }$ 表示數字

$i$ 在

$⟨a⟩,⟨b⟩$ 的位置，那你選出的序列

$\mathcal{S}$ 需要滿足所有

$p_i$ 都有在

$⟨a⟩$ 和

$⟨b⟩$ 出現過，且須符合

$a_{p_1}^{\prime }<a_{p_2}^{\prime }<\cdots <a_{p_{|\mathcal{S}|}}^{\prime }$ 跟

$b_{p_1}^{\prime }<b_{p_2}^{\prime }<\cdots <b_{p_{|\mathcal{S}|}}^{\prime }$。

如果有多組解請輸出使

$\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\to v$ 及

$v\to 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

給

$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\mathrm{\%}$ 的分數

[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

Scoreboard

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

解說

Editorial

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