## 2525/06/08 ## 高一生程式設計排名賽 ## 題解 --- ### 預測難度 ---- Paul : C < E < F < D < I < A < B < G < H Charhao : E < C < F < I < D < G < B < A < H Blame : C < E < F < D < I < G < B = A < H ---- ### 實際難度 (AC人數比較) ---- pC < pE < pG < pF < pB < pA < pH --- ### pA -寶石礦坑 ---- Fun fact 王🉐宏是某個人的化名 他是地科大師 那張照片上面的人根本不是他是charhao ---- 題目:給兩個凸多邊形，問有沒有重疊的部分 ---- 可以把會重疊的情況分成兩種: 1. 兩個多邊形的邊有重疊 2. 某一個多邊形完全被另一個多邊形包覆 ---- solution by Paul 針對第一個，就直接暴力判有沒有認兩條邊重疊 針對第二個，判有沒有其中一個多邊形的每個點都在另一個圖形裡面(打射線出去)~~然後被卡常~~ ---- solution by blame 針對第一個，就直接暴力判有沒有認兩條邊重疊 針對第二個，用向量外積判斷方向性 ---- Bonus 這題可以做到$nlogn$時間複雜度(minkowski sum) 去問 Brinton --- ### pB - 我得自升級 ---- Fun fact 我獨自升級是一個很好看的漫畫 ---- solution by blame 做一次manacher 對所有詢問離線回答 用BIT + 掃描線 ---- solution by brinton 這題是水題 做dp就行了 ---- bonus 假如每一筆詢問 $K$ 可變 又可以怎麼做呢？ --- ### pC - 向左走向右走 ---- Fun fact 題目名稱這是一本繪本/電影 然後這題長得有點線段樹的影子 ---- 妥妥的簽到題 沒啥好講的 --- ### pD - 寶箱怪阿祖北京烤鴨 ---- Fun fact 這是唯一一題沒有 fun fact 的題目 ---- solution by charhao 掃描線+[這個技巧](https://cses.fi/problemset/task/1076) ---- bonus 假如每個詢問都給你K K可變 那要怎麼做呢？ --- ### pE - 很得的問題 ---- Fun fact 1.原本這題要出最大子區間和，不過因為一直被嗆，所以就在比賽前天緊急換掉 2.這題原本叫簡短的問題，但是因為 $\oplus$ 和 :ideograph_advantage: 很像所以就改了 ---- solution by charhao 對每個數字計算他被所有區間涵蓋到幾次 如果是奇數次就代表他對答案有貢獻 否則就沒有 --- ### pF - 三天之後 ---- Fun fact 原本打算叫做三天三夜但是跟圖片有點不搭 這題原本的解法被打爛 ---- solution by Blame and Charhao 先對兩個數字暴力枚舉之後建表(map) 每次詢問的時候暴力枚舉第三個數字並查表 複雜度 $O(n^{2/3}+qn^{1/3}log(n^{2/3}))$ map、unordered_map會被卡常 要用離散化 --- ### pG - 數剖題 ---- Fun fact 1. 題目其實是想騙你做樹鍊剖分 2. 我畫的畫真好看 ---- solution by blame 仔細觀察會發現 兩點距離 > 63 因為鴿籠原理，所以一定是 YES 其他的用LCA跳一跳就好了 好吧 其實不用鴿籠原理也可以用LCA跳跳解 (我沒卡那個常數ㄏㄏ) --- ### pH - 速通麥塊 ---- Fun fact 1. 這題本來出出來是要拿來卡 Brinton 的 結果他沒有來 所以變成一題好難的防破台題 2. 題目一開始的圖是我畫的Dream ---- solution by blame Max Plus Matrix 也可以說是廣義矩陣乘法 也就是把矩陣的×改成+,+改成max 然後就一般的矩陣轉移 然後多筆區間詢問跟單點修改，線段樹！ ---- Bonus 假如 DP 式中的max plus 操作改成其他的 有哪些也可以用相同解法? --- ### pI - 電機社的殞落 ---- Fun fact 題敘是brinton想的，如果有電機社的人請去找他 ---- solution by charhao 把刪點變成加點，每次新增一個點時，就用這個點當作floyed-warshell的中間點做轉移 所以複雜度會是 $O(N^3)$ --- Last Fun Fact ---- 詢問大賽 9題裡有7題是Q筆詢問 --- ## 諧咖 ---- pB 線上賽 GPT 做出來了 沒寫出來的人 應該要檢討 ---- wonderhoi 花了一個小時幫我們驗證了 pF unordered_map 會被卡常 哈哈 ---- 有人 pG 刻 HLD  哈哈 考古 但他AC了 ㄏㄏ ---- 現場教學 string  ---- 教學過於認真，需要換頁才能裝得下  ---- 線上組 pF checker 爛掉，讓人AC了 及時修正，問題不大 ouob ---- 有人藏 code 藏到燒雞 哈哈 ---- ams 哈哈 ```cpp= sort(ans.begin(), ams.end()); ``` ---- 想再玩一次 "猜" ```cpp= #include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ if(time(0) & 1) puts("Yes"); else puts("No"); } ```