※ 引述《sophialiege.bbs@ptt.cc (got my nerve)》之銘言：
: sketch for each problem:
: [1]
: species (by Jingyue Wu):
: given n points in d-dimentional space.
: For two points A and B, define a function
: f(A,B) = |A[1]-B[1]|+|A[2]-B[2]|+...+|A[d-1]-B[d-1]| - |A[d]-B[d]|
^^^?
: find two points A, B so that f(A,B) is maximum.
: n<=100,000
: d<=5
: note: an O(n^2) algorithm will score only 30-40% points
: [2]
: dface (by Rujia Liu):
: given a n*n chessboard, each square is either 0 or 1.
: given m instructions, each involves changing a square(0->1, 1->0).
: after each instruction, print the number of 0-components and 1-components. co
: mponents are 4-connected.
: n<=200
: m<=10,000
: note: an O(mn^2) algorithm will score only 30% points
萬一print就要O(mn^2)呢?
: [3]
: corn (by Rujia Liu)
: given a tree, put it on the plane. i.e associate coordinates to the vertices
: so that no two edges intersect. the enclosing SQUARE should be as small as po
: ssible.
: this task is an output-only task
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 61.228.191.9