SummerSky's blog

By SummerSky, 7 years ago, In English

A. Word

This is a simple problem. We can count the number of uppercase letters and lowercase letters, respectively, and then compare their results and implement operations accordingly.

B. Fortune Telling

We can adopt two arrays to store the even integers and odd integers, respectively. If there are no odd integers, we should output 0. On the contrary, we first add all the even integers together, and sort all the odd integers in a decreasing order. Then, if the total number of odd integers is odd, we add all of them together; otherwise we add all of them except for the minimum one.

C. Title

It is sufficient to deal with the first half of the string. We use s[i] to denote the i-th (index starts from 1) character in the first half of the string, and further denote the length of the string is n. For each pair s[i] and s[n-i+1], if both of them are '?', we just leave them as they are. If both of them are letters, we check whether they are the same or not, and if they are different, we can immediately output "IMPOSSIBLE". If exactly one of them is a letter while the other one is "?", we just replace "?" with this letter.

After we have completed the above operations, we start from s(n+1)/2 until we reach s[1]. During this process, whenever we meet a "?", we replace it with the "largest" letter that is still not contained in the current string; while if all the letters have been contained in the string, we replace all the left "?" with letter 'a'. Finally, remember to check whether the required letters have appeared in the string for at least once or not.

D. Team Arrangement

At first, we should find out whether the student with number k is the captain or not. To solve this, we can first find the team to which this student belongs (this is just the row index in the "members of a given team" matrix). Then, we enumerate from the first student according to the results of personal training sessions, and find the first one who belongs to the team where the student with number k is. This student must be the captain of this team.

If student with number k is not the captain, we can directly output 1,2,...,n but skipping k, since the priority list of student with number k has no effect on how the members are selected.

If student with number k is the captain, we can immediately find out his two teammates, denoted as T1 and T2, and without loss of generality, we assume that T1<T2. Then, we divide the other students into two groups G1 and G2. At first, all the students that belong to the following teams are put into G2. Then, for the students that belong to the previous teams, if his number is larger than T2, he should be put into G2; otherwise put into G1. Finally, both T1 and T2 are put into G1. After sorting G1 and G2 in both increasing order, we can output G1 and G2 in turn, and this is just the answer. This solutions works since all the students belonging to the following teams cannot be put before T1 and T2, since otherwise some one of them will be selected instead of T1 or T2. Next, all the students with number larger than T2 and belonging to the previous teams should be put after T1 and T2, since they have been selected by other teams and thus they have no effect on the current team.

  • Vote: I like it
  • 0
  • Vote: I do not like it