※ 引述《[email protected] (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