Блог пользователя SummerSky

Автор SummerSky, 7 лет назад, По-английски

A. Chat room

Suppose that the given string is denoted as S while "hello" is denoted as T. We can solve the problem by adopting two pointers pS and pT, which point to string S and T, respectively. At first, both pS and pT are set to 0. Then, we increase pS by 1 until it reaches the end of string S. During this process, once it occurs that S[pS]=T[pT], we immediately increase pT by 1 as well. Note that when pT reaches the end of string T, we can break the loop. After all the characters in string S have been visited, and the loop is over (or we break the loop), we can check whether pT has arrived at the end of string T or not. If the answer is YES, it means that we can obtain "hello" from the original given string; otherwise we should output NO.

B. Coins

For any integer N, we can find all its prime divisors and write it in the form of N=p1^a1*p2^a2*...pn^an, where pi is a prime divisor while ai denotes the number of pi that N has. Intuitively, we may come up with such a sequence which is depicted as follows:

1

1*p1

1*p1*p1

1*p1*...*p1

1*p1*...*p1*p2

1*p1*...*p1*p2*p2

1*p1*...*p1*p2*p2*...*p2

...

1*p1*...*p1*p2*p2*...*p2*pn*...*pn

It can be seen that such a sequence have (a1+a2+...an+1) integers, and this is just the maximum number of coins that we can obtain. For instance, if N=36, we have 1, 1*2, 1*2*2, 1*2*2*3, 1*2*2*3*3. We can use "proof by contradiction" to prove this claim. Assume that the optimal sequence has M>(a1+a2+...an+1) coins and we denote this sequence as S. Then, let us try to implement some subtle modification to the current sequence to obtain a better one. We first sort S in an increasing order, and use S[i] to denote the i-th integer after sorting. If S[1] is not "1", we can immediately add "1" to S since any integer is divisible by 1, and thus we have obtained a better sequence S', which is contradictory to our assumption. Then, S[2] must be equal to some prime divisor, since otherwise we can decompose S[2] and obtain a better sequence again. Next, S[3]/S[2] must be some prime divisor as well, since otherwise we can decompose S[3]/S[2]=P*Q, and add S[2]*P to obtain a better sequence. Based on similar arguments, we can find that there are exactly (a1+a2+...an+1) integers in S, which is contradictory to our assumption, and thus proof is completed.

C. Trees

Note that S=(1,2,3....,3,2,1) is always a reasonable sequence. For the given sequence A=(a[1],a[2],...,a[N]), we can calculate the difference between A and S to obtain the following sequence T=A-S=(a[1]-1,a[2]-2,...,a[N-1]-2,a[N]-1). At first, one should note that if T[i]<0, then a[i] must be changed since the problem requires that a[1]>=1. Next, suppose that the optimal sequence is S'=(x+1,x+2,...,x+2,x+1), where x is some non-negative integer. Here "optimal" means that if we change A into S', we can achieve the minimum number of changes. Then, we compute T'=A-S', and count the number of "0" in T'. It can be seen that the number of "0" must be no less than that of any other sequence S''. Furthermore, if we add all the integers in T' by x, it is just the same as T, i.e., A-S'+x=T'+x=A-S=T. Therefore, if we count the number of "x" in T, it will be exactly the same as the number of "0" in T'. Based on these arguments, we can just count the number of different non-negative integers in T, and denote the maximum number of some integer as M. Then, the answer is N-M.

D. Calendar

At first, we store all the strings according to their length, i.e., they are divided into different groups based on their length. Then, all the strings belonging to the same group are sorted in an increasing order. As the problem requires that the final output lines should have the same length, one can calculate that the length should be L=(l1+l2+...+ln)/(n/2)+1, where li denotes the length of the i-th string.

Next, we need implement a loop pf length (n/2) to obtain the answer. During each loop, we will find the first and second string in turn. To find the first string, we can take out the first string of each group and append the special symbol, and find out the smallest one, which is just the target string. Then, we denote the length of the first string as L', and it is sufficient to take out the first string in the group whose strings all have length L-L'-1. The total complexity is O(N). The above operations in fact look like Bucket Sort...

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится