#38544: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [140.114.216.99]
最後登入時間 :
2024-10-27 14:56:56
a300. NOIP2011 Day1.2.选择客栈 -- NOIP2011提高组Day1第二题 | From: [223.139.70.124] | 發表日期 : 2023-12-05 08:00

我的複雜度 O(nlogn)

應該可以用單調對列優化我的作法變成 O(n)   吧

 

 

枚舉起點,二分搜從起點開始第一個小於P的位置(在 sparse table 上二分搜),再開一個vector紀錄每一個顏色出現過哪些位置。

再透過一次二分搜計算比第一個小於P的位置的後面有幾個跟起點顏色相同的數量即可(這一步應該也可以壓成O(1))

 
ZeroJudge Forum