# AtCoder Beginner Contest 418 Unofficial Editorial ~~為了減少製作成本~~，以下不會幫你翻譯題目，也不會有實作的 code (因為我覺得要自己想過然後用自己的方式實做出來比較好，不要直接抄)。 如果想看 code ，可以去 submission 找，應該有更多實作比我好看的。 然後為什麼這次 F 的難度爆炸難啊 (;°;ω;°;) ### A ( ･ ิω ･ ิ) ### B :::spoiler 觀察 1 因為字串的長度很短，所以直接枚舉端點然後直接算就好了 (^^з^^)-☆ ::: ### C :::spoiler 我是邪惡的 dealer 假設現在難度是 $b$，我是邪惡的 dealer，那我會給你||所有數量小於 $b$ 的茶包，再加上其他數量大於等於 $b$ 的茶包每種給你 $b-1$ 個，這樣你就湊不出來了哈哈哈|| 所以要確保打敗我，就必須拿上面算出來的數量 $+1$ ::: :::spoiler 實作 可以先 `sort` 再用 `lower_bound` ::: :::spoiler 複雜度 $O(NlogN)$ ::: ### D :::spoiler 觀察 1 兩個 1 可以變成一個 1，所以不管有幾個 1 都可以變成一個 1，所以 1 不重要 兩個 0 可以變成一個 1，所以 0 要有偶數個才能變成一個 1 ::: :::spoiler 實作 記錄 0 的個數的前綴和，若現在有奇數個 0，那答案就要加上之前也是奇數個 0 的那些位置，偶數則反之 ::: :::spoiler 複雜度 $O(N)$ ::: ### E :::spoiler 注意 這題會把平行四邊形也視為梯形喔 ::: :::spoiler 觀察 1 梯形有什麼性質？||會有兩條邊平行|| $N \leq 2000$ 所以可以枚舉兩點組成一個線段，然後用 `map` 之類的東西統計平行的線段 像是可以在 `map` 裡紀錄斜率 $dx$ 和 $dy$，注意要約分、正負號、水平線和鉛直線要怎麼紀錄（細節有點多呢 ::: :::spoiler 觀察 2 平行四邊形會被算到兩次！因為它有兩組平行的邊！ 但是平行四邊形有個性質：||兩個對角線交點是平行四邊形中心|| 所以可以順便在枚舉邊的時候順便紀錄這個中心，之後看每個中心被算了幾次，若有個中心被算了 $n$ 次，代表可以組成 $\frac{n(n-1)}{2}$ 個平行四邊形，要扣掉 ::: :::spoiler 複雜度 $O(N^2logN)$ 小心 `map` 可能會 `TLE` ::: :::spoiler TLE (⚲□⚲) 不要用那麼多 `map` 記錄中心的時候可以用 `vector`，之後再 `sort` 然後用雙指針找一個中心被算到幾次 也可以去 submission 看看其他人怎麼做的 (っ'ヮ'c) :::