這裡好像很多人在比，所以想問問看 解法，那我先就我知道的拋磚引玉吧！ 題目在： http://code.google.com/codejam/contest 防雷頁 1a.Greedy 最大配最小就對了。 我也不知道怎麼對的，有誰要說明一下嗎？ 時間複雜度：O(n lg n) (sorting) 1b.無法分類呀orz 看似SAT問題，結果都不敢去做。 但是其實他說每個人最多一個melted milk. 也就是說，決定melted milk要不要放是看人， 在這裡應該可以看出端倪是要建一個 人-牛奶的table ，記得某個人要哪些牛奶！ 另外要記得每一個人有沒有被satisfy Case 這個人不用melted milk就可以satisfy: 沒問題！ Case 這個人不用melted milk沒有satisfy: 那無論如何都要給他melted milk， 由於只有一個melted milk所以選擇唯一。 因此就每次都看過所有人，直到沒有人可以被多satisfy。 由於兩種Case的決定都是deterministic，所以掃一次至少 多satisfy一個人，而且是花人數的時間。 因此，時間複雜度是O(牛奶數*人數^2) 1c.Linear Algebra(?) 聽說是把1當作I,去解 (X-3)^2 = 5 的矩陣X。 就可以把(3+sqrt(5))^n 跟那個矩陣做mapping... 然後就可以divide and conquer乘次方. 但是最後面要怎樣轉回來不是很理解... O(n) (n是數字的encoding長度) 2a:Ring 窮舉by x,y 座標 用 3*(x mod 3)+(y mod 3) map到 {0,1,2 ... 9} 這樣的 ring 然後對ring中任取3個元素a,b,c with constraint a<=b<=c做窮舉，然後再用排列組合公式求解。 我的解法時間複雜度是O(n) (讀入input) 2b:Disjoint Set 把所有質數在10^6以下窮舉出來， 然後用disjoint set演算法。(就是超強神Tarjan大大的 接近linear演算法)跑一次整個範圍的數做merge. 要不要merge就看看是否有共同質因數大於P就好。 我的解法時間複雜度是O((nlog*n) * p(1000000)) p(1000000) 是在 1000000以下的質數 2c:Joseph題 環狀殺人問題，從1開始放牌，能放的先放就會對。 因為大的不會插隊去match小的。 時間複雜度我不會分析.... 3a:greedy 最小的儘量全部塞一起。 目前還沒想到怎樣證orz... 時間複雜度：O(n lg n) (sorting) 3b:Divide and conquer and remember used stated (DP) 我們只在意餘數，所以其實在一個{1 .. 2*3*5*7}的ring就足以 model我們看到的所有數字。 State有strlen*2*3*5*7個，因為斷一次數字，後面要什麼數字， 只跟前面分別對2,3,5,7的餘數有關，跟真正加減起來的數字無關。 然後就對數字的每個數字之間都斷斷看，每次斷都加減看看就好。 時間複雜度： O(n) 因為2,3,5,7是constant. 3c. 不會.... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.99.4.64 ※ 編輯: scan33scan33 來自: 122.99.4.64 (07/27 23:56) ※ 編輯: scan33scan33 來自: 122.99.4.64 (07/28 09:27)