108 北一區資訊學科能力競賽 + 題解

--- tags: Editorial --- # 108 北一區資訊學科能力競賽 + 題解 > 比賽時間：2019/11/13（三） > 參賽人數：29 位 > 晉級人數：2 位 > 評分標準：CMS，同分以執行時間比較 [TOC] ## 上午場 09:00 ~ 12:00 ### pA. 電話民調計票 **題目敘述** $N$ 位候選人，$P$ 位投票者，每位民眾最多可以投給 $M$ 個人有效的投票是一個長度為 $N$ 的字串，其中只包含最多 $M$ 個 `*`，其餘皆為 `0`。請計算每位候選人的得票數並排序。 **數據範圍** - $N, M \le 100$ - $P \le 5\,000$ | 子題 | 分數 | 限制 | |:----:|:--------------------:|:----------------:| | $1$ | $5\ 組 \times 1\ 分$ | 投票必定合理 | | $2$ | $5\ 組 \times 2\ 分$ | 投票長度必定合理 | | $3$ | $5\ 組 \times 2\ 分$ | 無額外限制 | :::spoiler 題解 by SorahISA $\qquad$ 對每次投票，只要長度不同或是 $\texttt{'*'}$ 超過 $M$ 個就直接 break，就剩下 sort 了～只要自己寫一個 cmp 就好。 $\qquad$ [Code by SorahISA](https://pastebin.com/w3kMb8SS) :::  ### pB. 採草莓問題 **題目敘述** 輸入同 $\text{IOI 1994 D1T1. The Triangle}$ <a href = "http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb1/problem.html"> Link </a> 不過要走到從左上角走到右下角並輸出路徑，向東優先，一開始在左上角格子的左邊，最後走到右下角格子的右邊。 **數據範圍** - $N \le 100$ | 子題 | 分數 | 限制 | |:----:|:--------------------:|:----------------------------------:| | $1$ | $3\ 組 \times 1\ 分$ | $N \le 10$，且不存在兩條相同的路徑 | | $2$ | $4\ 組 \times 3\ 分$ | $10 < N \le 50$ | | $3$ | $2\ 組 \times 5\ 分$ | $50 < N \le 100$ | :::spoiler 題解 by SorahISA $\qquad$ 基本的 dp～ $\qquad$ 走到 $\texttt{map[i][j]}$ 的最大收益是 $\texttt{map[i-1][j]}$ 跟 $\texttt{map[i][j-1]}$ 的最大值加上 $\texttt{strawberry[i][j]}$，不過要列出路徑，所以就把所有地方的轉移來源都記下來。 $\qquad$ 如果遇到同時可以走兩個方向，就紀錄是從「上面」轉過來的，因為在回朔路徑走法時，一定會有頭尾的 $\texttt{E}$、$(N-1)$ 次向 $\texttt{E}$、$(N-1)$ 次向 $\texttt{S}$，所以後面多走一點向南的路，就代表前面可以走較多向東的路。 $\qquad$ [Code by SorahISA](https://pastebin.com/QmC1RgpY) :::  ### pC. 解碼問題 **題目敘述** 將密鑰的空白以及重複字元刪除，再將 `a~z` 中剩餘字元依序接在後面，接下來按照字母表將其加密。輸入第一行是 $0$ 或 $1$，代表解密或加密。第二行是密鑰，由小寫組成，可能有空格。第三行是明文或密文，可帶有大小寫及空格，大小寫及空白按照原樣輸出。 **數據範圍** - $|S| \le 2\,000$ | 子題 | 分數 | 限制 | |:----:|:--------------------:|:----------:| | $1$ | $5\ 組 \times 5\ 分$ | 無額外限制 | :::spoiler 題解 by SorahISA $\qquad$ 用 set 去紀錄每個字元有沒有被選過，以此構建出字母對應表，剩下就是暴力ㄌ～如果遇到空白就直接輸出，遇到大寫就先轉小寫，加密 / 解密後再變回來。 $\qquad$ [Code by SorahISA](https://pastebin.com/AbegtQh1) :::  ### pD. 戳戳樂問題 **題目敘述** 在 $N \times M$ 的棋盤上確認一組多皇后的解是否有問題。對於所有有問題的點座標按照由左到右，由上到下輸出。 **數據範圍** - $N, M \le 500$ | 子題 | 分數 | 限制 | |:----:|:---------------------:|:-------------:| | $1$ | $1\ 組 \times 1\ 分$ | $N,M \le 5$ | | $2$ | $1\ 組 \times 2\ 分$ | $N,M \le 10$ | | $3$ | $1\ 組 \times 4\ 分$ | $N,M \le 20$ | | $4$ | $1\ 組 \times 8\ 分$ | $N,M \le 100$ | | $5$ | $1\ 組 \times 10\ 分$ | $N,M \le 500$ | :::spoiler 題解 by SorahISA $\qquad$ 如果暴力可以作到 $O(NM(N+M))$ 好像也可以過？ $\qquad$ 不過教授說要壓執行時間，所以可以改成紀錄每個直行、橫列、$2 \times (N+M-1)$ 條對角線有幾個洞再判斷，這樣就是 $O(NM)$ 了耶！ $\qquad$ [Code by SorahISA](https://pastebin.com/uZweTxEY) :::  ## 下午場 13:00 ~ 15:00 ### pE. 哆啦A夢的生日 **題目敘述** 已知 $2112/01/01$ 是星期五 $Q$ 次詢問 $2102/01/01$ 到 $2122/01/01$ 年之間的某一天是星期幾輸入長這樣： ``` 2 2112/01/01 2112/02/29 ``` 輸出長這樣： ``` Friday Monday ``` **數據範圍** - $\text{TL: 2 seconds}$ - $Q \le 3\,000$ | 子題 | 分數 | 限制 | |:----:|:---------------------:|:--------------:| | $1$ | $1\ 組 \times 1\ 分$ | $Q \le 5$ | | $2$ | $1\ 組 \times 2\ 分$ | $Q \le 10$ | | $3$ | $1\ 組 \times 4\ 分$ | $Q \le 20$ | | $4$ | $1\ 組 \times 8\ 分$ | $Q \le 2\,000$ | | $5$ | $1\ 組 \times 10\ 分$ | $Q \le 3\,000$ | :::spoiler 題解 by SorahISA $\qquad$ 雖然這題直接暴力是 $\mathcal{O}(3000 \times 10 \times 365)$，大約是 $10^7$ 也可以過，不過既然要看時間，那就有必要得到 $\mathcal{O}(1)$ 的做法。 $\qquad$ 我的作法是直接手動建表，建每年的元旦是星期幾，之後再判斷有沒有閏年。 $\qquad$ [Code by SorahISA](https://pastebin.com/TiHQ4dyj) :::  ### pF. 塗色問題 **題目敘述** 敘述簡略請見諒給 $N$，然後有 $N$ 層的 block，第 $i$ 層 $i$ 個，然後給每個 block 上色，不能重複（顏色編號 $1 \sim \frac{N(N+1)}{2}$）。接下來給 $M$ 組衝突的顏色，衝突的顏色不能放在相鄰的格子，問你第一層的格子放什麼顏色會使方案數最少，還有此時的方案數。如果有多個顏色，輸出編號最小的。 **數據範圍** - $\text{TL: 8 seconds}$ - $N \le 5$ - $0 \le M \le \frac{N(N+1)}{2}$ | 子題 | 分數 | 限制 | |:----:|:--------------------:|:---------------:| | $1$ | $1\ 組 \times 2\ 分$ | $N \le 2$ | | $2$ | $5\ 組 \times 3\ 分$ | $3 \le N \le 4$ | | $3$ | $2\ 組 \times 4\ 分$ | $N = 5$ | :::spoiler 題解 by SorahISA $\qquad$ 爆搜+剪枝 $\mathcal{O}\left(\left(\frac{N(N+1)}{2}-1\right)!\right)$ 可以過！ $\qquad$ 用 `next_permutation` 則會 TLE 拿到 $17$ 分 $\qquad$ 我的寫法可以被特定測資卡掉，應該有更好的解法？歡迎提供想法～ $\qquad$ [Code by SorahISA](https://pastebin.com/RuHeJbe2) :::  ## Rankings | 學校 姓名 | pA | pB | pC | pD | 上午場 | pE | pF | 下午場 | 總分 | |:------------------:|:----:|:----:|:----:|:----:|:------:|:----:|:----:|:------:|:-----:| | 花蓮高中 范釗維 | $25$ | $25$ | $25$ | $25$ | $100$ | $25$ | $25$ | $50$ | $150$ | | 宜蘭高中 黃允謙 | $25$ | $25$ | $25$ | $25$ | $100$ | $25$ | $23$ | $48$ | $148$ | | 花蓮高中 吳庭安 | $25$ | $25$ | $25$ | $25$ | $100$ | $25$ | $17$ | $42$ | $142$ | | 花蓮高中 林奕廷 | $25$ | $25$ | $25$ | $25$ | $100$ | $25$ | $2$ | $27$ | $127$ | | 台東高中 王景誠 | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | | 慧燈高中 林劭軒 | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | $?$ | | 佳作 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | | 宜蘭高中 朱偉哲 | $25$ | $25$ | $25$ | $15$ | $90$ | $25$ | $2$ | $27$ | $117$ |