skip to main
|
skip to sidebar
Algorithm‧ICPC‧Programming
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}
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
網誌存檔
►
2012
(4)
►
5月
(2)
►
2月
(2)
▼
2011
(51)
►
7月
(3)
►
6月
(1)
►
4月
(11)
►
3月
(10)
▼
2月
(25)
Codeforces #51 D Geometrical Problem
Codeforces #6 E Exposition
SRM 498 DIV 1 Easy + Medium
Codeforces #60 C Mushroom Strife
Codeforces #7 D Palindrome Degree
Codeforces #57
Codeforces School Team Contest #1 H Multiplication...
Small Math puzzle
Codeforces #1 C Ancient Berland Circus
Codeforces #33 D Knights
Codeforces #55
Codeforces #15 C Industrial Nim
Codeforces #13 C Sequence
SRM 497 Div 1 Easy Permutation Signature
Codeforces #10 C Digital Roots
Codeforces #27 C Unordered Sequence
Codeforces #19 B Checkout Assistant
Codeforces #30 C Shooting Gallery
Codeforces #7 C Line
Codeforces #37 C Old Berland Language
Codeforces #46 C Disposition
Codeforces #51 C Pie or Die
Codeforces #28 B pSort
Codeforces #24 C Sequence of Points
Codeforces #33 C Wonderful Randomized Sum
►
1月
(1)
►
2010
(2)
►
5月
(2)
►
2009
(17)
►
12月
(1)
►
9月
(6)
►
8月
(1)
►
7月
(8)
►
5月
(1)
►
2008
(8)
►
8月
(1)
►
7月
(2)
►
3月
(3)
►
2月
(2)
關於我自己
Hackson
檢視我的完整簡介
沒有留言:
張貼留言