Codeforces Round #761 ABCD 题解 (Java/C++)

A. Forbidden Subsequence

题解

直接对字符串排序即可,也就是说,直接输出形如aaaabbbbccccdefg的字符串即可。
但是,如果t是"abc",且s里面既有a又有b又有c,则输出形如aaaacccbbbdefg的字符串即可。

代码

Java

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

C++

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

B. GCD Problem

题解

如果c=1,那么问题就转换为把n-1分成a和b,使得a和b互质。

接着我们假设a为质数,则有(n-1-a) % a != 0。显然,只要(n-1) % a != 0,则(n-1-a)%a!=0。
于是问题就转变为了寻找一个质数a,使得a不是n-1的因数。
于是显然a最多是29,因为如果29以下的所有素数都能被n-1整除,那么n-1最少是2*3*5*...*23。

因此,只需要枚举a即可。

代码

Java

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

C++

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

C. Paprika and Permutation

题解

首先,如果某个a[i]本身就在1到n之间,那么我们优先不改变这个值。

除此之外的其他值,我们从小到大依次考虑,每次都看看能不能用来填充最小的且没有用过的数字。

代码

Java

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

C++

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

D. Too Many Impostors (easy/hard version)

题解

我们每次依次对连续的3个人进行查询。也就是第一次查询1,2,3;第二次查询4,5,6。这个需要$\frac 1 3 n$次查询。

在此基础上,如果我们知道了某一个impostor和crewmate的具体位置,那么对于某3个人,我们只需2次查询就能得到里面每个人的身份。
以1,2,3的查询结果为0,且我们知道了8是impostor,9是crewmate为例。
显然1,2这两个人中最多有1个crewmate,那么如果我们查询1,2,9是0,那么1和2必然都是impostor。同理2,3,9是0,则2和3都是impostor。
但如果1,2,9是1,说明1和2之间有且仅有一个crewmate。如果2,3,9也是1,那么必然2是crewmate。反之则必然1是crewmate。
反之,如果4,5,6的查询结果为1,则我们就用8去测试。
这个过程需要$\frac 2 3 n$次查询。

现在,我们的问题就是如何找出一对impostor和crewmate的具体位置。

首先,如果1,2,3的查询结果是0,而2,3,4的查询结果是1。则2和3中有且只有一个impostor。同时1必为impostor,而4必为crewmate。

于是,如果第一轮的查询的结果不全相同,则我们必然可以通过两次额外的查询得到上面的情况。
比如1,2,3的结果是0,而7,8,9的结果1。那么我们查询2,3,7和3,7,8,这4次查询中必有上面的情况。
这种情况需要2次查询。

如果查询的结果全相同,而impostor或者crewmate至少有$\frac 1 3 n$个。则每3个人中,恰好有一个是和结果不同的人。
以第一轮的结果全为0为例。如果1是crewmate,那么我们查询1,4,5和1,5,6的结果中应该至少有一个是1。否则1必为impostor。
如果我们尝试了1和2之后,发现都是impostor,那么3必然是crewmate。
这种情况最多需要4次查询。

于是综上,我们最多需要n+4次查询。

代码

Java

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

C++

Submission #141751586 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论