發表新討論
#29978: 比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!


shaogan10555015@gmail.com (少干)

學校 : 不指定學校
編號 : 126019
來源 : [49.215.37.242]
最後登入時間 ：
2023-03-21 00:55:20
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [49.216.45.69] | 發表日期 : 2022-04-17 18:49

a[]存角色等級

a[]小到大排序

sa[]存前綴和

sa2[]存平方前綴和(sa2[1]=a[0]^2+a[1]^2)

 

二分搜找U

對於每次遞迴

idx為a[]中第一個小於等於U的引索 或 n-1

《O(1)求cost》

cost=(idx+1)*U*U-2*U*sa[idx]+sa2[idx]

 

 
#29979: Re:比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!


shaogan10555015@gmail.com (少干)

學校 : 不指定學校
編號 : 126019
來源 : [49.215.37.242]
最後登入時間 ：
2023-03-21 00:55:20
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [49.216.45.69] | 發表日期 : 2022-04-17 18:52

 

由西格瑪公式推倒



 
#29982: Re:比解答投影片更快的O(logn^2) 解找cost只要O(1)!!!


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [111.248.166.32] | 發表日期 : 2022-04-18 06:37

 

由西格瑪公式推倒



我賽中是這樣寫的，但似乎會被卡，我subtask 1跟3(70分)有拿到，但subtask 2(30分)WA，我也不知道是甚麼測茲卡我，特判一下就被我拿滿囉(N<=100就爆搜)

 
ZeroJudge Forum