Topcoder SRM705

SuperUserDo

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.

Solution

签到题,看错题意导致浪费很多时间

直接差分就行,时间复杂度O(N+M)


AlphabetOrderDiv2

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.

Solution

依然是签到题,裸的传递闭包

时间复杂度O(26^{3}+n^{2})


ChristmasBinaryTree

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.

Solution

dp[i][j][k]表示深度为i的树,根节点颜色为j,叶子节点颜色为k的个数

dp[i][j][k]=dp[i-1][j][left[k]]+dp[i-1][j][right[j]]

考虑构造转移矩阵,跑矩阵快速幂

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

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

 

发表评论