这里好像很多人在比，所以想问问看 解法，那我先就我知道的抛砖引玉吧！ 题目在： 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)