#15760: 範例測資的第4個查詢為何是 206?
#15763: Re:範例測資的第4個查詢為何是 206?
c535. 動態曼哈頓最短距離
| From: [106.105.27.148] |
發表日期
:
2018-10-27 16:36
注意在輸入說明有說到「在做任何操作之前，請先執行 x = (last_ans + x) % 10^8 + 1, y = (last_ans + y) % 10^8 + 1」,
所以在執行第一次 1 1 1 時, 實際上所加入的點是 ((0+1) %10^8+1, (0+1)%10^8+1) = (2, 2) (此時S={(2,2)})
而執行第二次 1 1 1 時, 實際上所加入的點是 ((2+1) %10^8+1, (2+1)%10^8+1) = (4, 4) (此時S={(2,2), (4,4)})
故在查詢 2 100 100 時, 實際上查詢的點是 ((6+100) %10^8+1, (6+100)%10^8+1) = (107, 107) (此時S={(2,2), (4,4)})
所以答案為: min(|107-2|+|107-2|, |107-4|+|107-4|) = min(210, 206) = 206
以上希望有幫助到你~ OwO
ZeroJudge Forum