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


shaogan10555015@gmail.com (少干)

School : No School
ID : 126019
IP address : [49.215.37.242]
Last Login :
2023-03-21 00:55:20
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [49.216.45.69] | Post Date : 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 (少干)

School : No School
ID : 126019
IP address : [49.215.37.242]
Last Login :
2023-03-21 00:55:20
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [49.216.45.69] | Post Date : 2022-04-17 18:52

 

由西格瑪公式推倒



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


linlincaleb@gmail.com (臨末之頌)

School : 新北市立板橋高級中學
ID : 132772
IP address : [203.64.161.123]
Last Login :
2024-07-29 10:02:49
f815. TOI_y21m4_a01遊戲升等 -- TOI練習賽2021年4月潛力組 | From: [111.248.166.32] | Post Date : 2022-04-18 06:37

 

由西格瑪公式推倒



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

 
ZeroJudge Forum