赛前冲刺日志 | answerend42的Blog

离 noip2020 一个多月的一点学习记录。

2020.10.28

今天的题前四道是二分图和网络流相关的，主要使用了 xht37 的板子，做的也还可以，难点在于二分图的建立和一些细节处理。后四道题是 LCA 和树上差分相关的题目，主要复习了倍增 LCA 的求法以及点差分转边差分，难点在于模型的转化和一些细节处理。可见，图论的题最难的是建图，在实际使用中可以把最大流当做一个黑盒代码使用。

注意

最大流中两个 $n$ 的含义是不一样的，一个可能是行数而不是真正的点数
二分图中如果沿用 $n$ 应当注意，$n$ 是所有点的数量并非一个集合中点的数量
二分图中如果采用 Dinic，最后求和的时候一定要记得循环从 for (int i = 1; i <= n; i++) hi[i] = head[i]; 改为 for (int i = 0; i < T; i++) hi[i] = head[i];
倍增求 LCA 时，应该将较大的开在第一维如 f[N][25]
倍增求 LCA 时，判断条件中 if (dep[f[x][i]] >= dep[y]) 一定不要忘记是大于等于
无向图建图应当开双向边
网络流最初从 $1$ 开始建边

2020.10.29

今天的题目与树链剖分有关，主要参考了 oi wiki。为什么今天只有两道题呢？……因为树剖太难调了
树剖的常数很小，比倍增小很多。而且很适合用来统计树上问题，当然，要注意的地方也不少。

注意

我们需要维护每个结点的父亲、深度、子树大小、重儿子、重链的头、节点的 dfs 序、dfs 对应的节点编号等
第二遍 dfs 的时候一定要记得两个参数都是 v
线段树查询的时候一定要用 ql, qr 作为参数，便于调试
可以考虑精简线段树，不需要用到的可以不写
线段树空间要开到四倍
初始的时候 dep[1] = 1
求 LCA 时，一定是 if (dep[top[u]] > dep[top[v]]) 而不是 if (dep[u] > dep[v]) </span>

又臭又长的代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1;
const int inf = 2e9;
int to[N << 1], nxt[N << 1], x, y;
int n, m, root, tot, head[N], dep[N], siz[N], son[N], top[N], f[N], dfn[N], rnk[N], cnt;
char op[15];
class Tree {
private:
    int ls(int p) { return p << 1; }
    int rs(int p) { return p << 1 | 1; }

public:
    int sum[N << 2], tag[N << 2], maxx[N << 2], a[N];
    void push_up(int p) { sum[p] = sum[ls(p)] + sum[rs(p)], maxx[p] = max(maxx[ls(p)], maxx[rs(p)]); }
    void build(int p, int l, int r) {
        if (l == r) {
            maxx[p] = sum[p] = a[rnk[l]];
            return;
        }
        int mid(l + r >> 1);
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        push_up(p);
    }
    int query1(int p, int l, int r, int ql, int qr) {
        if (l > qr || r < ql)
            return -inf;
        if (ql <= l && r <= qr)
            return maxx[p];
        int mid(l + r >> 1);
        return max(query1(ls(p), l, mid, ql, qr), query1(rs(p), mid + 1, r, ql, qr));
    }
    int query2(int p, int l, int r, int ql, int qr) {
        if (l > qr || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return sum[p];
        int mid(l + r >> 1);
        return query2(ls(p), l, mid, ql, qr) + query2(rs(p), mid + 1, r, ql, qr);
    }
    void update(int p, int l, int r, int x, int t) {
        if (l == r) {
            maxx[p] = sum[p] = t;
            return;
        }
        int mid(l + r >> 1);
        if (x <= mid)
            update(ls(p), l, mid, x, t);
        else
            update(rs(p), mid + 1, r, x, t);
        push_up(p);
    }
} T;
void add(int u, int v) {
    to[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}
void dfs1(int u) {
    son[u] = -1, siz[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (!dep[v]) {
            dep[v] = dep[u] + 1;
            f[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if (son[v] == -1 || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}
void dfs2(int x, int tv) {
    top[x] = tv;
    dfn[x] = ++cnt;
    rnk[cnt] = x;
    if (son[x] == -1)
        return;
    dfs2(son[x], tv);
    for (int i = head[x]; i; i = nxt[i]) {
        int v = to[i];
        if (v != f[x] && v != son[x])
            dfs2(v, v);
    }
}
int querymax(int x, int y) {
    int ret = -inf, fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy])
            ret = max(ret, T.query1(1, 1, n, dfn[fx], dfn[x])), x = f[fx];
        else
            ret = max(ret, T.query1(1, 1, n, dfn[fy], dfn[y])), y = f[fy];
        fx = top[x];
        fy = top[y];
    }
    if (dfn[x] < dfn[y])
        ret = max(ret, T.query1(1, 1, n, dfn[x], dfn[y]));
    else
        ret = max(ret, T.query1(1, 1, n, dfn[y], dfn[x]));
    return ret;
}
int querysum(int x, int y) {
    int ret = 0, fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] >= dep[fy])
            ret += T.query2(1, 1, n, dfn[fx], dfn[x]), x = f[fx];
        else
            ret += T.query2(1, 1, n, dfn[fy], dfn[y]), y = f[fy];
        fx = top[x];
        fy = top[y];
    }
    if (dfn[x] < dfn[y])
        ret += T.query2(1, 1, n, dfn[x], dfn[y]);
    else
        ret += T.query2(1, 1, n, dfn[y], dfn[x]);
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &T.a[i]);
    dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    T.build(1, 1, n);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%s%d%d", op, &x, &y);
        if (!strcmp(op, "CHANGE"))
            T.update(1, 1, n, dfn[x], y);
        if (!strcmp(op, "QMAX"))
            printf("%d\n", querymax(x, y));
        if (!strcmp(op, "QSUM"))
            printf("%d\n", querysum(x, y));
    }
    return 0;
}

