Codeforces Round #498 (Div. 3)

  • 2018-07-20
  • 37
  • 1

A. Adjacent Replacements

题目:

Mishka got an integer array a of length n as a birthday present (what a surprise!).
Mishka doesn’t like this present and wants to change it somehow. He has invented an algorithm and called it “Mishka’s Adjacent Replacements Algorithm”. This algorithm can be represented as a sequence of steps:
Replace each occurrence of 1 in the array a with 2; Replace each occurrence of 2 in the array a with 1; Replace each occurrence of 3 in the array a with 4; Replace each occurrence of 4 in the array a with 3; Replace each occurrence of 5 in the array a with 6; Replace each occurrence of 6 in the array a with 5; \dots Replace each occurrence of 10^9 – 1 in the array a with 10^9; Replace each occurrence of 10^9 in the array a with 10^9 – 1. Note that the dots in the middle of this algorithm mean that Mishka applies these replacements for each pair of adjacent integers (2i – 1, 2i) for each i \in{1, 2, \ldots, 5 \cdot 10^8} as described above.
For example, for the array a = [1, 2, 4, 5, 10], the following sequence of arrays represents the algorithm:
[1, 2, 4, 5, 10] \rightarrow (replace all occurrences of 1 with 2) \rightarrow [2, 2, 4, 5, 10] \rightarrow (replace all occurrences of 2 with 1) \rightarrow [1, 1, 4, 5, 10] \rightarrow (replace all occurrences of 3 with 4) \rightarrow [1, 1, 4, 5, 10] \rightarrow (replace all occurrences of 4 with 3) \rightarrow [1, 1, 3, 5, 10] \rightarrow (replace all occurrences of 5 with 6) \rightarrow [1, 1, 3, 6, 10] \rightarrow (replace all occurrences of 6 with 5) \rightarrow [1, 1, 3, 5, 10] \rightarrow \dots \rightarrow [1, 1, 3, 5, 10] \rightarrow (replace all occurrences of 10 with 9) \rightarrow [1, 1, 3, 5, 9]. The later steps of the algorithm do not change the array.
Mishka is very lazy and he doesn’t want to apply these changes by himself. But he is very interested in their result. Help him find it.

Input:

The first line of the input contains one integer number n (1 \le n \le 1000) — the number of elements in Mishka’s birthday present (surprisingly, an array).
The second line of the input contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — the elements of the array.

Output

Print n integers — b_1, b_2, \dots, b_n, where b_i is the final value of the i-th element of the array after applying “Mishka’s Adjacent Replacements Algorithm” to the array a. Note that you cannot change the order of elements in the array.

Sample Input:

5
1 2 4 5 10

Sample Output:

1 1 3 5 9

Sample Input:

10
10000 10 50605065 1 5 89 5 999999999 60506056 1000000000

Sample Output:

9999 9 50605065 1 5 89 5 999999999 60506055 999999999

题目链接

给定一个数列,对1-10^9进行遍历,奇数+1偶数-1,输出操作后的数列。

显然数列中奇数不变,偶数-1。

AC代码:

B. Polycarp’s Practice

题目:

Polycarp is practicing his problem solving skill. He has a list of n problems with difficulties a_1, a_2, \dots, a_n, respectively. His plan is to practice for exactly k days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all n problems in exactly k days.
Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can’t skip problems or solve them multiple times. As a result, in k days he will solve all the n problems.
The profit of the j-th day of Polycarp’s practice is the maximum among all the difficulties of problems Polycarp solves during the j-th day (i.e. if he solves problems with indices from l to r during a day, then the profit of the day is \max\limits_{l \le i \le r}a_i). The total profit of his practice is the sum of the profits over all k days of his practice.
You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all n problems between k days satisfying the conditions above in such a way, that the total profit is maximum.
For example, if n = 8, k = 3 and a = [5, 4, 2, 6, 5, 1, 9, 2], one of the possible distributions with maximum total profit is: [5, 4, 2], [6, 5], [1, 9, 2]. Here the total profit equals 5 + 6 + 9 = 20.

Input:

The first line of the input contains two integers n and k (1 \le k \le n \le 2000) — the number of problems and the number of days, respectively.
The second line of the input contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 2000) — difficulties of problems in Polycarp’s list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).

Output

