2025/03/30 Toj Theme Contest 001 題解

pA

首殺 : paul

簡單來說就是

把東西塞進去
把東西拿出來 (假如不存在則不理)
詢問目前最多的東西 (假如有很多個，輸出最小的)

滿分解

用 set + map 小心實作即可

bonus:


#define int long long

被卡CE
但出題者表示:
我都沒有在#define int long long 的習慣
沒驗到不怪我 ╮(╯-╰)╭

pB

首殺 : 雷霆戰魂

簡單來說就是

把東西丟進去queue後面
把queue最前面的那個拔掉
問queue裡面最大值是多少

子任務2

1 \leq Q \leq 10^{3}

隨便暴力做應該都有

子任務3

X \in {1, 3}

沒有把東西拔掉的話，題目就變簡單了

把東西丟進去
詢問當前最大值

子任務4

1 \leq Q \leq 5 \cdot 10^{5}

用multiset小心實作

滿分解

發現multiset被卡log
很不爽，所以要想一個接近線性的解法

有一個經典技巧 : max_in_queue 剛好可以達成這件事:

想像queue 被拆成 stack1, stack2
東西塞進去的時候，丟到stack1
詢問的時候先看stack2 有沒有東西
假如沒有就把所有在stack1的東西丟過去stack2
時間複雜度均攤下來是 O(N)

然後小心實作即可

bonus:

被一大堆非官解期待的解打爛:

priority_queue + unordered_map
deque<pair<int, int> > 單調對列實作 (出題者覺得這個很讚)

pC

首殺 : paul

簡單來說就是
N個人圍成一環
A人會殺掉下一個人
B人會殺掉上一個人
C人不會做事

子任務 2

S_{i} \in {A}

經典約瑟夫問題，且範圍不大，可以用模擬的方式過
~~你想秀一下數學解也可以~~

子任務 3

S_{i} \in {B}

跟子任務 2 一樣，將環的順序反向即可

子任務 4

1 \leq N \leq 10^{4}

範圍小，簡單的模擬也可以過

滿分解

發現暴力模擬會TLE
所以我們可以仔細觀察
會發現

C

種人根本躺贏狗，輪到他的時候，他只會躺平
所以假如環上有一列全都是

C

的話，複雜度超級高!!!

所以我們可以考慮將所有排在一起的

C

人縮點
並使用list當作實作工具，仔細維護

C

人群的左右界即可

bonus:

這題是從2024 ISSC的題目幹下來的
所以charhao沒首殺要檢討

pD

首殺 : 羨慕秉宏有TOI的第N天

簡單來說就是

N

點，

M

種顏色，

C

是個肺霧

Q

次詢問
每次給

A

B

假如

A

B

中建邊後可以用不同顏色把整張圖的節點塗上顏色
且有連通的相鄰點不相同顏色
則建邊，否則將答案加上

C

子任務2

1 \leq Q \leq 10^{2}

單純暴力下去，每次隨便檢查
理論上會過

子任務3

1 \leq Q \leq 10^{3}

聰明點暴力，會發現每次建邊要檢查的只有那兩個還沒接在一起的連通塊
但這樣還是大機率會TLE
除非你常數壓到超級小，不然就是你超會檢查

子任務4

2 \leq N \leq 5 \cdot 10^{2}, 1 \leq Q \leq 10^{4}

只有

M = 2

的case

那麼簡單觀察就會發現題目變成了二分圖判斷的題目
所以每次dfs下去就可以簡單通過此題

滿分解

繼承子任務4的觀察
但二分圖判斷的方式太沒有效率了
所以可以透過經典技巧，DSU來判二分圖
輕鬆拿到本題滿分!

bonus:

本來要出四色原理，結果題目限制根本沒限制到
燒雞

然後我正解寫對，暴力解寫錯，超笨