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$的方案数。相乘的时候要固定后缀部分一定要选当前球员,这样可以避免算重。