Educational Codeforces Round 104 ABCDE题解(C++/Java)

A. Arena

题意

给你一个长度为n的数组a,表示n个英雄分别的初始登记。现在这些英雄之间随便互相打,等级高的获胜,获胜可以升一级。问多少英雄可以升到$100^{500}$级。

题解

只要这个英雄不是最低等级,就能一直打比他低等级的那个人,然后升级。

代码

C++:

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

Java:

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

B. Cat Cycle

题意

有两只猫,第一只从n往1循环跳,第二只从1往n循环跳。如果两只猫试图跳到同一个位置,第二只猫会再往后跳一步。问第k步,第二只猫的位置。

题解

首先把位置从1-n改为0-(n-1),同时第k步改成跳k-1次,这样可以方便取余。

计算第二只猫额外需要走的步数即可。不难发现,当n为奇数时,每$\frac{n-1}{2}$次第二只猫会多走一格。于是就可以算出第二只猫走的总步数,取余后加一即可。

代码

C++

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

Java

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

C. Minimum Ties

题意

n个球队踢巡回赛。打平各自得一分,打赢得3分,打输得0分。问,在打平得局数尽可能少得情况下,怎么使n个球队得分数相同。

题解

首先立刻可以想到一种打法:$i$胜过$i+1$。

于是我们可以进一步推广这种打法,我每次让$i$胜过$i+diff$,只要能让每个队都赢一轮,就可以保持分数相同。
不难得出,只要剩余得场次多余n场,就一定能打一轮。

代码

C++

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

Java

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

D. Pythagorean Triples

题意

问对于$1\leq a \leq b \leq c \leq n$。问满足下列等式的所有可能得abc有多少个:$$\begin{cases}
a^2+b^2=c^2\\
c=a^2-b\\
\end{cases}
$$

题解

可以看到$a^2=c+b$,于是$2\leq a^2 \leq 2\cdot 10^9$。于是我们可以枚举a的值。
将$c=a^2-b$代入$a^2+b^2=c^2$可得,$b=\frac{a^2-1}{2}$。进而可以求出$c$ 的值。

于是我们可以预处理出1到$10^9$之间所有可能的c。然后对于输入的n,我们二分出最大可能的c以及其下标即可。

代码

C++

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

Java

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

E. Cheap Dinner

题意

有$n_1$种前菜、$n_2$种主菜、$n_3$种饮料、$n_4$种甜品。每个东西都有一个花费。现在告诉你$m_1$种前菜和主菜不能搭配,$m_2$种主菜和饮料不能搭配,$m_3$种饮料和甜品不能搭配。问你凑出一桌菜最小花费。

题解

首先,先来一个暴力的DP。$dp[i][j]$表示第$i$道菜选择第$j$种菜的最小花费。于是有$dp[i][j]=\min\limits_{1\leq x \leq n_i}{(dp[i-1][x])}+cost[i][j]$。
但直接循环求解$\min\limits_{1\leq x \leq n_i}{(dp[i-1][x])}$一定会TLE。所以需要一种方法快速找出这个最小值。

我们把禁止的搭配按照$y$排序后再按$x$对应的花费进行排序,同时对dp[i-1]按照同样的方式排序。于是我们可以只要找到第一个没有被禁止的$dp[i-1][x]$即可。

代码

C++

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

Java

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