2011年2月12日 星期六

Codeforces #33 D Knights

題意﹕給了N個人,M個圓,K次詢間﹕問第a人到第b人,最少需要穿過多少次圓的邊界?假設人都不會站在圓的邊界上(但人的位置可以重覆)

這題和某場Topcoder SRM Div 1 Easy 完全一樣,那次炒得很慘,因此對簡單的做法尤其深刻。

設V[x][y]表示第x人是否包含在第y圓之內。對於每次詢問a, b答案則是很容易的用容斥原理算出﹕
Answer = Sum{V[a][i]+V[b][i] - 2(V[a][i] && V[b][i]): 1 <= i <= M}

沒有留言: