比赛地址

Factors of Factorial

直接把 $1\sim n$ 分解质因数即可。

代码

Walk and Teleport

显然从左往右走是最优的,相邻两个选更小的方式即可。

代码

Grouping

设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。

转移时枚举人数 $=j$ 的组数 $k$,那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个,然后要把 $jk$ 个人分成 $k$ 组,因此有

$$ dp_{i,j}=\sum_k dp_{i-jk,j-1}\times{n-i+jk\choose jk}\times\frac{(jk)!}{k!(j!)^k} $$

代码

Yakiniku Restaurants

显然每张烧烤券应该用在 $b_{i,j}$ 最大的位置。

考虑枚举右端点,并维护 $ans_l$ 表示左端点是 $l$ 时的答案。

那么当右端点右移时,收益发生改变当且仅当有一张烧烤券的选择变成了 $r$,也就是 $r$ 是一个前缀最大值。

考虑开 $m$ 个单调栈来维护每种烧烤券的前缀最大值,那么在弹栈时会有一段区间的 $ans_l$ 对应改变,可以通过差分来修改。

最后前面的 $ans_l$ 还需要减去路程,同样可以差分修改。

这样子再做一次前缀和来求出每个 $ans_l$ 来更新答案即可。

代码

最后修改:2020 年 09 月 15 日 08 : 04 PM