2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报 [2020/05/29 21:00]
admin 创建
+++ 2020-2021:teams:intrepidsword:2020.05.22-2020.05.28_周报 [2020/05/31 16:45] (当前版本)
prime21 [pmxm]
@@ 行 6: / 行 6: @@
 ==== 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 ====
+本周没有打比赛
 ==== jsh ====
@@ 行 14: / 行 22: @@
 ==== zzh ====
+Python：众所周知，Python 的整数是无限精度的，很多同学也可能知道 Python 有 decimal 处理浮点数。不过可能知道 Fraction 的人就不那么多了。例如 [[https://codeforces.com/contest/1359/problem/C|Educational Codeforces Round 88 C]] 这样的题，如果用 C++ 写可能会累死累活写 20 分钟，甚至还容易写错。而使用 Python 则可以很容易完成。
 ==== pmxm ====
+KM如何保持复杂度和点数少的那一边一致的问题。
+一个online问题:
+在线二分图匹配问题，给定一个二分图，每条边会在线的加入和删除，求最大匹配。
 ==== jsh ====
+=== 错排问题（错位排列） ===
+错排，是个时常会听到，但做到就有点抓瞎的东西。
+原始的全错位排列问题的做法有很多种，但要记得了解到做法的本质，因为出题通常就是某种做法的本质没变，在条件上稍加改动而已。
+具体的可参考 [[https://zh.wikipedia.org/zh-cn/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98|错排问题 - 维基百科]] 和 [[https://baike.baidu.com/item/%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F|错排公式 - 百度百科]]。
+== 牛客练习赛64 - D - 宝石装箱 ==
+[[https://ac.nowcoder.com/acm/contest/5633/D|题目链接]]
+题意：
+共 $n$ 个编号的宝石和 $n$ 个编号的箱子，$n \le 8000$。每个箱子要装有恰好一个宝石，但第 $i$ 个宝石不能放在第 $a_i$ 个箱子里。
+问有多少种装箱的方案数。取模。
+$a_i$ 不是个排列，可能有重。
+<hidden 题解>
+错排改了改，每个物品的限制虽然还是一个，但限制可能有重复。
+范围上看 $\mathcal{O}(n^2)$ 就能过。
+那我们考虑一下容斥，记 $A_i$ 为每个箱子要装有恰好一个宝石的情况下，第 $i$ 个宝石放在了第 $a_i$ 个箱子的方案集合，方案数就是：
+\[{\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|}\]
+哦天哪，我们把所有 $j$ 个 $A_i$ 的交集的大小的和，记为 $S_j$，即有 $j$ 个宝石放错，其余随便放的方案数。问题的答案就是：
+\[\sum_{i=0}^{n} (-1)^i S_i\]
+这个 $S_j$ 很好算。记第 $i$ 个箱子有 $b_i$ 个宝石不能放，那么对于放错宝石的数量贡献与否，可以得到多项式：
+\[\prod_{i} (1 + b_i x)\]
+记展开的第 $i$ 项系数为 $c_i$，即 $i$ 个宝石放错的玩法。我们乘上其余宝石乱排的方案数，有 $S_i = c_i (n - i)!$。
+那个多项式展开就是个背包，$\mathcal{O}(n^2)$ DP 一下，剩下的都好做。
+zzh's comment：多嘴一下，FFT 甚至可以做到 $\mathcal{O}(n\log^{2}n)$。
+</hidden>

2020-2021/teams/intrepidsword/2020.05.22-2020.05.28_周报.1590757250.txt.gz · 最后更改: 2020/05/29 21:00 由 admin