2022 TOI初選題目整理 by Cookie197 (2022.3.13)

# 2022 TOI初選題目整理 by Cookie197 (2022.3.13) ###### tags: `競程筆記` #### Scoreboard https://sorahisa.github.io/OI/DumpedRanks/toi2022/ranking/Ranking.html 有拿分的人數 : $260$ 人 --- ## pA ~~神秘入口~~ ### Problem Statement 有$n$個圖騰，每個圖騰的「影響範圍」都是一個半徑$r$的圓。請問有多少個格子點(座標是整數的點)恰好被奇數個圖騰影響？ ### Constraints $n\le 2500$, $r\le10$, 座標絕對值$\le 1000000$ ### Subtasks $[26]$ ? $[36]$ ? $[38]$ 無額外限制 ### Statistics $AC$ : $99$ 人 $[62]$ : $78$ 人 $[36]$ : $3$ 人 $[26]$ : $56$ 人平均分數 : $62.3$ --- ## pB 打鍵盤 ### Problem Statement 有一個人在打字，但他只會用兩隻手指頭。一開始左手在F右手在J。對於一個想打的字母，他可以選擇要把左手移過去或是右手移過去，花費的時間就是他們在鍵盤上的最短距離。打完那個字之後手就會停在那裡。給你一個長度$n$的字串，問他要多久才能把他打完。 ### Constraints $n\le 10000$ ### Subtasks $[29]$ $n\le 20$ $[30]$ 只有和 F J 同一行的字母 $[41]$ 無額外限制 ### Statistics $AC$ : $54$ 人 $[30]$ : $7$ 人 $[29]$ : $27$ 人平均分數 : $24.6$ --- ## pC ~~歸還Ubike問題~~ ### Problem Statement 給你一顆邊帶權的樹，每個節點上都有零個以上的人。你希望讓每個點上最後人數都是$k$。請問那些人移動距離的總和最少是多少？（總人數一定是$n \times k$） ### Constraints $n\le 100000$, 邊權 $\le 10^9$（好像吧） $k\le 10$ ### Subtasks 忘了！ ### Statistics $AC$ : $55$ 人 $[38]$ : $1$ 人 $[28]$ : $6$ 人 $[27]$ : $1$ 人 $[17]$ : $1$ 人 $[11]$ : $20$ 人平均分數 : $22.9$ --- ## pD 2022 ### Problem Statement 給你兩個正整數$x, y$，定義一個「好的數字」： * 只由 $0$ 和 $2$ 組成，恰有 $x$ 個 $0$ 和 $y$ 個 $2$ * 是 $22$ 的倍數 * 可以有leading zeroes 請問第二大和第二小的「好的數字」？ ### Constraints $x,y \le 100000$ ### Subtasks $[8]$ $x,y \le 10$ $[7]$ $x,y \le 30$ $[17]$ $x,y \le 300$ $[24]$ $y$ 是偶數 $[44]$ 無額外限制 ### Statistics $AC$ : $16$ 人 $[56]$ : $1$ 人 $[39]$ : $1$ 人 $[32]$ : $101$ 人 $[24]$ : $4$ 人 $[8]$ : $35$ 人平均分數 : $20.4$ --- ## pE 間諜 ### Problem Statement 一個$n\times m$的棋盤方格，你要構造一個路徑使得每個格子恰走過一次，而且路徑中任兩個連續的格子都不共用直行/橫列/對角線，最後還要可以回到一開始的點。 ### Constraints $n\times m\le 2000$ ### Subtasks $[7]$ $n\times m \le 16$ $[35]$ $n = 2$ or $m = 2$ $[40]$ $n \ge 12$ and $m \ge 12$ $[18]$ 無額外限制 ### Statistics $AC$ : $1$ 人 $[42]$ : $9$ 人 $[35]$ : $14$ 人 $[7]$ : $9$ 人平均分數 : $3.96$