2021-team02-007

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team02 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 流水账 =

~~这里是流水账~~

= 总结 =

=== pb： ===
TODO：

1. 补 G √，但是我是笨蛋


=== Creatix： ===
TODO：

1. 学拟阵 √（？）

2. 补 I √

3. ~~补 H~~

----

拟阵是一个空间 (E, I)，其中 E 是一个集合，I 是 E 的子集的集合（预先使用之后才被定义的名词：I 是 E 的独立集的集合）。

我们称其为拟阵，当且仅当以下三条性质得到满足：

I1. 空集属于 I，或者说空集是独立集。

I2. 独立集的子集是独立集。

I3. 如果 A 和 B 都是独立集且 A 的元素个数比 B 多，那么存在 x 属于 A \ B 使得 B ∪ {x} 是个独立集。

一个元素个数最多的独立集被称为矩阵的一组基。

----

我们可以给一个集合定义权函数 W(A) 为：W(A) = \sum_{a \bel A} w(a)。

结论 1：在这个新的结构（E, I, W) 下，如果我们需要找到最大权的独立集，我们只需维护一个集合，每次加入权值最大的、不会导致集合不独立的元素即可。

例子：用拟阵证明最小生成树算法。

在这里，E 表示整个边集，独立集被定义为能构成森林的边集，则基表示能构成树的集合，而权函数 w 就是边权，W 就是边集中所有边的边权。

想求最小生成树，我们只需要按边权从小到大的顺序尝试加入边即可。

----

关于结论 1 的证明：

基具有以下两条性质（容易由独立集的性质得出）

B1. 任意拟阵至少存在一个基。

B2. 对于任意两个不同的基 A，B，对于任意 a 属于 A \ B，存在 b 属于 B \ A，使得 A \ {a} ∪ {b} 也是一个基。

另外，容易发现所有基的大小都是相同的，我们称一个子集的基的大小为它的 rank。

有了这些性质，我们再来考虑上文所说贪心的正确性。

假设我们通过这个贪心所求出来的基为 A，那么对于任意一个不同的基 B，我们取 m 为 A \ B 中权值最大的元素，

取独立集 C = {x 属于 A | w(x) >= w(m)}，D = B \ (C \ {m})

根据前面的贪心，w(m) 一定不小于比 D 中的任意元素的权。

所以，我们利用性质 I3，每次用 B 独立集来拓展 C 独立集，直到 C 独立集变成一个基 C'。

此时容易发现，C' 独立集的权值不小于 B。我们用 C' 替换 B。

重复这个步骤有限次后，我们得到的独立集会和 A 完全相等。即，W(A) >= ...  >= W(C') >= W(B) 

----

=== Eden_CY： ===
TODO：

1. 补 B √


= 题解 =

 * A：

 * B：预处理每个圆要积分的O(n)个的段，询问时枚举每个圆二分位置，分类讨论。

 * C：二分答案

 * D：简单dp

 * E：简单dp

 * F：

 * G：

 * H：

 * I：注意判 -1

 * J：

 * K：

 * L：

 * M：

[/wiki/2021-team02 返回]

流水账

这里是流水账

总结

pb：

TODO：

1. 补 G √，但是我是笨蛋

Creatix：

TODO：

1. 学拟阵 √（？）

2. 补 I √

3. 补 H

---

拟阵是一个空间 (E, I)，其中 E 是一个集合，I 是 E 的子集的集合（预先使用之后才被定义的名词：I 是 E 的独立集的集合）。

我们称其为拟阵，当且仅当以下三条性质得到满足：

I1. 空集属于 I，或者说空集是独立集。

I2. 独立集的子集是独立集。

I3. 如果 A 和 B 都是独立集且 A 的元素个数比 B 多，那么存在 x 属于 A \ B 使得 B ∪ {x} 是个独立集。

一个元素个数最多的独立集被称为矩阵的一组基。

---

我们可以给一个集合定义权函数 W(A) 为：W(A) = \sum_{a \bel A} w(a)。

结论 1：在这个新的结构（E, I, W) 下，如果我们需要找到最大权的独立集，我们只需维护一个集合，每次加入权值最大的、不会导致集合不独立的元素即可。

例子：用拟阵证明最小生成树算法。

在这里，E 表示整个边集，独立集被定义为能构成森林的边集，则基表示能构成树的集合，而权函数 w 就是边权，W 就是边集中所有边的边权。

想求最小生成树，我们只需要按边权从小到大的顺序尝试加入边即可。

---

关于结论 1 的证明：

基具有以下两条性质（容易由独立集的性质得出）

B1. 任意拟阵至少存在一个基。

B2. 对于任意两个不同的基 A，B，对于任意 a 属于 A \ B，存在 b 属于 B \ A，使得 A \ {a} ∪ {b} 也是一个基。

另外，容易发现所有基的大小都是相同的，我们称一个子集的基的大小为它的 rank。

有了这些性质，我们再来考虑上文所说贪心的正确性。

假设我们通过这个贪心所求出来的基为 A，那么对于任意一个不同的基 B，我们取 m 为 A \ B 中权值最大的元素，

取独立集 C = {x 属于 A | w(x) >= w(m)}，D = B \ (C \ {m})

根据前面的贪心，w(m) 一定不小于比 D 中的任意元素的权。

所以，我们利用性质 I3，每次用 B 独立集来拓展 C 独立集，直到 C 独立集变成一个基 C'。

此时容易发现，C' 独立集的权值不小于 B。我们用 C' 替换 B。

重复这个步骤有限次后，我们得到的独立集会和 A 完全相等。即，W(A) >= ... >= W(C') >= W(B)

---

Eden_CY：

TODO：

1. 补 B √

题解

• A：
• B：预处理每个圆要积分的O(n)个的段，询问时枚举每个圆二分位置，分类讨论。
• C：二分答案
• D：简单dp
• E：简单dp
• F：
• G：
• H：
• I：注意判 -1
• J：
• K：
• L：
• M：