CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020.05.03-2020.05.09 周报 ======

团队周报是怎么回事呢？团队相信大家都很熟悉，但是团队周报是怎么回事呢，下面就让小编带大家一起了解吧。

团队周报，其实就是团队的周报，大家可能会很惊讶团队怎么会周报呢？但事实就是这样，小编也感到非常惊讶。

这就是关于团队周报的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

===== 团队训练 =====

本周无团队训练。

===== 团队会议 =====

2020.5.9 建立[[.:skill_tree|技能树]]，确定[[.:training_plan_2020spring|训练计划]]

===== 个人训练 - nikkukun =====

==== 比赛 ====

本周冯如杯，没有打比赛。

==== 学习总结 ====

=== 容斥原理 ===

容斥的一些理解：

我们能快速知道的是至少满足性质集合 $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}$，即五阶完全图与三阶完全二分图。


==== 本周推荐 ====


=== 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 =====


==== 比赛 ====

2020.05.01 [[.:qxforever:codeforces_round_638_div._2|Codeforces Round #638 (Div. 2)]]

2020.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$过程。
CVBB ACM Team

用户工具

站点工具

页面工具
