Posted in: QuestOJ 比赛题解

「FZOI」OI 寒假赛 #1 Div.1 – 题解

A - 资本家 kal0rona

我们可以考虑把每个员工的前缀收益放在折线图上进行考虑:一条折线从$(1, 0)$出发,在$(x, y)$向上走就是给第$x$个员工发钱,上升高度就是发钱数量。最后,把老板当作第$n + 1$个员工即可。可以发现,因为这个是前缀收益,所以最后我们会走到$(n + 1, m)$,我们只需要算从$(1, 0)$到$(n + 1, m)$的不降路径数即可,也就是${n + m \choose m}$。

Read More "「FZOI」OI 寒假赛 #1 Div.1 – 题解"

Posted in: QuestOJ 比赛题解

kal0rona 的 CSP-S2 模拟赛 #1 出题分析

Day 1

篮球 - Basketball

前 30% 的数据

直接枚举上场状态和中间断开的点,由于上场状态只有上场和不上场,所以总的复杂度是$\Theta(2^n n)$。

正解

我们发现球员的数位非常小,且上场球员也非常少。那么,我们可以考虑设计一个前缀异或和还有后缀与和,那么在相同的数字上相乘即可得到结果。$prefix[i][j]$表示前$i$个中,能凑成$j$的方案数,$suffix[i][j]$表示$[i, n]$中,能凑成$j$的方案数。相乘的时候要固定后缀部分一定要选当前球员,这样可以避免算重。

Read More "kal0rona 的 CSP-S2 模拟赛 #1 出题分析"