第二部分解題報告

1、 解題華東師范大學第二附屬中學【時空限制】每個測試點時限 秒，空間限制無。【問題描述】有 棵樹從 到 標號?，F(xiàn)要把這些樹種在一條直線上，第 棵樹的種植位置 如下確定： ； 。每棵樹種植的費用，是所有標號比它小的樹與它的距離之和。計算各棵樹費用之積，模?！緮?shù)據(jù)規(guī)模和約定】N,L200000; 【試題】如果樸素地解決此問題，時間復雜度將為 ，這是不能接受的。必須降低每次計算費用的代價。注意到第 棵樹的費用，嘗試將絕對值拆開，則有從而容易發(fā)現(xiàn)，只需要一種數(shù)據(jù)結構，能夠查詢一段區(qū)域內(nèi)的數(shù)據(jù)個數(shù)及其和即可，這可以用線段樹、樹狀數(shù)組、平衡二叉查找樹等實現(xiàn)。具體地，以線段樹為例。按標號從小到大計算樹的費用。

2、計算樹 的費用時，分別查詢兩側的樹的個數(shù)及距離和，計算得出費用。最后將 線段樹，相關值。【算法描述】建立線段樹。按標號從小到大計算樹的費用。計算樹 的費用時，首先查詢 左側所有樹的個數(shù) 及位置之和 ，則 即為樹 左側標號比 小的樹到樹 的距離之后。同理求得 為右側距離和，相加即得樹 費用。然后將 線段樹，相關值。此算法每次查詢和每次的時間復雜度均為 ，故總時間復雜度為 ?！酒渌惴ā勘绢}還有一些算法，通過讓數(shù)據(jù)結構不同的值來解決問題，例如線段樹中結點區(qū)間內(nèi)所有點到左、右端點距離之和等等。這些算法和上述算法的本質(zhì)相同，此處不再贅述?！緦崿F(xiàn)情況】實現(xiàn)情況【感謝】感謝 在 er上提供的題解?！靖戒洝?/p>

3、原題Problem SementThere are N trees numbered 0 to N-1, and you must plant them along a straight line. Tree i will be planted atcoordinate Xi, where X is constructed using the following recursive definition:X0 = X0 MOD LXi = (Xi-1*A+B) MOD L (notet Xi-1*A+B may overflow a 32-biteger)The price of planti

4、ng tree i is the sum of the distanbetn tree i and each tree numbered lessn i.Calculate the product of the pri1,000,000,007.of all the trees (except tree 0), and return this number moduloDefinitionClass:ProductOfPriMethod:productParameters:,Returns:Method signature:product(N,L,X0,A,B)(be sure your me

5、thod is public)Constras-N will be betn 2 and 200,000, inclusive.-L will be betn 1 and 200,000, inclusive.-X0,A,B will each be betn 0 and 1,000,000,000, inclusive.Exles0)510311Returns: 180The trees are planted atitions: 3, 4, 5, 6, 7. Their priare (starting from tree 1): 1, 3, 6, 10. Theproduct of priis 1 * 3 * 6 * 10 = 180.1)320523Returns: 642)421171Returns: 30873)1010043711Returns: 5918607674)5200000999999999123456789987654321Returns: 499739175This problem sement is the exclusive and proprietary property of TopCoder, Inc.Any unauthorized use or reproduction of this information witho