图的存储与遍历

图的存储与一般有三种形式,邻接矩阵、邻接表、链式前向星(邻接表的一种)。 本文全文使用这个图来进行演示。 图示 我们规定,一共有 $n$ 个点,$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:

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

邻接矩阵

由于邻接矩阵空间消耗巨大,一般不使用。 邻接矩阵初始化时,我们使用无穷。 继续阅读 »

欧几里得算法、欧拉筛模板

扩展欧几里得

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

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
        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
                break;
        }
    }
}

2018 NOIP 青岛冬令营行记

第一次参加这种集训呢…… 也许我退役之后,会更加怀念这段时光呢。

Day 0

从临沂到青岛的路上真心体会到了车内缺氧的环境有多么的可啪,头晕晕的 qwq…… 路上看到工厂冒出来的浓浓的白烟,真心感觉我们国家的环境保护还是有点不够。虽然不是黑烟了,但是那里的天空的颜色都已经失去了原本的蓝色。 Smoke Day 0 也就是正式开始的前一天,被老唐指定为组长还是挺有意思的,只是没有想到组长的活竟然这么麻烦。 在海大的学术交流中心里面住宿。分套房的时候是让自己分的哇,必须好评!和 dzy 两人住一间屋甚是愉快啊! 继续阅读 »

栈与队列的基础实现

之前学习栈和队列就不是很系统,这会趁着有时间赶紧补一补。

栈 (stack) 是一种“先入后出”的数据结构。栈的基本结构类似洗盘子,你必须把上面的盘子全部移走,才能够取得下面的盘子。栈的图解如下: stack picture 可以看出,栈由两部分组成,数据和栈指针。 在 C++ 中,我们一般通过数组模拟来实现栈。 栈的类型声明如下: 继续阅读 »