多校9-解题报告.doc

A Poor KingTag: Reversed BFSPreprocessing is needed to calculate answers for all positions (states). Beginning with all checkmate states, you should do reversed Breath-First Search (BFS) to update values. The state can be specified by three positions, so 64*64*64 states in all. For each state, make all possible next states and check if all their values had already determined. If so, you can determine the value (answer) for this state.Best DivisionTag: DP, Trie, Data structureThis is a Dynamic Programming (DP) problem. Let dpi be the answer (maximum K) for the subarray A1Ai. Then, dpi = (max i-Lji, SiSjX dpj) + 1 (Si = A1A2Ai). Now, build bit (1-0) trie to add Si values in order. For each i, indices such that SiSjX is determined by going down along the trie, considering X. Maximum values of a subtree can be stored in its root. Adding or removing values to/from the trie can be done by suitable data structure such as sliding RMQ or multiset.Convex HullTag: Geometry, 3D transform, Convex hullSeveral geometric procedures are needed to solve this problem. First, construct the 3D convex hull of given points. Then, for each query, use CG formulas to transform the query plane to XOY plane. After that, you can find out all intersection points between the edges of convex hull and XOY plane. Now, answer is the area of 2D convex hull of these points.Different SumsTag: Construction, MathFor small n, its easy problem.Let Si be the sum of first i numbers.We take a prime number p larger than n, and an integer x (0 = x p), make Si = 2 * i * p + (i * (i+1) / 2 * x) % p. Lets define ri = (i * (i+1) / 2 * x) % p.If Si Sj = Sk Sl, then i j = k l because |ri -rj| p and |rk rl| p. Also (ri rj rk + rl) must be divisible by p, this leads to i + j = k + l. It means that i = k and j = l.Thus, the array that has these subsums satisfies the problem statement.Now we must make all integers in the array less than 3*n+18.We can choose p as the smallest prime larger than n, and select x that minimizes maxSi-Si-1.For all 6 = n =d or mindist(V, u) , dist(V, v)=d, or there exists at least one node w, f(w) is on the path from f(u) to f(v), mindist(w, u), dist(w, v) = d. The last condition can be checked by considering the center c of the path from u to v. So for all nodes w, if f(w) is on the path f(u) to f(c), dist(u, w) =d, else dist(v, w) =d must be held. This leads a simple range maximum query problem. These can be pre-calculated, so we can answer each query by O(1) time. So required time is O(N*log(N)+Q).GeneratorTag: Inclusion/Exclusion principle, String Matching, Linear equations.Consider the probability that all sequences are generated in i seconds. Lets denote it as f(i). The answer is the sum of i*(f(i)-f(i-1) for all positive integers i. By inclusion/exclusion principle, f(i) is the signed sum of the probability of 2N subsets of sequences are not generated in i seconds. For each subset S, lets denote it as p(S, i). Then q(S,i) = 1-p(S,i) is the probability which at least a sequence of S is generated in i seconds. So f(i) is the signed sum of q(S,i), for all non-empty subset of 1,2,N. The sign is +1 for odd subset, -1 for even subset. For a fixed subset S, summing i*(q(S, i)-q(S,i-1) for all integer i, its simply the expected time of at least a sequence of S is generated. Lets denote it as e(S). So the answer is the signed sum of all e(S).e(S) can be calculated by linear equation.Let x(i) will be the probability i-th sequence of S is the first generated.Then sum of all x(i) equals to 1. And there are |S| equations about x(i) and e(S). All coefficients are calculated by KMP matching. So the answer can be calculated by O(N*N*L+N*N*N*2N).Honey TourTag: Plug DP, Matrix exponentiationCells on a path have exactly two adjacent on-path cells except the two ends.Combine connected component id and cells degree to represent DP state.The number of valid states Ns is less than 200.Calculate state transition matrix by passing the maze once.Intersection is not allowed!Tag: Counting, MatrixFor the simplest case, if K = 1, the number of different ways from (1, a1) to (N, b1) is C(b1-a1)+(N-1)N-1. Here, Cnk means binomial coefficient.If K = 2, the answer is the product of two independent numbers of ways minus number of intersecting ways. Here, all intersecting ways correspond to the ways from (1, a1) to (N, b2) and from (1, a2) to (N, b1). Thus, the answer isC(b1-a1)+(N-1)N-1C(b2-a2)+(N-1)N-1-Cb2-a1+N-1N-1Cb1-a2+N-1N-1=C(b1-a1)+(N-1)N-1C(b2-a2)+(N-1)N-1Cb1-a2+N-1N-1Cb2-a1+N-1N-1Let fi, j=C(bj-ai)+(N-1)N-1 be the number of ways from (1, ai) to (N, bj).In general, it can be proved that the answer is represented as the following determinant:f(i, jK*K=C(b1-a1)+(N-1)N-1C(bK-a1)+(N-1)N-1C(b1-aK)+(N-1)N-1C(bK-aK)+(N-1)N-1Jong Hyok and StringTag: Suffix automataSuffix Automatons each node has corresponding set of strings related to it.Strings in this set have common occurrences in the given strings P1, , PN.Therefore, your task is to count the number of strings related to the SAM node related to string qi.This can be done by calculating lenu-lenlinku. K-th ValueTag: Binary searchBinary search for Ans.Root the tree at an arbitrary node.We define f(i, l) as the maximum number of edges whose length isnt bigger than Ans of any downward path starting from i and with length l.And define g(i, l) = k * f(i, l) l.If there exists a pair (i, l) with L = l 0, then return true.Otherwise if there exists two pairs (i, l) and (j, h) with L = l + h 0 return true.This could take NR time using sweeping.Otherwise return false.So the time complexity is N * R * logN.Less Time, More ProfitTag: Binary search, Maximum flowFind the minimum time by using binary search. Lets see time tm is valid! Make the graph G(V, E, C). V: nodes, E: edges C: value of nodesV: = X + Y, X = 1, 2, , N , Y = 1, 2, ME: (v, u), , we need u to enable v.C: cv = provCalculate maximum weight closure of G by using maximum flow.When this value is not less than L, tm is valid.Math is FunTag: DP, Sta