• 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.

5
1 2 4 5 10

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

# 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.

8 3
5 4 2 6 5 1 9 2

20
3 2 3

5 1
1 1 1 1 1

1
5

4 2
1 2000 2000 2

4000
2 2

# 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).

5
1 3 1 1 4

5

5
1 3 2 1 4

4

3
4 1 2

0

# 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.

7
abacaba
bacabaa

4

5
zcabd
dbacz

0

大佬E题呢