PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ACM 11084 11127 (TLE)

看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間13年前 (2011/09/03 11:02)推噓2(2推 0噓 0→)

留言2則, 1人參與討論串2/2 (看更多)

試了一下,純 O(|s|!)枚舉仍然會TLE,就換了個方式枚舉可過想法是,如果我們用輸入的一部分湊出了餘數r,那必須用輸入的另一部分湊出餘數 d-r. 所以說,我們把輸入拆分成前 |s|/2 個和後 |s|/2 個分別排列,使得排列的花費降為 (|s|/2)! 之後,再把兩邊分別組合起來;為了方便,我們先枚舉前 |s|/2 個字所要佔用的位置,這樣後 |s|/2 可以用的位置就確定了. 枚舉位置+排列後,對前後分別記下算出餘數r(0≦r＜d),然後算出被d整除的方式枚舉位置的花費則是 C(n,n/2),極限測資C(10,5)≦252;所以這樣做時間複雜度為 O( C(n,n/2)[d+(n/2)!] )... 傳上去是跑 0.120s 舉個例子, s=12345, d=2, 前半取 2 個, 後半取 3 個 12 21 餘0的有12000,21000共兩個餘1的0個 345 354 435 453 534 543 餘0的354,534兩個餘1的345,435,453,543共四個所以位子這樣分配時,mod d餘零的共 2*2 + 0*4 = 4個 1 2 2 1 餘0的有10200,20100共兩個餘1的零個 3 45 3 54 4 35 4 53 5 34 5 43 餘0的有3054,5034兩個餘1的3045,4035,4053,5043共4個 ...剩下類推附上寫得爛爛的程式碼 http://pastie.org/2474232 我想這樣做在這題能跑這麼快是因為d不會全部都是10,000... 而這種題目讓人很想狀態壓縮 DP (狀態:[哪些用了哪些還沒][餘數]) ,不過枚舉能過就算了... ※ 引述《singlovesong (~"~)》之銘言： : 題目: : 11084 http://luckycat.kshs.kh.edu.tw/homework/q11084.htm : Code: : 11084: http://codepad.org/c7XwSbg4 : 這兩題都沒有什麼特別的想法直接暴搜 : 果然都TLE : 想請問這兩題該用什麼解法才可以不超時的呢？ : 上網google 了好一陣子都沒什麼結果... : code寫的很醜只希望強者能指點一下算法^^" -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.33.236 ※ 編輯: suhorng 來自: 61.217.33.236 (09/03 11:03)