2020 ICPC Template

数学

快速幂

  1. 求 b^p mod k
  2. 将 p 按照二进制切开,与 b 的二进制倍增次方 相乘。
ll quick_pow(ll b, ll p, ll k) {
    ll ans = 1, base = b;
    while (p > 0) {
        if (p & 1) {
            ans *= base;
            ans %= k;
        }
        base *= base;
        base %= k;
        p >>= 1;
    }
    return ans % k;
}

素数筛(欧拉筛)

  1. 求 n 内所有素数
  2. prime[] 0 表示是素数,1 表示非素数
  3. ans[] 从 [1, ans] 由小到大存储 n 以内所有素数
bool prime[N];
int ans[N], sum = 0;

void isprime(int n) {
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) ans[++sum] = i;
        for (int j = 1; j <= sum && i * ans[j] <= n; j++) {
            prime[i * ans[j]] = 1;
            if (i % ans[j] == 0) break;
        }
    }
}

常用常数

const long double pi = acos(-1); /// 圆周率

数据结构

树状数组

  1. 树状数组本质是log修改,log查询的前缀数组。
  2. 区域修改,单点查询维护的是差分数组。
ll a[maxn], tr[maxn];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, ll k) {
    while (x <= n) {
        tr[x] += k;
        x += lowbit(x);
    }
}

inline ll query(int x) {
    ll ans = 0;
    while (x > 0) {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

ST 表

  1. 查询 [1, n] 范围内任意区间的区间最值(RMQ问题),可以解决重复贡献问题(GCD)
  2. O(nlogn)建表,O(1)查询
  3. st[i][j] 表示从 i 开始 2 ^ j 个数的最值
int a[maxn];
int st[maxn][18];
// st[i][j] 表示从 i 开始 2^j 个数的最值
// 2^16 < 1e5 < 2^17
// st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
    // x + (1 << k) - 1 = r
    // x = r - (1 << k) + 1
}

// 建表方法
for (int i = 1; i <= n; i++) st[i][0] = a[i];
for (int j = 1; j < 18; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

图论

链式前向星

  1. 使用前要先将 head[] 进行初始化,全为 -1
  2. 遍历顺序为存边顺序的倒序
int head[N], cnt = 0;
struct edge {
    int to, len, nxt;
} edge[M];

inline void add_edge(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].len = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    cnt++;
}

for (int i = head[t.idx]; i != -1; i = edge[i].nxt) {
    // 遍历方式
}

树上问题

树的直径

求树上任意两个点之间最大的距离。

正解:两遍DFS,第一遍从任意一点找最远的点,这个点一定是直径的一端,第二遍从这一点再找最远的点,即为树的直径。

单源最短路 (dijkstra)

  1. 配合上文链式前向星使用
  2. 每个点只能参与优化一次,使用 vis[] 数组记录
  3. 使用优先队列存结构体方式模拟小根堆,STL中中优先队列默认大值优先,注意结构体中的运算符重载
struct node {
    int idx;
    ll len;

    bool operator<(const node &a) const {
        return len > a.len;
    }
};

ll dis[N];
int vis[N];

void dijkstra() {
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0;
    priority_queue<node> pq;
    pq.push(node{s, 0});
    while (!pq.empty()) {
        node t = pq.top();
        pq.pop();
        if (vis[t.idx]) continue;
        vis[t.idx] = 1;
        for (int i = head[t.idx]; i != -1; i = edge[i].nxt) {
            if (dis[edge[i].to] > t.len + edge[i].len) {
                dis[edge[i].to] = t.len + edge[i].len;
                pq.push(node{edge[i].to, dis[edge[i].to]});
            }
        }
    }
}

最小生成树 (Kruskal)

  1. n 点图若有最小生成树,一定为 n - 1 条边
const int N = 5005;
const int M = 2e5 + 5;

int n, m;

struct edge {
    int u, v, w;
    bool operator<(const edge &a) const { return w < a.w; }
} e[M];

int fa[N];

inline int find(int x) {
    while (fa[x] != x) x = fa[x] = fa[fa[x]];
    return x;
}

inline void merge(int x, int y) {
    x = find(x), y = find(y);
    fa[y] = x;
}

int main() {
    read(n), read(m);
    for (int i = 0; i < m; i++) read(e[i].u), read(e[i].v), read(e[i].w);
    sort(e, e + m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    ll ans = 0;
    for (int i = 1, j = 0; i < n; i++) {
        while (find(e[j].u) == find(e[j].v)) {
            j++;
            if (j == m) {
                printf("orz");
                return 0;
            }
        }
        merge(e[j].u, e[j].v);
        ans += e[j].w;
    }
    write(ans);
    return 0;
}

动态规划

区间 DP

for (i: 区间长度) {
    for (j: 起点) {
        ...
    }
}

STL 相关

函数

容器

优先队列

priority_queue<int> p; //默认大根堆
priority_queue<int, deque<int>, greater<int> > p; //小根堆

双向队列

  1. 常用 双向队列 来模拟 单调队列
deque<pair<int, int> > d;

d.empty();      // 队列是否为空
d.front();      // 队列中最先入队的元素
d.back();       // 队列中最后入队的元素
d.push_fornt();
d.push_back();
d.pop_front();
d.pop_back();  

bitset

可以当做 bool 数组使用,节省空间

bitset<N> prime; // N 表示开的大小
Last modification:December 23rd, 2020 at 03:36 pm
如果觉得我的文章对你有用,请随意赞赏