一碗酸梅湯 作品
第248章 需要對答案嗎?
預處理的方案很多，但各有利弊。
比如，在這道題中，如果使用線段樹來做預處理，需要維護三個值:區間內最小值、最大值、數的個數。
這種辦法有個缺點，當hi的值很大時，有可能會內存開銷過大，導致空間超限。
根據規定，程序可以使用的內存只有128兆，一旦使用的內存超出限制，則整道題0分。
為了解決這個問題，就需要進行離散化操作，平添難度。
江寒通過分析，綜合比較、權衡了一番後，選擇了比較保險的雙向鏈表模擬算法。
相比線段樹，雙向鏈表不需要離散化，但是細節比較多，調試起來會稍微麻煩一點。
江寒自然不怕這點麻煩，一個是他對雙向鏈表掌握得很好，二來……早上吃那麼多東西，就是為了用在這種地方的。
只要捨得全力開動腦力，編寫起這種複雜度的代碼來，只是小意思。
還剩下一個半小時，時間上是完全夠用的。
對輸入數據進行了預處理之後，接下來就可以尋求題目要求的解答了。
這一步，可以用“倍增法”進一步提速，這樣就可以保證，在很短的時間內算出答案，避免時間超限。
由於答案數字很大，這道題也要用高精度來處理一下。
但和第二題又有點不一樣，這道題的精度壓力，其實並沒有那麼離譜，完全可以嘗試採用longlong（對應著vs裡的int64）數據類型來解決。
如果為了萬無一失或者炫技，當然也可以再次手寫一個高精度算法。
但江寒經過分析、計算，認為longlong已經完全夠用，就沒費那個勁兒。
放在幾年前，在noip等各種編程比賽中，longlong還是禁止使用的數據類型，但從去年開始，noi官方終於放鬆了限制，明文允許使用了。
這樣一來，很多難題的編程複雜度，就被大大地削減了。
編寫完第三題的代碼，調試通過後，江寒又設計了一些數據去檢測，結果完全正確。
看看時間，還剩下半個小時。
這個時間自然也不能浪費，江寒將代碼整理了一番，清理掉調試數據，註釋掉不需要的輸出，刪除多餘的文件。
最後，再跑了一遍代碼，確認毫無問題後，又利用最後十分鐘，複查了一遍文件夾、源代碼、輸入輸出文件的命名，排除各種低級錯誤。
別說，還真讓江寒查出了一個問題，第1題的輸出文件名，打漏了一個字母。
應該是vigenere.out，結果打成了vigener.out。
比如，在這道題中，如果使用線段樹來做預處理，需要維護三個值:區間內最小值、最大值、數的個數。
這種辦法有個缺點，當hi的值很大時，有可能會內存開銷過大，導致空間超限。
根據規定，程序可以使用的內存只有128兆，一旦使用的內存超出限制，則整道題0分。
為了解決這個問題，就需要進行離散化操作，平添難度。
江寒通過分析，綜合比較、權衡了一番後，選擇了比較保險的雙向鏈表模擬算法。
相比線段樹，雙向鏈表不需要離散化，但是細節比較多，調試起來會稍微麻煩一點。
江寒自然不怕這點麻煩，一個是他對雙向鏈表掌握得很好，二來……早上吃那麼多東西，就是為了用在這種地方的。
只要捨得全力開動腦力，編寫起這種複雜度的代碼來，只是小意思。
還剩下一個半小時，時間上是完全夠用的。
對輸入數據進行了預處理之後，接下來就可以尋求題目要求的解答了。
這一步，可以用“倍增法”進一步提速，這樣就可以保證，在很短的時間內算出答案，避免時間超限。
由於答案數字很大，這道題也要用高精度來處理一下。
但和第二題又有點不一樣，這道題的精度壓力，其實並沒有那麼離譜，完全可以嘗試採用longlong（對應著vs裡的int64）數據類型來解決。
如果為了萬無一失或者炫技，當然也可以再次手寫一個高精度算法。
但江寒經過分析、計算，認為longlong已經完全夠用，就沒費那個勁兒。
放在幾年前，在noip等各種編程比賽中，longlong還是禁止使用的數據類型，但從去年開始，noi官方終於放鬆了限制，明文允許使用了。
這樣一來，很多難題的編程複雜度，就被大大地削減了。
編寫完第三題的代碼，調試通過後，江寒又設計了一些數據去檢測，結果完全正確。
看看時間，還剩下半個小時。
這個時間自然也不能浪費，江寒將代碼整理了一番，清理掉調試數據，註釋掉不需要的輸出，刪除多餘的文件。
最後，再跑了一遍代碼，確認毫無問題後，又利用最後十分鐘，複查了一遍文件夾、源代碼、輸入輸出文件的命名，排除各種低級錯誤。
別說，還真讓江寒查出了一個問題，第1題的輸出文件名，打漏了一個字母。
應該是vigenere.out，結果打成了vigener.out。