Educational Codeforces Round #108 ABCD ​题解

A. Red and Blue Beans

题意

你有$r$个红豆子,$b$个蓝豆子。现在你要把豆子分成若干堆。要求每一堆至少有1个红豆子,至少1个蓝豆子,且红豆子和蓝豆子的数目差不能超过$d$个。问可不可能?

题解

取$r$和$b$的最小值$min$,最大值$max$。

那么分成$max-min$堆。然后$max$中剩下的均分到每一堆里,看看会不会超过$d$个。

代码

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

B. The Cake Is a Lie

题意

给你一个$n\times m$的地图。你从$(1,1)$出发,要到$(n,m)$去。往右走的开销是$x$,往下走的开销是$y$。问可不可能恰好用$k$走到目的地。

题解

开销其实是固定的。其开销一定是$n -1+(m -1)\times n$。

代码

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

C. Berland Regional

题意

有$n$个人,有$n$个学校。第$i$个人属于学校$u_i$,其技能是$s_i$。现在每个学校都派队伍打比赛。每个队伍要$k$个人,每个学校都是按“强强组合”的方式派队伍出来。必须派一整个队,不能派半个队。

问对于任意的$k$,整个比赛的参赛者的总技能数是多少。

题解

计算每个学校的技能的前缀和。然后直接暴力求解即可。

复杂度一定不会爆,因为对于每个学校,超过其人数之后的$k$都没有必要考虑了。

代码

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

D. Maximum Sum of Products

题意

给你一个长度为$n$的数组$a$和一个长度为$n$的数组$b$。现在你能把$a$中的最多一段反转。问你$\sum\limits_{i=1}^n a_i \cdot b_i$可能的最大值。

题解

可以看作一个DP,虽然其本质就是直接暴力求解。

首先定义$base=\sum\limits_{i=1}^n a_i \cdot b_i$。也就是不做任何操作下的结果。

我们定义$dp[i][j]$表示把$a$中$[i,j]$反转后的结果。不难得出:$$dp[i][j]=a[i]\cdot b[j] + a[j]\cdot b[i] - (a[i]\cdot b[i] + a[j]\cdot b[j]) + dp[i+1][j-1] + base$$

而显然$dp[i][i]=base$,同时$dp[i][i+1]$可以很容易算出来。

代码

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