从今天开始写题解吧,这样好督促自己做题,也可以让自己知道哪些题还不会。
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 (待补充)