In the first line of the output print the maximum possible total profit.
In the second line print exactly k positive integers t_1, t_2, \dots, t_k (t_1 + t_2 + \dots + t_k must equal n), where t_j means the number of problems Polycarp will solve during the j-th day in order to achieve the maximum possible total profit of his practice.
If there are many possible answers, you may print any of them.

Sample Input:

8 3
5 4 2 6 5 1 9 2

Sample Output:

20
3 2 3

Sample Input:

5 1
1 1 1 1 1

Sample Output:

1
5

Sample Input:

4 2
1 2000 2000 2

Sample Output:

4000
2 2

题目链接

对元素个数位n的数列分为k个区间,使每个区间的最大值之和最大,输出此值和每个区间的元素个数。

用最大的k个数进行区域划分,使这k个值分别单独存在于一个区间中。

AC代码:

C. Three Parts of the Array

题目:

You are given an array d_1, d_2, \dots, d_n consisting of n integer numbers.
Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.
Let the sum of elements of the first part be sum_1, the sum of elements of the second part be sum_2 and the sum of elements of the third part be sum_3. Among all possible ways to split the array you have to choose a way such that sum_1 = sum_3 and sum_1 is maximum possible.
More formally, if the first part of the array contains a elements, the second part of the array contains b elements and the third part contains c elements, then:
sum_1 = \sum\limits_{1 \le i \le a}d_i, sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i, sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.
The sum of an empty array is 0.
Your task is to find a way to split the array such that sum_1 = sum_3 and sum_1 is maximum possible.

Input:

The first line of the input contains one integer n (1 \le n \le 2 \cdot 10^5) — the number of elements in the array d.
The second line of the input contains n integers d_1, d_2, \dots, d_n (1 \le d_i \le 10^9) — the elements of the array d.

Output

Print a single integer — the maximum possible value of sum_1, considering that the condition sum_1 = sum_3 must be met.
Obviously, at least one valid way to split the array exists (use a=c=0 and b=n).

Sample Input:

5
1 3 1 1 4

Sample Output:

5

Sample Input:

5
1 3 2 1 4

Sample Output:

4

Sample Input:

3
4 1 2

Sample Output:

0

题目链接

把数列分为三段,使第一段之和等于第三段之和,求最大和。

先计算前i项和存入set中,对数列倒序遍历,每次删除一个set中的数,并更新前i项和与后j项和,当后j项和在set中存在时判断记录。

AC代码:

D. Two Strings Swaps

题目:

You are given two strings a and b consisting of lowercase English letters, both of length n. The characters of both strings have indices from 1 to n, inclusive.
You are allowed to do the following changes:
Choose any index i (1 \le i \le n) and swap characters a_i and b_i; Choose any index i (1 \le i \le n) and swap characters a_i and a_{n – i + 1}; Choose any index i (1 \le i \le n) and swap characters b_i and b_{n – i + 1}. Note that if n is odd, you are formally allowed to swap a_{\lceil\frac{n}{2}\rceil} with a_{\lceil\frac{n}{2}\rceil} (and the same with the string b) but this move is useless. Also you can swap two equal characters but this operation is useless as well.
You have to make these strings equal by applying any number of changes described above, in any order. But it is obvious that it may be impossible to make two strings equal by these swaps.
In one preprocess move you can replace a character in a with another character. In other words, in a single preprocess move you can choose any index i (1 \le i \le n), any character c and set a_i := c.
Your task is to find the minimum number of preprocess moves to apply in such a way that after them you can make strings a and b equal by applying some number of changes described in the list above.
Note that the number of changes you make after the preprocess moves does not matter. Also note that you cannot apply preprocess moves to the string b or make any preprocess moves after the first change is made.

Input:

The first line of the input contains one integer n (1 \le n \le 10^5) — the length of strings a and b.
The second line contains the string a consisting of exactly n lowercase English letters.
The third line contains the string b consisting of exactly n lowercase English letters.

Output

Print a single integer — the minimum number of preprocess moves to apply before changes, so that it is possible to make the string a equal to string b with a sequence of changes from the list above.

Sample Input:

7
abacaba
bacabaa

Sample Output:

4

Sample Input:

5
zcabd
dbacz

Sample Output:

0

题目链接

两个字符串,可以进行三种交换操作,问改变第一个字符串中的几个字符后可以进过这三种交换操作和第二个字符串完全相等。

直接暴力判断\lbrace a[i],a[n-i-1],b[i],b[n-i-1] \rbrace四个数的情况进行计数即可。

AC代码:

评论

  • hh回复

    大佬E题呢