Codeforces Round #761 ABCD solutions (Java/C++)

A. Forbidden Subsequence

Solution:

You can sort the strings directly, that is, you can directly output the string in the form of aaaabbbbccccdefg.
However, if t is "abc", and there are both a, b, and c in s, output a string of the form aaaacccbbbdefg.

Code:

Java

C++

B. GCD Problem

Solution:

If c=1, then the problem is transformed into dividing n-1 into a and b so that a and b are relatively prime.

Then we assume that a is a prime number, then (n-1-a)% a != 0. Obviously, as long as (n-1)% a! = 0, then (n-1-a)% a! = 0.
The problem then turns to find a prime number a such that a is not a factor of n-1.
So obviously a is 29 at most, because if all prime numbers below 29 are divisible by n-1, then n-1 is at least 235*...*23.

Therefore, only need to enumerate a.

Code:

Java

C++

C. Paprika and Permutation

Solution:

First of all, if a certain a[i] itself is between 1 and n, then we prefer not to change this value.

For other values, we consider from small to large, and each time we see if it can be used to fill in the smallest and unfilled numbers.

Code:

Java

C++

D. Too Many Impostors (easy/hard version)

Solution:

We inquire 3 people each time. That is, the first query 1, 2, 3; the second query 4, 5, 6. This requires $\frac 1 3 n$ queries.

On this basis, if we know the specific location of a certain impostor and crewmate, then for a certain 3 people above, we only need 2 queries to get the identity of each person inside.
Take the query result of 1, 2, and 3 as 0, and we know that 8 is impostor and 9 is crewmate as an example.
Obviously, there is at most 1 crewmate among the two people 1, 2, then if we query 1, 2, and 9 are 0, then 1 and 2 must be impostor. Similarly, if 2, 3, and 9 are 0, then 2 and 3 are both impostor.
But if 1, 2, 9 are 1, it means that there is one and only one crewmate between 1 and 2. If 2, 3, and 9 are also 1, then 2 must be crewmate. Otherwise, 1 must be crewmate.
Conversely, if the query result of 4, 5, 6 is 1, then we use 8 to test.
This process requires $\frac 2 3 n$ queries.

Now, our problem is how to find out the specific location of a pair of impostor and crewmate.

First, if the query result of 1, 2, 3 is 0, and the query result of 2, 3, 4 is 1. Then there is one and only one impostor in 2 and 3. At the same time, 1 must be impostor, and 4 must be crewmate.

Therefore, if the results of the first round of queries are not all the same, we must be able to get the above situation through two additional queries.
For example, the result of 1, 2, 3 is 0, and the result of 7, 8, 9 is 1. Then we query 2, 3, 7 and 3, 7, 8, and these 4 queries must have the above situation.
This situation requires 2 queries.

If the results of the query are all the same, and there are at least $\frac 1 3 n$ of impostor or crewmate. Then out of every three people, exactly one person is different from the result.
For example, that the results of the first round are all 0. If 1 is a crewmate, then at least one of the results of queries 1, 4, 5 and 1, 5, 6 should be 1. Otherwise, 1 must be impostor.
If we try 1 and 2 and find that both are impostor, then 3 must be the crewmate.
This situation requires up to 4 queries.

So in summary, we need at most n+4 queries.

Code:

Java

C++