2020.10.30

P2680 运输计划

一道题还没做完（

这个题本来自信能 20pts，结果 15 pts，调了一会找不到错误，于是看了看数据发现查询的起点和终点是一个点……

在网上找不到想要的暴力做法，明天可能会自己写一个 60pts 的

code_20pts

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = N * 2, inf = 0x3f3f3f3f;
int n, m;
int tot, to[M], cost[M], nxt[M], head[N], dep[N], f[N][25], d[N], rnk[N];
void add(int u, int v, int w) {
    to[++tot] = v;
    nxt[tot] = head[u];
    cost[tot] = w;
    head[u] = tot;
}
int u, v, w;
vector<pair<int, int> > q;
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for (int i = 1; (1 << i) <= dep[u]; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 24; i >= 0; i--) {
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];
        if (x == y)
            return x;
    }
    for (int i = 24; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
void calc(int u, int fa) {
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        calc(v, u);
        d[u] += d[v];
        rnk[v] = i;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    q.reserve(3005);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        q.push_back(make_pair(u, v));
    }
    assert(!q.empty());
    dfs(1, 0);
    if (m == 1) {
        int x = q[0].first, y = q[0].second;
        if(x == y) return printf("0"),0; // 这个点是真的毒瘤
        d[x]++, d[y]++, d[lca(x, y)] -= 2;
        calc(1, 0);
        int maxx = -inf, ans = 0;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                maxx = max(maxx, cost[rnk[i]]);
                ans += cost[rnk[i]];
            }
        }
        printf("%d", ans - maxx);
    }
    return 0;
}

注意

查询起点和终点的是同一个点要记得特判
calc 中是 rnk[v] = i; 不是 rnk[u] = i;

打了 Codeforces Round #675 (Div. 2) ：

2020.10.31

可以看到，除了三道题是来自原来的任务列表以外，做了四道模板题，按照熟练程度由大到小排序。

注意

线段树

空间要开四倍
下推标记时先加法后乘法

ST表

考虑线性求 log

void pre() {
    Logn[1] = 0,Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}

AC自动机

应当考虑写个函数 rnk 用来求 str[i] - 'a' ，避免 i 和 idx 两个变量混用

2020.11.1

2020.11.2~11.4

sb文化课+月考（