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
[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
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.162.210.22