标签： 算法模板

题目

题目传送门: 【P3373】【模板】线段树 2 – 洛谷

如题，已知一个数列，你需要进行下面三种操作：
1. 将某区间每一个数乘上 $x$。
2. 将某区间每一个数加上 $x$。
3. 求出某区间每一个数的和。 继续阅读 »

题目传送门: 洛谷 P3369、LibreOJ #104、BZOJ 3224

我们需要实现一种数据结构，实现以下操作。
1. 插入 $ x $ 数；
2. 删除 $ x $ 数（若有多个相同的数，因只删除一个）；
3. 查询 $ x $ 数的排名（若有多个相同的数，因输出最小的排名）；
4. 查询排名为 $ x $ 的数；
5. 求 $ x $ 的前趋（前趋定义为小于 $ x $，且最大的数）；
6. 求 $ x $ 的后继（后继定义为大于 $ x $，且最小的数）。 继续阅读 »

图的存储与一般有三种形式，邻接矩阵、邻接表、链式前向星（邻接表的一种）。
本文全文使用这个图来进行演示。

我们规定，一共有 $n$ 个点，$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:

1 2 2
1 4 3
2 3 1
2 5 3
3 1 2
5 3 2
5 4 4

邻接矩阵

由于邻接矩阵空间消耗巨大，一般不使用。
邻接矩阵初始化时，我们使用无穷。

因为对于有些题目，存在瞬移术，可以将某个权重的边跳过，这时可以把它的边权设为 0，这样就和不连通的情况产生了冲突，因此，就不能使用 0 为初值，当然，对于不存在这种情况的题目，仍可使用 0。
对于这个图，其邻接矩阵为：

邻接矩阵的实质，就是用元素的有无来判断两个点是否连通。
因此，邻接矩阵的遍历效率很低，空间开销也很大，而且不能存储重边，可以存储自环(不过好像用处不大)。
建图、存储的时间复杂度为 $\text{O}(n^2)$ (若初始化为 $0$ 则为 $O(m)$ 的时间复杂度)，空间复杂度为 $\text{O}(n^2)$。
遍历的时间复杂度为 $\text{O}(n^2)$。
模板如下： 继续阅读 »

扩展欧几里得

int gcd(int const a, int const b) {
    return !b ? a : gcd(b, a % b);
}

int lcm(int const a, int const b) {
    return a / gcd(a, b) * b;
}

int exgcd(int const a, int const b, int &x, int &y) {
    int ans = a;
    if (b == 0) {
        x = 1, y = 0;
        return ans;
    }
    else {
        ans = exgcd(b, a % b, y, x);
        y -= x * (a / b);
        return ans;
    }
}

欧拉筛

bool is_prime[MAXN];
int primes[MAXN], query[MAXM];
int n, m, p;

void sieve(int const n) {
    memset(primes, 0, sizeof(primes));
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[p++] = i;
        }
        for (int j = 0; j < p && i * primes[j] <= n; j++) {
            is_prime[ i * primes[j] ] = false;
            if (! (i % primes[j]) )
                break;
        }
    }
}