# 2025/03/30 Toj Theme Contest 001 題解 ## pA **首殺 : paul** :::success 簡單來說就是 1. 把東西塞進去 2. 把東西拿出來 (假如不存在則不理) 3. 詢問目前最多的東西 (假如有很多個，輸出最小的) ::: :::spoiler **滿分解** 用 set + map 小心實作即可 ::: bonus: ```cpp= #define int long long ``` 被卡CE 但出題者表示: 我都沒有在#define int long long 的習慣 沒驗到不怪我 ╮(╯-╰)╭ ## pB **首殺 : 雷霆戰魂** :::success 簡單來說就是 1. 把東西丟進去queue後面 2. 把queue最前面的那個拔掉 3. 問queue裡面最大值是多少 ::: :::spoiler 子任務2 $1 \le Q \le 10^3$ 隨便暴力做應該都有 ::: :::spoiler 子任務3 $X \in \{1, 3\}$ 沒有把東西拔掉的話，題目就變簡單了 1. 把東西丟進去 2. 詢問當前最大值 ::: :::spoiler 子任務4 $1 \le Q \le 5 \cdot 10^5$ 用multiset小心實作 ::: :::spoiler **滿分解** 發現multiset被卡log 很不爽，所以要想一個接近線性的解法 有一個經典技巧 : max_in_queue 剛好可以達成這件事: 想像queue 被拆成 stack1, stack2 東西塞進去的時候，丟到stack1 詢問的時候先看stack2 有沒有東西 假如沒有就把所有在stack1的東西丟過去stack2 時間複雜度均攤下來是 O(N) 然後小心實作即可 ::: bonus: 被一大堆非官解期待的解打爛: 1. priority_queue + unordered_map 2. deque<pair<int, int> > 單調對列實作 (出題者覺得這個很讚) ## pC **首殺 : paul** :::success 簡單來說就是 N個人圍成一環 A人會殺掉下一個人 B人會殺掉上一個人 C人不會做事 ::: :::spoiler 子任務 2 $S_i \in \{A\}$ 經典約瑟夫問題，且範圍不大，可以用模擬的方式過 ~~你想秀一下數學解也可以~~ ::: :::spoiler 子任務 3 $S_i \in \{B\}$ 跟子任務 2 一樣，將環的順序反向即可 ::: :::spoiler 子任務 4 $1 \le N \le 10^4$ 範圍小，簡單的模擬也可以過 ::: :::spoiler **滿分解** 發現暴力模擬會TLE 所以我們可以仔細觀察 會發現 $C$ 種人根本躺贏狗，輪到他的時候，他只會躺平 所以假如環上有一列全都是 $C$ 的話，複雜度超級高!!! 所以我們可以考慮將所有排在一起的 $C$ 人縮點 並使用list當作實作工具，仔細維護 $C$ 人群的左右界即可 ::: bonus: 這題是從2024 ISSC的題目幹下來的 所以charhao沒首殺要檢討 ## pD **首殺 : 羨慕秉宏有TOI的第N天** :::success 簡單來說就是 $N$ 點，$M$種顏色，$C$是個肺霧 $Q$ 次詢問 每次給 $A$ $B$ 假如$A$ $B$ 中建邊後可以用不同顏色把整張圖的節點塗上顏色 且有連通的相鄰點不相同顏色 則建邊，否則將答案加上 $C$ ::: :::spoiler 子任務2 $1 \le Q \le 10^2$ 單純暴力下去，每次隨便檢查 理論上會過 ::: :::spoiler 子任務3 $1 \le Q \le 10^3$ 聰明點暴力，會發現每次建邊要檢查的只有那兩個還沒接在一起的連通塊 但這樣還是大機率會TLE 除非你常數壓到超級小，不然就是**你超會檢查** ::: :::spoiler 子任務4 $2 \le N \le 5 \cdot 10^2, 1 \le Q \le 10^4$ 只有 $M = 2$ 的case 那麼簡單觀察就會發現 題目變成了二分圖判斷的題目 所以每次dfs下去就可以簡單通過此題 ::: :::spoiler **滿分解** 繼承子任務4的觀察 但二分圖判斷的方式太沒有效率了 所以可以透過經典技巧，DSU來判二分圖 輕鬆拿到本題滿分! ::: bonus: 本來要出四色原理，結果題目限制根本沒限制到 燒雞 然後我正解寫對，暴力解寫錯，超笨