# YTP 2023 部份題解 By abc864197532 --- ## 題目們 - 國中組初賽 p2 Bocchi and Mango Masks - 高中組初賽 p1 Nijika or Doritos? - 國中組決賽 p3 Eleven - 高中組決賽 p4 Yuna and Quests --- ### Bocchi and Mango Masks 給定 $n$ 個長方體 $A_i$ 與長方體 $B$，問有幾個長方體 $A_i$ 可以在經過旋轉或翻轉後被放在 $B$ 裡面。 $1 \leq n \leq 1000$ ---- - 長方體旋轉對應到的邊長組合只有 $3!$ 種 - $(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)$ - 硬寫的話把每種都判完就好了 ---- - 假設已經將長方體 $B$ 的三邊長排序好，那其實上面敘述的條件其實只有排序好的那個是重要的 - 枚舉一下 case 會發現其他條件符合的時候這個也會符合 ---- - 假設長方體 $B$ 的三邊長為 $L \leq W \leq H$，某個長方體 $A_i$ 的三邊長為 $l \leq w \leq h$。 - 則若 $l \leq L, h \leq W, w \leq H$，就代表 $l \leq L, w \leq h \leq W, w \leq h \leq H$。 - 其他情況也可以用類似的想法推出來。 ---- - 賽中多數人都是用後面的方法過的 - [標程](https://ideone.com/iZPBOI) --- ### Nijika or Doritos? 給定兩種三角形 $A, B$，$q$ 筆詢問某個三角形跟哪個全等或都沒有 $1 \leq q \leq 1000$ ---- - 國中數學：可以用 SSS 判斷兩三角形是否全等 - 將三角形的三邊長算出來，再判斷組成邊長的數字是否相同即可 ---- - 直接用浮點數存邊長會有浮點數誤差 - 點都是格子點 $\implies$ 邊長的平方一定是個整數 - 所以使用邊長平方作為比較依據就可以了 ---- - 浮點數誤差 ```cpp= #include <bits/stdc++.h> int main() { long long x = 98765432123456789; long long y = 98765432123456798; double a = sqrt(x), b = sqrt(y); if (a == b) { cout << "Yes\n"; } else { cout << "No\n"; } } ``` ---- - 少用 `std::pow` 函式 ```cpp= #include <bits/stdc++.h> int main() { long long a = 864197532; long long res1 = std::pow(a, 2); long long res2 = a * a; std::cout << res1 << '\n' << res2 << '\n'; } ``` ---- - 輸出 ```cpp= 746837374314891008 746837374314891024 ``` ---- - 很多人會 WA 的測資 ``` 0 0 0 1 1000000000 1000000000 0 7 0 8 1000000000 1000000000 1 0 7 1 7 1000000000 1000000000 ``` 需要比較： $\sqrt{1999999984000000050}$ 跟 $\sqrt{1999999984000000064}$ ---- - [標程](https://ideone.com/CBPAzR) --- ### Eleven 給定 $n$，輸出最大的數使得： - 每個數碼都非 $0$ - 數碼和為 $n$ - 可被 $11$ 整除 $1 \leq n \leq 10^5$ ---- - $11$ 倍數判別法 - $n$ 的奇數位數碼和減掉偶數位數碼和可以被 $11$ 整除 $\iff$ $n$ 可被 $11$ 整除 - 接著就來分一點 case ---- - $n$ 是偶數：範測告訴你 $n = 2$ 的答案，有沒有辦法推廣？ - 輸出 $n$ 個 $1$。 - 顯然他是最大的，而且根據前面所說他顯然可以被 $11$ 整除 ---- - $n$ 奇數：範測告訴你 $n = 3$ 無解，那有沒有其他無解的情況？ ---- - 令所需數字的奇數位數碼和為 $a$，偶數位為 $b$ - 由於 $n = a + b$ 為奇數，所以可以得知 $|a - b| \geq 11$。 - 若 $n < 11$，則顯然不可能 - 若 $n = 11$，則 $a$ 或 $b$ 有一項會 $= 0$，但因為滿足條件的數至少為兩位數所以不可能 ---- - $n = 13$ 有解嗎？ - $913$！ - 而剩下 $n > 13$ 的 case 會發現其實就只要在 $913$ 後面補 $n - 13$ 個 $1$ 即可 ---- 結論 - $n$ 偶數，輸出 $n$ 個 $1$ - $n$ 奇數且 $n \leq 11$，無解 - 否則輸出 $913$ 後面接 $n - 13$ 個 $1$ - [標程](https://ideone.com/NyPD6X) --- ### Yuna and Quests 座騎與服裝都分別有兩種，每次操作可以將座騎或服裝其中之一換成另一種。 請依序完成 $n$ 個條件，每個條件會對於座騎以及服裝，分別限制需要的種類，也可以沒有限制。問完成全部條件所需要花費的最少操作數。 $1 \leq n \leq 1000$ ---- #### 作法一 - 考慮 $dp[i][a][b]$ 代表已經完成前 $i$ 個條件，且目前座騎為第 $a$ 種服裝為第 $b$ 種，這樣情況下的最少操作數 - 轉移先判斷是否滿足條件，再枚舉進行的操作 - 總複雜度 $O(n)$，但有個 $2^4$ 的常數 ---- #### 作法二 - 觀察到服裝和座騎這兩種是互相獨立的，所以可以分開計算這兩種個別的答案貢獻，再把兩者加起來 - 只要會算服裝的答案即可 ---- - 觀察發現在「什麼服裝都可以」的任務不進行操作永遠是最優的，所以可以直接把那些任務移除掉 - 那之後就可以有很簡單的 greedy 策略：在需要換服裝的時候再進行操作就好 - 總複雜度為 $O(n)$。 ---- - [標程（作法一）](https://ideone.com/1KsjvL) - [標程（作法二）](https://ideone.com/4zDqWC) --- ### 結束 謝謝各位~