發表新討論
#13734: 換個方法


054025 (東翰)

學校 : 高雄市立高雄高級中學
編號 : 63295
來源 : [101.9.112.182]
最後登入時間 ：
2021-07-17 17:36:17
c310. PE:蘋果之塔 -- 2017高雄市高師大附中資訊學科能力 | From: [114.38.241.132] | 發表日期 : 2018-04-15 22:44

本來是做詢問的時候跑dfs結果超時

改成增減蘋果的時候跑dfs就過ㄌ

 
#16059: Re:換個方法


k034006 (Sine Wu)

學校 : 高雄市立高雄高級中學
編號 : 46921
來源 : [180.217.135.99]
最後登入時間 ：
2024-09-07 23:27:34
c310. PE:蘋果之塔 -- 2017高雄市高師大附中資訊學科能力 | From: [219.84.57.99] | 發表日期 : 2018-11-16 00:21

本來是做詢問的時候跑dfs結果超時

改成增減蘋果的時候跑dfs就過ㄌ



真的喔www

我以為要寫個線段樹什麼的(?

 
#16063: Re:換個方法


OwO310659 (OwO)

學校 : 新北市立板橋高級中學
編號 : 58647
來源 : [118.150.111.60]
最後登入時間 ：
2024-04-25 01:16:40
c310. PE:蘋果之塔 -- 2017高雄市高師大附中資訊學科能力 | From: [106.105.27.148] | 發表日期 : 2018-11-16 16:56

那應該是本題的測資沒有出得很好,

理論上當 詢問 和 修改 的操作數量差不多時,
不管是 詢問的時候跑DFS 或 修改的時候跑DFS 其所需時間應該也要差不多才對,
其所有操作的時間複雜度為 O(QN)

若使用樓上所說的線段樹來 詢問/修改 ,
其所有操作的時間複雜度只需 O(QlgN)
這樣的時間複雜度才會是合理的~~~  OwO

 
ZeroJudge Forum