Educational Codeforces Round #108 ABCDE 题解

A. Red and Blue Beans

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

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

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

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

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

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

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

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

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

给你一个长度为$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]$可以很容易算出来。