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