---
# System prepended metadata

title: ABC 418
tags: [題解, ABC]

---

# 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)
:::