2020-2021:teams:wangzai_milk:weekly18
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly18 [2020/09/04 13:32] wzx27 |
2020-2021:teams:wangzai_milk:weekly18 [2020/09/04 15:15] (当前版本) zars19 |
||
|---|---|---|---|
| 行 20: | 行 20: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| 暂无。 | 暂无。 | ||
| + | |||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| [[codeforce 1392部分题解]] | [[codeforce 1392部分题解]] | ||
| + | |||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| 暂无。 | 暂无。 | ||
| + | |||
| ===== Zars19 ===== | ===== Zars19 ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | topcoder若干。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | Codeforces Round #666 (Div. 1) | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ==== Zars19 ==== | ==== Zars19 ==== | ||
| + | |||
| + | **来源**：[[https://community.topcoder.com/stat?c=problem_statement&pm=16346|TopCoder - 16346]] | ||
| + | |||
| + | **tag**：计数, dp | ||
| + | |||
| + | **概述**： $n\times n$ 方格，其中 $T$ 个位置放置标记，每行每列都最多放两个，问方案数。 | ||
| + | |||
| + | **答案**：可以用 $dp[i][j][k]$ （第一维可以滚动）表示处理完第 $i$ 行，有 $j$ 列放 $0$ 个， $k$ 列放 $1$ 个的方案数，显然 $n-j-k$ 列放两个。然后转移方程就很好想了。结果只需要统计放置完第 $n$ 行满足 $k+2(n-j-k)=T$ 的加和即可。 | ||
| + | |||
| + | **comments**:巧妙的状态设计。 | ||
| ==== _wzx27 ==== | ==== _wzx27 ==== | ||
| 行 47: | 行 69: | ||
| **答案**： | **答案**： | ||
| - | 容易想到状压 $dp$ ：f[i][num][s1][s2]表示填了前 $i$ 列，放了 $num$ 个东西且最后两列的放置状态为 $s1$ 和 $s2$ 的方案数，但由于 $R$ 并不小，最大可以是 $13$，所以这样过不了。 | + | 容易想到状压 $dp$ ：$f[i][num][s1][s2]$ 表示填了前 $i$ 列，放了 $num$ 个东西且最后两列的放置状态为 $s1$ 和 $s2$ 的方案数，但由于 $R$ 并不小，最大可以是 $13$，所以这样过不了。 |
| 但由于题目的限制 $s1$ 和 $s2$ 两个状态有很多是不必要的，因此可以预处理出放两列的合法状态，发现远比 $2^{13} \times 2^{13}$ 小，在此基础上在转移即可。 | 但由于题目的限制 $s1$ 和 $s2$ 两个状态有很多是不必要的，因此可以预处理出放两列的合法状态，发现远比 $2^{13} \times 2^{13}$ 小，在此基础上在转移即可。 | ||
2020-2021/teams/wangzai_milk/weekly18.1599197570.txt.gz · 最后更改: 2020/09/04 13:32 由 wzx27
