2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报 [2020/05/29 23:07] chielo [jsh] |
2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报 [2020/05/31 16:45] (当前版本) prime21 [pmxm] |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| ==== zzh ==== | ==== zzh ==== | ||
| + | |||
| + | [[https://codeforces.com/contest/1358/|Codeforces Round #645 (Div. 2)]]: ''pro: 5/6/6'' ''rk: 80/18169'' | ||
| + | |||
| + | [[https://codeforces.com/contest/1359/|Educational Codeforces Round 88]]: ''pro: 5/6/6'' ''rk: 159/14430'' | ||
| + | |||
| + | 学习了一下 SA。 | ||
| ==== pmxm ==== | ==== pmxm ==== | ||
| + | |||
| + | 本周没有打比赛 | ||
| ==== jsh ==== | ==== jsh ==== | ||
| 行 14: | 行 22: | ||
| ==== zzh ==== | ==== zzh ==== | ||
| + | |||
| + | Python：众所周知，Python 的整数是无限精度的，很多同学也可能知道 Python 有 decimal 处理浮点数。不过可能知道 Fraction 的人就不那么多了。例如 [[https://codeforces.com/contest/1359/problem/C|Educational Codeforces Round 88 C]] 这样的题，如果用 C++ 写可能会累死累活写 20 分钟，甚至还容易写错。而使用 Python 则可以很容易完成。 | ||
| ==== pmxm ==== | ==== pmxm ==== | ||
| + | KM如何保持复杂度和点数少的那一边一致的问题。 | ||
| + | |||
| + | 一个online问题: | ||
| + | |||
| + | 在线二分图匹配问题，给定一个二分图，每条边会在线的加入和删除，求最大匹配。 | ||
| ==== jsh ==== | ==== jsh ==== | ||
| 行 33: | 行 48: | ||
| 题意： | 题意： | ||
| - | 共 $n \le 8000$ 个编号的宝石和 $n$ 个编号的箱子，每个箱子要装有恰好一个宝石，但第 $i$ 个宝石不能放在第 $a_i$ 个箱子里。 | + | 共 $n$ 个编号的宝石和 $n$ 个编号的箱子，$n \le 8000$。每个箱子要装有恰好一个宝石，但第 $i$ 个宝石不能放在第 $a_i$ 个箱子里。 |
| - | 问有多少种装箱的方案数。 | + | |
| + | 问有多少种装箱的方案数。取模。 | ||
| $a_i$ 不是个排列，可能有重。 | $a_i$ 不是个排列，可能有重。 | ||
| - | 题解： | ||
| <hidden 题解> | <hidden 题解> | ||
| 行 54: | 行 69: | ||
| \[\prod_{i} (1 + b_i x)\] | \[\prod_{i} (1 + b_i x)\] | ||
| - | 记展开的第 $i$ 项系数为 $c_i$，即 $i$ 个宝石放错的玩法，乘上其余宝石乱排的方案数，有 $S_i = c_i (n - i)!$。 | + | 记展开的第 $i$ 项系数为 $c_i$，即 $i$ 个宝石放错的玩法。我们乘上其余宝石乱排的方案数，有 $S_i = c_i (n - i)!$。 |
| 那个多项式展开就是个背包，$\mathcal{O}(n^2)$ DP 一下，剩下的都好做。 | 那个多项式展开就是个背包，$\mathcal{O}(n^2)$ DP 一下，剩下的都好做。 | ||
| + | |||
| + | zzh's comment：多嘴一下，FFT 甚至可以做到 $\mathcal{O}(n\log^{2}n)$。 | ||
| </hidden> | </hidden> | ||
2020-2021/teams/intrepidsword/2020.05.22-2020.05.28_周报.1590764848.txt.gz · 最后更改: 2020/05/29 23:07 由 chielo
