看板 [ Prob_Solve ]
討論串[問題] ZeroJudge-c216
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] ZeroJudge-c216
推噓1(1推 0噓 0→)留言1則，0人參與, 5年前最新作者fatcat8127 (胖胖貓)時間5年前 (2019/04/02 17:45), 編輯資訊
0
0
3
內容預覽:
如題，附上題目連結(https://zerojudge.tw/ShowProblem?problemid=c216). 這題是關於線段樹的操作，但是奇妙的是題目的區段更新是整體更新. (感覺有貓膩但不知道怎麼利用)，以下是兩個想法但都會出現TLE的情況。. 每個節點分別紀錄區段內的長度總和和『容忍度
(還有284個字)
#2
Re: [問題] ZeroJudge-c216
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者GYLin (Lynx)時間5年前 (2019/04/02 20:45), 編輯資訊
1
0
0
內容預覽:
大致策略:. 1. 把途中所有累積加值都模100000, 原因很明顯. 2. 當需要計算Sum[L,R]時, 其值為"不考慮爆掉的原本加總"扣掉100000*(區間內爆掉人數). 爆掉人數為: 區間內的Ai個數, 其值加上目前累積加值會超過100000的人們. 要計算爆掉人數, 只要維護一個 Map
(還有112個字)
#3
Re: [問題] ZeroJudge-c216
推噓8(8推 0噓 11→)留言19則，0人參與, 5年前最新作者stimim (qqaa)時間5年前 (2019/04/02 23:17), 5年前編輯資訊
0
0
0
內容預覽:
另一種可以 online 的作法(不用預處理詢問). 在每次的詢問，. 假設不會爆掉，我們只要知道原始的 aL + ... + aR 再加上 K * (R - L + 1) 就是. 答案。這個部份只要先算出原始 a_i 的前綴和就可以做到。. 而每爆掉一個，答案就需要減掉 10^5，. 因此我們想知
(還有586個字)
首頁
上一頁
1
下一頁
尾頁