Codeforces Round #710 Div3 Solutions

A: Strange Table

Solution:

Just calculate the row and column problem.

Code:

Submission #111192517 - Codeforces
Codeforces. Programming competitions and contests, programming community

B: Partial Replacement

Solution:

Greedy。Start from frist *, find as far as possible * with in k.

Proof:

Under the premise of not exceeding k. If the closer * have solution,then the farther * must also have a solution.
Because they want as less * as possible. So chose farther one.

Code:

Submission #111193559 - Codeforces
Codeforces. Programming competitions and contests, programming community

C: Double-ended Strings

Solution:

Because the length of a and b is 20. So just brute force with $n^4$.

Enumerate the possible substrings of a, and then get the b string to see if it is also a substring. Even no need KMP.

Code:

Submission #111194136 - Codeforces
Codeforces. Programming competitions and contests, programming community

D: Epic Transformation

Solution:

Count the number of occurrences of each number. Then take the two most frequent numbers each time. It's enough to simulate it all the time, up to 10w times.

Code:

Submission #111195611 - Codeforces
Codeforces. Programming competitions and contests, programming community

E: Restoring the Permutation

Solution:

Greedy. Let's prove it.

Because q is increasing.

when $q_i\neq{q_{i-1}}$, then $p_i=q_i$

When  $q_i={q_{i-1}}$. If want lexicographically maximal, then go to the remaining numbers to find the largest value which smaller than $q_i$. If want lexicographically minimal, find the smallest value which smaller than $q_i$.

Code:

TreeSet is very useful.

Submission #111196996 - Codeforces
Codeforces. Programming competitions and contests, programming community

F: Triangular Paths

Solution:

Let's consider the sum of each node. The node with odd sum always go to the right. And the next node of it is also with odd sum. So it come to a kind of "layer".

So the problem change to count the number of odd layer need to be passed.

The only thing is: If the current position and next position are in same even layer, then every step need change the status.

Code:

Submission #111198697 - Codeforces
Codeforces. Programming competitions and contests, programming community

G: Maximize the Remaining String

Solution

Lexicographically maximum. And the length of answer is less than 26. So let's go through the index of answer string one by one.

For each index (for example ans[i]), we want to chose the biggest alphabet, and want to put it in front as much as possible.

But we also need avoid something like abcde, and we put ans[0]=e. And then all other alphabet can't put in follow position.

So what I did is: For each ans[i], we try to put alphabet from z to a.

  1. Filter out the alphabet never present or already be chosen.
  2. Find the first index of current alphabet after "the index of last chosen alphabet".
  3. Check all 26 alphabets, to see if all of them are never present or already be chosen or can be chosen after the index above. If so, we can chose current alphabet. And because we try from z to a, so if current alphabet is ok, then it should be the best solution.

代码:

Submission #111210979 - Codeforces
Codeforces. Programming competitions and contests, programming community

DigitalOcean Referral Badge 蜀ICP备19018968号