Topcoder SRM705


Problem Statement

Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies: in addition to the program, the package manager has to install some libraries used by the program.
The package repository contains exactly 1000 libraries. For simplicity, we will number them from 1 to 1000, inclusive.
You are given the information about the dependencies of the programs Fox Ciel wants to install. More precisely, you are given the int[]s A and B, both containing the same number of elements. For each valid i, one of the programs needs all libraries that have numbers between A[i] and B[i], inclusive. Note that the programs may have overlapping dependences: multiple programs may require the same library to be installed. Of course, in such cases it is sufficient to install such a library once.
Calculate and return the total number of libraries that need to be installed.





Problem Statement

The ancient civilization of Nlogonia used the same 26 letters as modern English: 'a'-'z'. However, we do not know the order in which these letters appeared in the Nlogonian alphabet.
One particular custom in Nlogonia was that in a good word the letters appear in non-decreasing order. For example, in English the word "ciel" is not a good word because in the alphabet 'i' is after 'e'. The word "ceil" is a good word because 'c' <= 'e' <= 'i' <= 'l'.
You are given the String[] words. Each element of words is a nonempty string of lowercase English letters. Return "Possible" if it is possible that all elements of words were good words in Nlogonian, and "Impossible" otherwise.
In other words, return "Possible" if and only if there is at least one possible Nlogonian alphabet such that the letters of each word in words are in non-decreasing alphabetical order.





Problem Statement

Agus has a binary Christmas tree. More precisely, the decorative balls on his tree are arranged into a complete binary tree with depth levels. At the top of the Christmas tree there is a single ball: the root of the binary tree of balls. This is the only ball on level 1. For each x between 1 and depth-1, inclusive, each ball on level x has exactly two children on level x+1: one ball that is its left child and one ball that is its right child. Hence, there are exactly 2^x balls on level x. The balls on level depth are the leaves of the tree.
There are N colors, numbered 0 through N-1. Each ball has one of those N colors. The colors of the balls follow a simple pattern: If the color of a ball is c, then the color of its left child is left[c] and the color of its right child is right[c].
You are given the long depth. You are also given the int[]s left and right, each with N elements.
You do not know the colors of any of the balls on Agus's tree. Obviously, the colors of all balls are determined by the color of the ball that is the root of the tree. For each possible color r of the root of the tree, do the following:

  1. For each i, determine c(i) = the number of leaves of color i.
  2. Compute the value v(r) = (c(0)^2 + c(1)^2 + ... + c(N-1)^2) modulo 10^9+7.

Return the largest of all possible values v(r).
Note that the maximum of all v(r) is taken only after the modulo operator is used to compute each of them. In other words, we are not necessarily maximizing the sum of c(i)^2, we are maximizing the remainder that sum can give modulo 10^9+7.





我们的目标就是\sum a[j][i]^{2}的最大值

时间复杂度O(\log d\times N^{3})