2020-2021:teams:i_dont_know_png:week_summary_1:nikkukun

差别

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

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:week_summary_1:nikkukun [2020/05/09 01:03]
nikkukun 创建
+++ 2020-2021:teams:i_dont_know_png:week_summary_1:nikkukun [2020/05/09 12:22] (当前版本)
nikkukun
@@ 行 1: / 行 1: @@
-扮演中
+===== 比赛 =====
+本周冯如杯，没有打比赛。
+===== 学习总结 =====
+==== 容斥原理 ====
+容斥的一些理解：
+我们能快速知道的是至少满足性质集合 $S$ 的个数 $f(S)$，而很多情况下 $f(S)$ 对相同的 $|S|$ 是相同的，这个时候计算贡献就需要乘上组合数，因为统计的是所有 $|S|$ 相同的贡献 $f(S)$，自然要从所有属性里选择 $|S|$ 种出来枚举。
+如果要求的是没有任何性质 $S$ 的个数，则为
+$$
+\sum _{i=0}^n (-1)^i \binom ni f(i)
+$$
+如果要求的是有至少一个性质 $S$ 的个数，则为
+$$
+\sum _{i=1}^n (-1)^{i+1} \binom ni f(i)
+$$
+显然，这两种之和应该为 $f(0)$，也就是所有性质的集合 $S$。同时不难通过贡献计算得到，第一个式子中只有 $|S| = 0$ 的 $S$ 被计算 $1$ 次，其余都计算了 $0$ 次；第二个式子中只有 $|S| = 0$ 的 $S$ 被计算 $0$ 次，其余都计算了 $1$ 次。
+==== 图论 ====
+平面图的一些相关结论：
+若一个图 $E > 3V-6$，则这个图一定不是平面图。反过来说，如果保证了图是平面图，那么它的边数也不会很多。
+一个图是平面图，当且仅当不存在 $K_5$ 和 $K_{3, 3}$，即五阶完全图与三阶完全二分图。

2020-2021/teams/i_dont_know_png/week_summary_1/nikkukun.1588957400.txt.gz · 最后更改: 2020/05/09 01:03 由 nikkukun