回『原創/不分類題庫』
b446. 史蒂芙的煩惱
標籤 : KD樹 分治 搜索結構 樹套樹 離線處理
通過比率 : 14人/19人 ( 74% ) [非即時]
評分方式：
Tolerant

最近更新 : 2015-08-07 10:33

內容

背景

動畫 遊戲人生《No Game No Life》中，史蒂芙 (Stephanie Dola) 常常被欺負，儘管她以學院第一畢業，對於遊戲一竅不通的她在這個世界常常被欺負。現在就交給你來幫幫她。

問題描述

兩個人輪流在一個大棋盤上下棋，每一步棋的得分根據這一步棋與最鄰近的敵方棋子的曼哈頓距離。

對於兩個點 $p, q$ 座標 $(p_x, p_y), (q_x, q_y)$，曼哈頓距離 (Manhattan distance) 為 $|p_x - q_x| + |p_y - q_y|$。

輸入說明

每組測資只有一筆，第一行一個整數 $N$，表示兩方輪流下 $N$ 步棋。接下來會有 $2N$ 行，奇數行為玩家史蒂芙下棋的座標，偶數行為玩家空下棋的座標。

  • $1 \le N \le 50000$
  • 棋座標 $(x, y)$，範圍 $0 \le x, y \le 32767$
  • 保證每一個座標最多只會有其中一方的棋子
輸出說明
除了先手的第一步，每一步都找到最鄰近敵方旗子的曼哈頓距離。
範例輸入 #1 
3
1 1
5 5
4 4
3 2
2 4
2 3
範例輸出 #1 
8
2
3
3
1
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <10M
提示 ：
  • 測資中，稠密、稀疏情況都有可能。
  • 範例輸入如下圖所示 史蒂芙 (A)、空 (B)
                                                                                                                              
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+   
 |A1|  |  |  |  |     |A1|  |  |  |  |     |A1|  |  |  |  |     |A1|  |  |  |  |     |A1|  |  |  |  |     |A1|  |  |  |  |   
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+   
 |  |  |  |  |  |     |  |  |  |  |  |     |  |  |  |  |  |     |  |  |  |  |  |     |  |  |  |A3|  |     |  |  |B3|A3|  |   
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+   
 |  |  |  |  |  | +-> |  |  |  |  |  | +-> |  |  |  |  |  | +-> |  |B2|  |  |  | +-> |  |B2|  |  |  | +-> |  |B2|  |  |  |   
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+   
 |  |  |  |  |  |     |  |  |  |  |  |     |  |  |  |A2|  |     |  |  |  |A2|  |     |  |  |  |A2|  |     |  |  |  |A2|  |   
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+   
 |  |  |  |  |  |     |  |  |  |  |B1|     |  |  |  |  |B1|     |  |  |  |  |B1|     |  |  |  |  |B1|     |  |  |  |  |B1|   
 +--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+
標籤:
KD樹 分治 搜索結構 樹套樹 離線處理
出處:
[管理者： morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」