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

A. Forbidden Subsequence

题解

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

代码

Java

C++

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

C++

C. Paprika and Permutation

题解

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

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

代码

Java

C++

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

C++