Codeforces Round #733 ABCDE 题解 (Java/C++)

A. Binary Decimal

题解

显然,我们只需检查每一位的数字。对于每一个数字,其数字是多少,就需要多少个数组成。比如321的十位为2,就需要由两个数组成。

代码

Java

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

C++

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

B. Putting Plates

题解

模拟即可。我们从左往右,从上往下依次扫描每个点,只要这个点处于边界,且这个点的四周都没有被占,我们就占住这个点。

代码

Java

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

C++

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

C. Pursuit

题解

模拟即可,因为显然每添加一场,玩家都得100分,Ilya都得0分。因此我们只需要维护添加一场后各自得得分即可,

对于玩家来说,我们使用一个优先队列。因为每多加一场,可能会淘汰优先队列中分数最低得那场比赛。因此我们只需要根据总场数来维护优先队列得长度即可。
对于Ilya来说,我们对Ilya不是0分得比赛进行排序。随着场次得增多,Ilay会逐渐失去分数较低的场次的分数。

不断增加场次,直到玩家分数比Ilya高为止。

代码

Java

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

C++

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

D. Secret Santa

题解

首先b中出现了多少个不同的数字,就有有多少人能送给想送的人。所以现在的问题就只是剩下的人怎么办。

那么剩下的人只有一种出问题的可能:b[i]=i了,且这个人原本想送的人一定被其他的人送了。不妨假设有两个人i和j,一开始b[i]和b[j]=x,而最终b[i]=i,b[j]=x。于是我们只需要交换两个人的送礼目标即可,即b[i]=x,b[j]=i。

因此,我们先忽略不能给自己送礼的条件,在保证尽可能满足每个人意愿的条件下,依次分配即可。
分配完之后,再检查给自己送礼的情况。对于这样的人,我们找到给他想送礼的目标送礼的人,和他交换即可。

代码

Java

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

C++

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

E. Minimax

题解

显然,如果某个字母只出现了一次,那么f(t)=0,我们只需要把这个字母放在最开头即可。比如aabbz,那么zaabb即可。
不难发现,除非有某个字母只出现一次。否则f(t)>0。比如x???x?,k=5时f(t)=1。

接着,如果某个某个字母的出现次数没有占到大约一半,就可以构造出如下字符串:xxyxyxyxyxy...这样f(t)=1。
否则,如果有两个字母,我们就构造xyyyyyxxxxx....这样f(t)=1。
否则我们构造xyxxxxxxxxzabcd。这样的f(t)=1。

于是一堆if else即可。

代码

Java

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

C++

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