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

A. Odd Set

题解

只需要统计偶数的个数即可。当且仅当偶数个数和奇数的个数相等时输出Yes。

代码

Java

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

C++

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

B. Plus and Multiply

题解

不难发现,如果n在集合中,则n必能表示为$a^x+y\cdot b$,其中$x\geq 0, y \geq 0$。因此枚举x即可。
以$(a+b)\cdot a + b$为例,这个等价于$a^2+b\cdot(a+1)$。

代码

Java

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

C++

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

C. Strange Function

这个题的关键在于,我们可以发现,随着f(i)的值增大,剩下的i都不能被已有的任何数整除,因此也就不能被已有的所有数的最小公倍数整除。

Codeforces Round #729 Strange Function 题解 (Java/C++)
题解首先我们立刻可以注意到,当i为奇数时,f(i)=2。接着我们开始考量f(i)=3的情况。显然根据定义我们可以知道,只有i为偶数,且i不能被3整除时f(i)=3。因此我们也可以说:对于所有的i,排除f(i)=2和f(i)=3的情况,剩下的i一定不能被6整除。进一步,当我们考虑到f(i)=4的情况后,剩下的i一定不能被lcm(4,6)=12整除。
点击上面链接查看详细题解

D. Priority Queue

这个题的主要关键是把问题转化为求每个数字能出现在多少种子序列中。以及在计算过程中要注意一些细节的情况。

Codeforces Round #729 Priority Queue 题解 (Java/C++)
题解立刻可以想到,我们只需要统计每个+操作的x能在多少种子序列中出现即可。假设第i步是+操作,其值为a[i]。如果这个a[i]保留到最后,那么整个过程中的所有-操作都不会操作到a[i]。也就是说,这个整个过程中,执行-操作时,必为下面两种情况之一: