discover

SEERC 2009 解题记录(不完全,待补充)

从今天开始写题解吧,这样好督促自己做题,也可以让自己知道哪些题还不会。
A.RSA Factorization 
 根据:  |q - kp| <= 10^5.
得到  |q^2 - k*n| <= 10^5 *q.
     => (q - 10^5)*q  <=  k*n  <=  (q + 10^5)*q.
     => q-10^5 <=  sqrt(k*n)  <= q + 10^5 .
     于是在sqrt(k*n) 的附近搜索就可以了,搜索次数不会超过 2*10^5次。

B.Hard-working Student
水题,直接模拟就好了,注意每个语句起始点是 v[index1],不是index1.
C.System Engineer
水题,二分图的匹配。
D.Cycles of Lanes. 水题。
E.Multiprocessor Scheduling(待补充)
F.Maze Stretching 水题
G.Software Industry Revolution DP,用滚动数组,状态表示和转移都是很显然的。 
H.The Lucky Numbers (待补充)
I.The Robbery 居然是个搜索,剪枝很犀利
J.The Computer Game (待补充)
K.The Bad Number (待补充)



posted on 2011-11-01 16:35 discover 阅读(140) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2026年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿

文章档案

搜索

最新评论