差别

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

--- 2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/09 01:15]
potassium
+++ 2020-2021:teams:i_dont_know_png:week_summary_1 [2020/05/16 21:04] (当前版本)
potassium
@@ 行 1: / 行 1: @@
-====== 2020.05.04-2020.05.10 周报 ======
+====== 2020.05.03-2020.05.09 周报 ======
 团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。
@@ 行 11: / 行 11: @@
 本周无团队训练。
+===== 团队会议 =====
-===== 本周推荐 =====
+.5.9 建立[[.:skill_tree|技能树]]，确定[[.:training_plan_2020spring|训练计划]]
+===== 个人训练 - nikkukun =====
-* [[https://codeforces.com/contest/1342/problem/F|1342F - Make It Ascending]]
+==== 比赛 ====
-  * 位运算 DP
-  * 最优性的转移需要想一想
-  * 通过改变 DP 状态减小空间。这题要记录三个状态：last, cnt, mask。一开始的想法是用 ''%%f[last][cnt][mask]%%'' 表示一个状态是否存在，这样数组很大，会爆。即使后来变成了 ''%%f[last][mask]%%'' 记录最小 ''%%cnt%%''，两个 $2^{15}$ 级别的数也会爆。正解是使用 ''%%f[cnt][mask]%%'' 记录最小 ''%%last%%''，这样由于 ''cnt'' 的级别非常小，整体数组是不会爆的。
+本周冯如杯，没有打比赛。
-===== nikkukun =====
+==== 学习总结 ====
+=== 容斥原理 ===
-[[.:week_summary_1:nikkukun|nikkukun]]
+容斥的一些理解：
+我们能快速知道的是至少满足性质集合 $S$ 的个数 $f(S)$，而很多情况下 $f(S)$ 对相同的 $|S|$ 是相同的，这个时候计算贡献就需要乘上组合数，因为统计的是所有 $|S|$ 相同的贡献 $f(S)$，自然要从所有属性里选择 $|S|$ 种出来枚举。
-===== qxforever =====
+如果要求的是没有任何性质 $S$ 的个数，则为
-[[.:week_summary_1:qxforever|qxforever]]
+$$
+\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}$，即五阶完全图与三阶完全二分图。
+==== 本周推荐 ====
+=== ARC 092 F - Two Faced Edges ===
+[[https://atcoder.jp/contests/arc092/tasks/arc092_d|题目链接]]
+**题意**：给一个 $n$（$\leq 1,000$）个点和 $m$（$\leq 2 \times 10^5$）条边的有向图，求反转每一条边的方向后，整个图的强联通分量是否改变。
+**题解**：$u, v$ 在同一个 SCC 中的充要条件是 $u, v$ 可以相互到达。这题只需要通过讨论两个点的连通情况就能解决。
+此外，本题要求一个“不通过某条边，是否能从 $u$ 走到 $v$”的问题（或者说，是否还有通过其他边到达的方法）。通过依次以每条边作为起点，给当前未访问的点标记最早能到达它的边的编号 $low_i$，再把边的枚举顺序反过来，记录最早能到达它的编号 $upp_i$。这相当于说，对一个点 $i$，边 $[low_i, upp_i]$ 中存在边可以到达，只要区间长度不小于 $1$，就有两条以上的方法可以到达。
+这个思路可以用于寻找“是否有一种以上的方案选择”的问题。
+===== 个人训练 - qxforever =====
+==== 比赛 ====
+.05.01 [[.:qxforever:codeforces_round_638_div._2|Codeforces Round #638 (Div. 2)]]
+.05.03 [[.:qxforever:qkoi_r1|QkOI Round1]]
+==== 学习总结 ====
+无
+==== 本周推荐 ====
+[[2020-2021:teams:i_dont_know_png:qxforever:qkoi_r1#E|[QkOI#R1] E Quark and Game]] 想不到
+===== 个人训练 - Potassium =====
+==== 比赛 ====
+无
+==== 学习总结 ====
+=== 莫比乌斯反演 ===
+莫比乌斯反演：$g(n)=\sum_{d|n}f(d)$，则$f(n)=\mu *g$
+$\epsilon(i)=[i=1]$在积性函数里扮演了类似于自然数中$1$的角色，为什么让$\epsilon$扮演自然数中$1$的角色呢，因为$(f*\epsilon)(n)=\sum_{d|n}f(\frac nd)\epsilon(d)=f(n)$。
+$$id(i)=i$$
+$$1(i)=1$$
+$$\phi(i)=\text{多少个<i且与i互质}$$
+$$d(i)=i \text{约数个数}$$
+$$\sigma(i)=i \text{约数个数和}$$
+设$n=\sum_{i=1}^{m}p_i^{k_i}$，则
+$$\mu(n)=\left\{\begin{aligned}&1,&n=1\\&(-1)^m,&\forall _ik_i=1\\&0,&\exists_ik_i\geq2 \end{aligned}\right.$$
+狄利克雷卷积中，$1$的逆是$\mu$，即$1*\mu=\epsilon$。
+这很容易理解：对$(1*\mu)(n)$作出贡献的仅有**$n$的质因数的乘积**和**$1$**。
+对于$n$的质因数，如果$n$有$m\geq 1$个质因数，那它就有$m$个“一个质因数的积”，$C_{m}^{2}$个“两个质因数的积，…，他们卷起来的和是
+$$C_m^1+(-1)\cdot C_m^2+(-1)^2\cdot C_m^3+...+(-1)^mC_m^{m}=(1+(-1))^m-1$$
+加上$1$的贡献，即为$0$。
+所以只有当$n=1$的时候$(1*\mu)(n)$才为$1$，故$1*\mu=\epsilon$。
+通过这个我们很容易推出莫比乌斯反演：$g=f*1$，所以$f=g*\mu$。
+然后就是一些常见的结论：
+$d=1*1$（枚举约数，对$1$求和）
+$\sigma=d*1$（枚举约数，对约数求和）
+$id=1*\phi$（枚举约数，每个约数求出小于他且与他互质的个数，即求这个约数为分母的真分数个数，它们的和必为$n$，例子见下：
+$$\frac 1{12}\frac 2{12}\frac 3{12}\frac 4{12}\frac 5{12}\frac 6{12}\frac 7{12}\frac 8{12}\frac 9{12}\frac {10}{12}\frac {11}{12}\frac {12}{12}$$
+可以化简为
+  * $\frac 1{12},\frac 5{12},\frac 7{12},\frac{11}{12}$（$\phi(12)=4$）
+  * $\frac 1{6},\frac 5{6}$（$\phi(6)=2$）
+  * $\frac 1{4},\frac 3{4}$（$\phi(4)=2$）
+  * $\frac 1{3},\frac{2}{3}$（$\phi(3)=2$）
+  * $\frac 12$（$\phi(2)=1$）
+  * $\frac 11$（$\phi(1)=1$）
+根据$id=1*\phi$，有$\phi=id*\mu$。
+题目略（摸了，下次再补）
+常用套路：$\sum_{i}\sum_{j}f(i,j)$变换为$\sum_{k}\sum_{i}\sum_{j}[f(i,j)=k]$这样拆出来，比如$f(i,j)=\gcd(i,j)$的时候拆出来比较容易进行反演之类的操作。
+=== 组合数学 ===
+需要注意的一个式子：$\sum_{i=L}^{R}C_{i}^{x}=C_{R+1}^{x+1}-C_L^{x+1}$。其实就是对$C_i^x=C_{i+1}^{x+1}-C_{i}^{x+1}$求和。
+==== 本周推荐 ====
+=== CF994F Compute Power ===
+[[https://codeforces.com/contest/994/problem/F|题目链接]]
+**题意**：$n\leq 50$个任务，每个任务$a,b$两个属性$(1\leq a_i\leq 10^8,1\leq b_i\leq 100)$。有一些机器，每台机器可以执行最多两次任务，执行两次的时候要求第二个任务比第一个任务的$a$小。设第一次执行任务的集合为$S$，最小化$\frac{\sum_{i\in S}a_i}{\sum_{i\in S} b_i}$。
+**题解**：根据01分数规划套路，二分答案$m$，即求${\sum_{i\in S}a_i-mb_i}\leq 0$能否满足。按$a$从大到小、$a-mb$从大到小排序，合并一下$a$相同的项（可以在$dp$的时候进行这一步，要记录第$i$项开始与第$i$项的$a$相同的元素有$cnt_i$个），按顺序枚举，分别加入$S$或补集$C_US$，有任意时刻$S$中元素多于$C_US$。于是设$f[i][j]$表示到$i$，有$j$个分配到$1$且可用（可分配一个$2$）的任务的最小值，则对于一个$i$，枚举分配给第二个任务的个数$k\in[0,cnt_i]$，有
+$$f[i][j+(cnt_i-k)-k]=\min(f[i][j+(cnt_i-k)-k],f[i-1][j]+\sum_{l=i+k}^{i+cnt_i-1} (a_l-m\times b_l))$$
+这题需要记录的地方在于，将相同的项合并，从而简化$dp$过程。
-===== Potassium =====
-[[.:week_summary_1:potassium|Potassium]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具