151A - Soft Drinking

Simply calculate the answer as the sample indicates.

151B - Phone Numbers

A straightforward implementation problem. Take care of the output format.

151C - Win or Freeze

Note that the player who can not move wins! Therefore, for the initially given integer q, if it is a prime number, the first player wins.

Otherwise, we decompose q = (p₁)^a₁(p₂)^a₂..., where p_i is a prime divisor. If q only has two prime divisors, it is obvious that the second player wins. If q has more than two prime divisors, the first player definitely wins, since he can find any two prime divisors p_i and p_j and write down integer p_i × p_j, and then the second player has to face an integer that has only two prime divisors.

As a general method, we can find a divisor of q, denoted as d, which falls into interval [2, \srqt{q}]. If such d can not be found, the first player wins. Otherwise, we have found two divisors of q, i.e., d and q / d. Then, we test whether both of them are prime integers. If yes, the first player loses. Otherwise, it suffices to find any two prime divisors of q.

151D - Quantity of Strings

One of the methods is the same as mentioned in tutorials. We can start from some simple examples and find out some particular rules (or patterns) for different values of k and n. Then, we compute the answers according to different cases.

Another method is using union-find. Each letter in the string can be viewed as a node, and a palindrome in fact has introduced edges among different nodes. The connected nodes must have the same letter and thus the number of connected components just indicates that we have these “positions” and each of them can be assigned with a number of letters, which is equal to the size of alphabet.

151E - Smart Cheater

The problem asks to find a segment for each passenger so that he and the conductor can earn as much money as possible.

Suppose that the segment [x_i, x_j] is selected. Then, they can save money equal to x_j - x_i = x_i + 1 - x_i + x_i + 2 - x_i + 1 + ..., while might be penalized with an expected amount of money equal to (p_i + p_i + 1 + ...p_j - 1) × c. Thus, the expectation should be (x_i + 1 - x_i - p_i × c) + (x_i + 2 - x_i + 1 - p_i + 1 × c) + .... It can be seen that the expectation can be viewed as the sum of expectation value of each neighboring stop. Therefore, the original problem can be reduced to such one that asks to find a consecutive subsequence which gives the maximum sum (a classical problem).

To solve the reduced problem, we should adopt segment tree since the number of queries is large. The main idea is divide and conquer. Given a sequence with range of [l, r], we divide it into two smaller sequences with ranges of [l, mid] and [mid + 1, r], respectively. For [l, r], the subsequence with maximum sum can only belong to the following three cases: 1) it is completely included in [l, mid]; 2) it is completely included in [mid + 1, r]; 3) it has intersection both with the two smaller sequences, and thus it must be the concatenation of “maximum suffix of the first sequence” and “maximum prefix of the second sequence”.

Therefore, for each node in the segment tree, we should store maximum prefix, maximum suffix, total sum, and maximum subsequence sum. Then, we can build the tree, and answer the queries.