玖的数学&算法录

并查集

并查集是一种树形数据结构，经常用于处理集合之间的操作（如元素查找、集合合并。

n元素，m次查询

复杂度：O(m)，最坏复杂度：O（mlogn)

并查集初始化

1
2
3
4
5
6

void init(int n) {
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = dep[i] = 1;
    }
}

集合合并

讲元素x,y所在的集合合并。

首先先找到 x,y 对应的代表元 （fa 等于自己的元素）

将其中一个代表元的 fa 指向另外一个，那么原来在这个代表元下的所有元素的代表元都会指向另外一个。

1
2
3
4
5
6
7
8
9
10
11

int Findset(int x) {
    if(fa[x] == x) return x;
    return Findset(fa[x]);
}

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    fa[fx] = fy;
}

路径压缩

通过缩短并查集的路径，具体是查询过程中，把沿途的每个节点的 fa 都设为集合代表元。

1
2
3
4
5

int Findset(int x) {
   if(x == fa[x]) return x;
   fa[x] = Findset(fa[x]);
   return fa[x];
}

或者

1
2
3

int Findset(int x) {
   return x == fa[x] ? x : (fa[x] == Findset(fa[x]));
}

启发式合并

合并两个集合优化的方法。

在合并集合的时候，我们尽量选择包含元素个数少的集合，将它合并到另一个集合中，使需要改变代表元的元素数量尽可能少。

小集合合并到较大集合称为启发式合并。

时间复杂度：log

1
2
3
4
5
6
7
8

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(sz[fx] > sz[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    sz[fy] += sz[fx];
}

按深度合并

深度小的集合合并到深度大的一方。

时间复杂度：log

路径压缩过程中，有可能破坏我们维护的深度值，但总体复杂度不会差。

1
2
3
4
5
6
7
8
9

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(dep[fx] > dep[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    if(dep[fx] == dep[fy]) //只有两棵树深度相等时才会更新
        dep[fy]++;
}

数分每日一题

8.1

Fejer积分

记

$$\displaystyle I_n = \int_{0} ^ \frac{\pi}{2}(\frac{\sin nx}{\sin x})^2\mathrm{d}x$$

证明

$$\displaystyle I_n = \frac{n \pi}{2}$$

prove:

$$\displaystyle I_n - I_{n - 1} = \int_{0} ^ {\frac{\pi}{2}}\frac{\sin ^ 2 nx - \sin^2{(n-1)x}}{\sin ^2 x}\mathrm dx$$

$$\displaystyle =\frac{1}{2} \int_{0} ^ \frac{\pi}{2} \frac{\cos(2n - 2)x - \cos 2nx}{\sin ^ 2x}\mathrm dx$$

$$\displaystyle = \int_{0} ^ \frac{\pi}{2} \frac{\sin (2n - 1)x}{\sin x}\mathrm dx = J_{n}$$

$$\displaystyle J_n - J_{n-1} = \int_0^\frac{\pi}{2} \frac{\sin(2n - 1)x - \sin(2n - 3)x}{\sin x}\mathrm dx$$

$$\displaystyle = \int_0^\frac{\pi}{2} \frac{2\sin\frac{2n - 1 -(2n - 3)}{2} x \cdot \cos \frac{(2n - 1 ) + (2n - 3)}{2}x}{\sin x}\mathrm dx$$

$$\displaystyle = 2\int_0^\frac{\pi}{2} \cos(2n - 2)x \mathrm dx = 0$$

即得出

$$J_n = J_{n-1} = \cdots = J_{1}$$

又

$$\displaystyle J_1 = \int_{0}^\frac{\pi}{2} \mathrm dx = \frac{\pi}{2} , I_1 = \frac{\pi}{2}$$

因此由等差数列求和公式得出

$$\displaystyle I_n = I_1 + (n - 1)\cdot \frac{\pi}{2} = \frac{n\pi}{2}$$

8.2

IMC 2022 Day1 problem1

Problem 1 : Let f :[0,1]->(0,∞) be an integrable function such that f(x) · f(1-x) = 1 for all x ∈ [0,1]. Prove that

$$\displaystyle \int_0^{1} f(x)\mathrm{d}x \geq 1$$

译：设**f[0,1] -> (0,+∞)**是一个可积函数，满足f(x)f(1-x) = 1，对于所有x∈[0,1],证明：

$$\displaystyle \int_0^{1} f(x)\mathrm{d}x \geq 1$$

Prove1:

由 AM-GM 不等式得

$$\displaystyle f(x) + f(1-x) \geq 2\sqrt{f(x)f(1-x)}=2$$

同时我们考虑

$$\displaystyle \int_0^{1}f(x)\mathrm{d}x = \int_0^\frac{1}{2}f(x)\mathrm{d}x+\int_0^\frac{1}{2}f(1-x)\mathrm{d}x$$

$$\displaystyle =\int_0^\frac{1}{2}(f(x)+f(1-x))\mathrm{d}x\geq\int_0^\frac{1}{2}2\mathrm{d}x=1$$

Prove2:

注意到:

$$\displaystyle \int_0^1 f(x)\mathrm{d}x=\int_0^1 f(1-x)\mathrm{d}x =\int_0^1\frac{1}{f(x)}\mathrm{d}x$$

所以有

$$\displaystyle (\int_0^1 f(x)\mathrm{d}x)^2 = \int_0^1 f(x)\mathrm{d}x\cdot\int_0^1\frac{1}{f(x)}\mathrm{d}x \geq (\int_0^1 1\mathrm{d}x)^2\geq1$$

8.3

3