ACM►数据结构►虚树

虚树小结

虚树

据说虚树的英文是叫 Auxiliary tree，简单的来说是维护树上仅于题目有关的信息，除去掉冗余信息以保证时间复杂度的一种算法。为什么说是虚树呢，是因为他是在原来树的基础上建出的一颗全新的树，需要重新建边或分配点权等信息。

虚树的题目通常是这样的，给出一颗大小为 n 有边权或点权的树，然后有 q 次询问，每次给出 $k_i$ 个关键点，要求计算关于这 k 个点的问题（通常和 LCA 有关），但是 $\sum k_i$ 又比较小（通常和树的大小同阶）。

假设你可以 $O(n)$ 的在树上解决单次的询问，那么总时间复杂度是 $O(nq)$ 的，问题的 n 和 q 一般为 $10^5$ 显然这样是不可以过这道题的。这时候就需要用到虚树了，使用虚树我们对于每个询问都可以 $O(k_i)$ 的建出一颗有 $O(k_i)$ 个节点的树，并且可以通过这棵树 $O(k_i)$ 的计算出答案。

BZOJ 2886

给出一颗 n 个节点的树，每条边有正边权，有 q 次询问，每个询问包含 $k_i$ 个选中的点，要求选出一些边使得去掉这 k 条边后 1 号节点不与这 k 个点中的任一个连通。

$ 1 \le n \le 250000, \sum k_i \le 5 \times10^5$

分析

对于每次询问，我们首先考虑 $O(n)$ 的做法，我设 $dp[u]$ 是使得 u 节点及其子树中所有选中的点与 u 的父亲断开的最小花费，我们考虑接下来两种转移；

如果 u 号节点是选中的点的话，那么肯定要断开 u 号点到父亲的边，并且为了让花费最少 u 的子树中不需要断开其他边了。

如果 u 号节点不是选中的点，那么如果我们不断开从 u 到其父亲的边的话，那么我们需要保证 u 的子树中所有的选中的点不与 u 连通，那么 $dp[u] = \sum dp[v]$，v 是 u 的所有的儿子。

虚树优化

接下来我们考虑这个 DP，对于树上一条没有分叉的链，我们如果要断开这条链的话我们肯定要断开这条链上的边权最小的边。仔细分析的话会发现，对于这个问题的每次询问，其实只和选中的 $k_i$ 个点及他们之间两两的 LCA 有关。

思考到这一步，并且会虚树的话，这个题已经解决了。虚树可以对某些关键点求出其两两的 LCA，并且有证明给出，k 个点的两两求 LCA，得出的不同的点的数量是 $O(k)$ 的。

虚树构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//储存关键的点及其 dfs 序
vector<pair<int, int> > imp;
//虚树上的边
vector<int> G[MAX];
//构建虚树时用到的栈
int s[MAX], s_top;

void build() {
    //按照 dfs 序排序
    sort(imp.begin(), imp.end());
    //为了方便处理，我们把树根固定当做关键点
    s[s_top = 1] = 1;

    //按照 dfs 序遍历每个点
    for (int i = 0; i < imp.size(); i++) {
        //求出当前节点与栈顶节点的 LCA
        int v = imp[i].second;
        int t = lca(v, s[s_top]);
        // t 的 dfs 序肯定小于等于栈顶元素的 （因为他是 v 和栈顶元素的 LCA）
        while (dfn[t] < dfn[s[s_top]]) {
            //直到栈顶的元素的前一个元素的 dfs 序小于当前的 LCA，停止循环，如果当前的 LCA 不在栈中，那么入栈
            if (dfn[t] >= dfn[s[s_top - 1]]) {
                G[t].push_back(s[s_top]);
                if (s[--s_top] != t) s[++s_top] = t;
                break;
            }
            //进入循环以为着栈顶元素 dfs 小于当前的 LCA，并且我们是按照 dfs 序遍历的，那么栈顶元素的子树肯定已经构建完毕，需要出栈并对当前的 LCA 建边
            G[s[s_top - 1]].push_back(s[s_top]);
            s_top--;
        }
        s[++s_top] = v;
    }
    //最后对栈中的元素依次建边
    while (s_top--) G[s[s_top]].push_back(s[s_top + 1]);
}

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAX = 250000 + 100;

struct Edge {
    int u, v, w, nxt;
} edge[MAX * 2];

int head[MAX], etot;
int n;

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

vector<pair<int, int> > imp;

int dfn[MAX], clo;
int f[MAX][20], dep[MAX];
ll pre[MAX][20];

void dfs(int u, int fa, int depth) {
    dfn[u] = ++clo;
    f[u][0] = fa;
    dep[u] = depth;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (dfn[v]) continue;
        pre[v][0] = edge[i].w;
        dfs(v, u, depth + 1);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int i = 0; i < 20; i++) if (diff >> i & 1) u = f[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}

ll get_pre(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    ll ans = 1e18;
    for (int i = 0; i < 20; i++)
        if (diff >> i & 1) {
            ans = min(ans, pre[u][i]);
            u = f[u][i];
        }
    return ans;
}

void init() {
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
            pre[j][i] = min(pre[f[j][i - 1]][i - 1], pre[j][i - 1]);
        }
    }
}

bool ojbk[MAX];

vector<int> G[MAX];
vector<int> occur;

int s[MAX], s_top;

void build() {
    sort(imp.begin(), imp.end());

    s[s_top = 1] = 1;
    occur.push_back(1);

    for (int i = 0; i < imp.size(); i++) {
        int v = imp[i].second;
        int t = lca(v, s[s_top]);
        occur.push_back(v);
        occur.push_back(t);

        while (dfn[t] < dfn[s[s_top]]) {
            if (dfn[t] >= dfn[s[s_top - 1]]) {
                G[t].push_back(s[s_top]);
                if (s[--s_top] != t) s[++s_top] = t;
                break;
            }
            G[s[s_top - 1]].push_back(s[s_top]);
            s_top--;
        }
        s[++s_top] = v;
    }
    while (s_top--) G[s[s_top]].push_back(s[s_top + 1]);
}

ll dp[MAX];

void dfs(int u, ll pre) {
    dp[u] = pre;
    ll sum = 0;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        dfs(v, get_pre(u, v));
        sum += dp[v];
    }
    if (!ojbk[u]) dp[u] = min(dp[u], sum);
}

void magic() {
    build();
    dfs(1, 1e18);
    for (int i = 0; i < occur.size(); i++) {
        G[occur[i]].clear();
        ojbk[occur[i]] = false;
    }
    occur.clear();
}


int main() {
    memset(pre, 0x3f, sizeof(pre));
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs(1, 0, 0);
    init();
    int m;
    scanf("%d", &m);
    while (m--) {
        imp.clear();
        int k;
        scanf("%d", &k);
        for (int i = 1; i <= k; i++) {
            int t;
            scanf("%d", &t);
            ojbk[t] = true;
            imp.push_back(make_pair(dfn[t], t));
        }
        magic();
        printf("%lld\n", dp[1]);
    }
}
历程

2018邀请赛总结（陕西）

热身赛

首先看的 A 题，这个题目有问题，最后讨论区更正了下题面后才 AC，弄得心态有点不好。

B 题刚开始理解错了题意，当成了 2-SAT 问题，后来发现有 20 多个队伍 A 了，重新看了下觉得应该是是个简单题就随便写写 A 了，不想写并查集强行 DFS 染色 + 二分。

C 刚开始没给数据范围，给出数据范围后一眼看过去就是状压 DP（听说还有其他更优秀的做法），最后统计答案的时候换了个方式，比赛结束 5 分钟前 A 了。

最后看了下榜，全场做出三题的队伍只有10 个（我们是第 10 个），已经很开心了，幻想着明天正式赛也这个成绩就很 OK 了。

正式赛

首先看的 E 题，很显然的一个几何的结论三分钟 A 了。

然后看的 A 题，猜了个显然不对的做法，WA 一次，然后和 szq 讨论后又写了一个优化版的做法，还是 WA，最后又讨论了下，算是推出来了出题人认为的正解，不过这个题目出错了，在我们推出来正解后讨论区裁判公布了正解。算是可惜了两发罚时，不过裁判组处理也是比较得当，如果不这样的话会有好多有水平的队伍卡在 A 题。

在我敲 A 题的时候 szq 就已经在看 D 题，看上去就是 nim 博弈的变种，推出来 SG 函数就基本上做出来的了，不过他没有打好表，还是我上去记忆化搜索一波后打出来表，规律非常显然，出了个小失误 WA 一发后就 AC 了。

然后 lxw 告诉我了下 B 题（最后也没写出来）的题意后我就去看 K 了，这里我大概敲了一个小时，思路越敲越乱，大概浪费了一个多小时，最后 szq 说他有一个比较简单的做法，我就让开机位去让他敲了，自己去洗了把脸清醒一下…最后 szq 写完调试了半个小时多才 A 掉这个题，算是这次比赛里面最大的失误了。

之前看榜上有好多人过了 G 题，并且 szq 和 lxw 已经讨论出来了这是一个简单的板子题，于是 A 完 K 题后直接去做 G 题了，敲完板子后一直 WA，最后我打印代码让他们两个看，去敲了 C 题，C 题在 szq 敲 K 题的时候我已经和 lxw 讨论的差不多了。

最后实在没找到其他的错误，于是只好试试改精度，然后改完之后 G 题居然 AC 了，随后我敲完 C 题过了样例也顺利 1A 了。

这时候刚好封榜，只有一个小时剩余的时间了，看榜上其他有人做出来的题只有 B 和 H 题，F 题只有 GDUT 穷游中国做出来了，感觉可能比较难，于是就去做 B 题了（后来发现这个是错误选择）。

最后让 lxw 读出来了 H 题的题目，B 和 H 最后也没有思路。

比赛后听他们讨论说封榜前没人过的 I 和 J 题都是数据结构的模板题，感觉自己没看有点可惜。

总结

排除省赛拿的金牌之后，这算是自己摸到的第二块金牌，本以为邀请赛没有那么正式，结果主办方办的规模和区域赛差不多。这次邀请赛好多强校没有来，比如清华北大复旦等，基本上他们每来一个队伍我们排名都要加一的。这个结果自己还是挺满意的，颁奖的时候读完银牌没有自己的时候感觉非常开心。另外就是终于能打得过山大一次了，去年区域赛一直都是被山大的骑士王的荣耀队碾压的，一直定为打不过的队伍…

接下来的基本目标是区域赛金牌，努力打进 Final！

ACM►数据结构►树

树分治小结

分治

首先树分治是一种在树上的分治算法，分为点分治和边分治，边分治不常见并且不能保证复杂度，所以没学。那么对于点分治，核心实现是每次选取一个点当做根节点，然后解决根节点的问题，再去递归到每个子树去解决子树的问题。

分治的一个核心在于根据树的重心去划分递归子树，重心是树上的一个点，删去这个点后剩下的最大的子树最小。可以保证删去这个点后剩下的所有子树的大小不会超过原来的一半。由此保证递归深度至多 $\log n$ 层，如果解决每层的问题需要 $O(n)$，那么总时间复杂度是 $O(n\log n)$。

两道例题

POJ 1741

给出一棵树，每条边有边权，设树上任意两点 $u, v$ ($u\neq v$)的最短距离为 $dist(u,v) $ 问有多少个序偶 $(u, v)$ 使得 $dist(u, v) \le K$。

节点数不超过 $10^4$，边权不超过 $10^3$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int MAX = 112345;

int n, K;
vector<pair<int, int> > edge[MAX];

int size, root, ans;
int num[MAX], max_son[MAX], depth[MAX];
bool done[MAX];
vector<int> dep;

void get_root(int u, int fa) {
    max_son[u] = 0;
    num[u] = 1;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        if (done[v] || v == fa) continue;
        get_root(v, u);
        num[u] += num[v];
        max_son[u] = max(max_son[u], num[v]);
    }
    max_son[u] = max(max_son[u], size - num[u]);
    if (max_son[u] < max_son[root]) root = u;
}

void get_dep(int u, int fa) {
    dep.push_back(depth[u]);
    num[u] = 1;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        int w = edge[u][i].second;
        if (done[v] || v == fa) continue;
        depth[v] = depth[u] + w;
        get_dep(v, u);
        num[u] += num[v];
    }
}

int calc(int u, int init) {
    dep.clear();
    depth[u] = init;
    get_dep(u, 0);
    sort(dep.begin(), dep.end());
    int rst = 0;
    for (int l = 0, r = dep.size() - 1; l < r;) {
        if (dep[l] + dep[r] <= K) rst += r - l++;
        else r--;
    }
    return rst;
}

void solve(int u) {
    ans += calc(u, 0);
    done[u] = true;
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i].first;
        int w = edge[u][i].second;
        if (done[v]) continue;
        ans -= calc(v, w);
        max_son[0] = size = num[v];
        get_root(v, root = 0);
        solve(root);
    }
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n >> K) {
        if (n == 0 && K == 0) break;
        memset(done, 0, sizeof(done));
        for (int i = 1; i <= n; i++) edge[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edge[u].push_back(make_pair(v, w));
            edge[v].push_back(make_pair(u, w));
        }
        max_son[0] = size = n;
        root = 0;
        get_root(1, -1);
        ans = 0;
        solve(root);
        cout << ans << endl;
    }
}

CF 715C

给出一棵树，每条边有边权，定义$dist(u, v)$的值为将从ｕ到ｖ经过的点权依次写成１０进制数，问多少个序偶 $(u, v)$ 使得 $dist(u, v) \equiv 0 \mod m$。

节点数不超过 $10^5$，边权范围为$1-9$，$m \le 10^9$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX = 112345;
int MOD;

void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
    if (!b) {
        d = a;
        x = 1;
        y = 0;
    }
    else {
        exgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

ll inv(ll a, ll p) {
    ll d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x + p) % p : -1;
}

ll pow_mod(ll a, ll k) {
    if (MOD == 1) return 1;
    ll rst = 1;
    while (k) {
        if (k & 1) rst = rst * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return rst;
}

vector<pair<int, int> > edge[MAX];

int siz, root;
ll ans;
int num[MAX], max_son[MAX];
bool done[MAX];

void get_root(int u, int fa) {
    max_son[u] = 0;
    num[u] = 1;
    for (const auto &e : edge[u]) {
        int v = e.first;
        if (done[v] || v == fa) continue;
        get_root(v, u);
        num[u] += num[v];
        max_son[u] = max(max_son[u], num[v]);
    }
    max_son[u] = max(max_son[u], siz - num[u]);
    if (max_son[u] < max_son[root]) root = u;
}

ll pow_num[MAX], rev_pow[MAX];
map<ll, ll> pre;

void init() {
    pow_num[0] = 1;
    rev_pow[0] = 1;
    for (int i = 1; i < MAX; i++) pow_num[i] = pow_num[i - 1] * 10 % MOD;
    for (int i = 1; i < MAX; i++) rev_pow[i] = inv(pow_num[i], MOD);
}

void add(ll t) {
    if (pre.count(t)) pre[t]++;
    else pre[t] = 1;
}

ll get(ll t) {
    if (pre.count(t)) return pre[t];
    return 0;
}

ll rst;

void dfs1(int u, int fa, int len, ll now) {
    num[u] = 1;
    for (const auto &e : edge[u]) {
        int v = e.first;
        int w = e.second;
        if (done[v] || v == fa) continue;
        ll t = (now + pow_num[len] * w) % MOD;
        add(t);
        dfs1(v, u, len + 1, t);
        num[u] += num[v];
    }
}

void dfs2(int u, int fa, ll now, int len) {
    for (const auto &e : edge[u]) {
        int v = e.first;
        int w = e.second;
        if (done[v] || v == fa) continue;
        ll t = (now * 10 + w) % MOD;
        rst += get((MOD - t) * rev_pow[len] % MOD);
        dfs2(v, u, t, len + 1);
    }
}

ll calc(int u, int init) {
    rst = 0;
    pre.clear();
    dfs1(u, 0, 0, 0);
    if (init) {
        ll t = (init * 10 + init) % MOD;
        add(0);
        rst += get((MOD - t) * rev_pow[2] % MOD);
        dfs2(u, 0, t, 3);
    } else {
        rst += get(0);
        add(0);
        dfs2(u, 0, 0, 1);
    }
    return rst;
}

ll solve(int u) {
    ans += calc(u, 0);
    done[u] = true;
    for (const auto &e : edge[u]) {
        int v = e.first;
        int w = e.second;
        if (done[v]) continue;
        ans -= calc(v, w);
        max_son[0] = siz = num[v];
        get_root(v, root = 0);
        solve(root);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    MOD = m;

    init();

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        edge[u].push_back(make_pair(v, w));
        edge[v].push_back(make_pair(u, w));
    }
    max_son[0] = siz = n;
    get_root(1, root = 0);
    cout << solve(root) << endl;
}
杂物

浅谈应试教育对大学生身体素质的影响（体育作业）

本文的关注点有两部分，一是现今大学生的身体素质，二是应试教育，然后综合探讨下应试教育对大学生的身体健康的影响。

首先写这篇文章的目的是找出问题和提出解决方案的，所以我们先谈下如今大学生的身体素质。因为我本身就是一名大学生，对这方面也比较有话语权，这里描述下我在日常中发现的一些事情。

总的来说大学生如果按身体素质划分分类的话，大抵能划分出来 4 类，这里详细说一下：第一类，属于非常热爱体育运动，平时就喜欢打打篮球、足球、羽毛球之类的，这类人因为平时一直在参与运动身体素质非常好，完全符合一个大学生应该有的身体素质，对于他们来说身体素质上完全没有问题；第二类，对体育运动的热情不如第一类人的高，但是如果需要的话也可以打的还算不错，应付体育考试和体测完全不再话下，但是平时一直在学习或者待在宿舍，不怎么主动参与体育运动，身体素质自从上了大学后逐渐变差；第三类，身体素质本来就不怎么好，经常得病，平时也是一直避免参加各种运动，体育课和体测都是难题，勉强才能通过。第四类，因为身体上的各种因素（体型、疾病）不能参加过于激烈的体育运动（例如竞争性较强的篮球足球等），本身身体素质较差加上不能参加一些运动导致雪崩效应，身体素质越来越差。

应试教育，又叫填鸭式教育，通常是指只培养学生的应试能力、只关心考试成绩的一种教育方式。从应试教育的这个定义上来看，显然他对大学生的身体素质是有非常重要的影响的。我终结了影响分为两个方面。第一个方面，根据定义，应试教育只注重应试能力考试成绩，所以学校和家长不注重学生的身体素质和体育锻炼。这里拿我的高中当做例子，大家都知道高中是一个非常关键的事情，高考也可以说是人生中一个比较重要转折点，所以大家都非常看重高考成绩，于是我们学校每星期仅安排了一节体育课，再到后来因为课程紧张，唯一的一节体育课也被其他的文化课占了；第二个方面，应试教育为了提高学生的成绩，一天从早上 6 点到晚上 10 点，让学生一直待在教室里学习，对于热爱运动的同学都没有时间去进行运动。

最后终结一下应试教育对于上面四类同学的影响及解决问题的方法。对于第一类同学，在大学期间完全有充足的时间去参与自己喜欢的运动，完全没有问题，反而应该注意下会不会太贪玩影响了学习成绩；对于第二类同学，要保持对体育运动的热情，保证每周都要固定参加一些体育运动，保持自己的身体素质；对于第三类同学，本身身体素质较差就更应该参加运动，可以从先从羽毛球、乒乓球之类的运动开始，培养运动的爱好；对于第四类同学，不能自暴自弃，应该考虑参加一些舒缓的运动，比如慢跑等，逐步提高自己的身体素质。

命题

2017级《程序设计基础（B）II》期末机考题解（Fish出题部分）

The Legend of Zelda

首先一个点 $(x, y)$ 如果 $x \le x_1$ or $y \le y_1 $ or $ x \ge x_2 $ or $y\ge y_2$那么这个点肯定不选的，我们舍弃掉这样的点。

接下来我们要选择一些点组成一个序列并且橫纵坐标都严格递增，我们先只考虑满足横坐标的条件，直接对所有点按照先比较横坐标再比较纵坐标的方式进行排序，排序下来保证所有点的横坐标是不递减的。那么我们在排序后的序列里找一个橫纵坐标递增的最长子序列就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>

#define MAX 1000

struct Node {
    int x, y;
} data[MAX];

int compare(Node a, Node b) {
    if (a.x != b.x) return a.x - b.x;
    return a.y - b.y;
}

int max(int a, int b) {
    return a > b ? a : b;
}

void quick_sort(Node data[], int l, int r) {
    Node key = data[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && compare(data[j], key) >= 0) j--;
        data[i] = data[j];
        while (i < j && compare(data[i], key) <= 0) i++;
        data[j] = data[i];
    }
    data[i] = key;
    if (l < i) quick_sort(data, l, i - 1);
    if (i < r) quick_sort(data, i + 1, r);
}

int dp[MAX];

int x1, x2, y1, y2;

bool check(int x, int y) {
    return x1 < x && x < x2 && y1 < y && y < y2;
}

int main() {
    while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2)) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &data[i].x, &data[i].y);
        }
        quick_sort(data, 1, n);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!check(data[i].x, data[i].y)) continue;
            for (int j = 0; j < i; j++) {
                if (data[j].y >= data[i].y) continue;
                dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans + 2);
    }
}

Dragon Quest

按题意模拟即可，暴力递归写。可能需要注意下，释放魔法后是立即生效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <string.h>

int ans = 0;
int H1, A1, D1, H2, A2, D2;

int max(int a, int b) {
    return a > b ? a : b;
}

void Boss(int, int, int, int, int);
void Player(int, int, int, int, int);

//玩家操作
void Player(int H, int A, int D, int BH, int dep) {
    //如果进行超过五回合就结束
    if (dep > 5) return;
    //如果玩家HP小于等于0结束游戏
    if (H <= 0) return;
    //计算造成的伤害
    int hurt = max(0, A - D2);
    //玩家进行攻击
    Boss(H, A, D, BH - hurt, dep);
    //玩家释放加强攻击魔法
    Boss(H, A + 5, D, BH, dep);
    //玩家释放加强防御魔法
    Boss(H, A, D + 5, BH, dep);
}

//Boss操作
void Boss(int H, int A, int D, int BH, int dep) {
    //Boss血量小于等于0，玩家胜利
    if (BH <= 0) {
        ans++;
        return;
    }
    //计算对玩家造成的伤害
    int hurt = max(0, A2 - D);
    //Boss进行攻击
    Player(H - hurt, A, D, BH, dep + 1);
}

int main() {
    while (~scanf("%d %d %d %d %d %d", &H1, &A1, &D1, &H2, &A2, &D2)) {
        ans = 0;
        //玩家先进行操作
        Player(H1, A1, D1, H2, 1);
        printf("%d\n", ans);
    }
}
历程

第九届ACM山东省赛总结

简易题解：

A

题意就不说了，只考虑第一个字符串和第二个字符串的每种字母有多少个，然后贪心的考虑怎么变化，比如后面需求两个 A，那么先考虑依次前面有没有 Z 、Y、X 来转化。不过这题也可以写最小费用流，KM 二分图最佳完美匹配，毕竟只有 26 × 2 个点。

B

n × n 的棋盘，每个格子上有一个非负的值，0 表示不可选，其他值可选，需要选择若干个格子，并且所选的格子不能同行或同列，在保证选的格子尽量多的情况下使得选的权值最小的格子尽量的大。

如果只考虑让选的格子尽量的大的话，那么这就是一个二分图的模板题，假设棋盘最多选 M 个格子，这里选择的最小的格子尽量大，那么二分答案，考虑删除小于答案的格子剩下的格子能否选够 M 个。

据说出题人卡了网络流的写法…不知道匈牙利能不能过，我不放心复杂度写的 HK。

C

给出一个 N 个节点的无向图，初始没有边，让你连边使得图连通，节点编号 1 到 N，建一条 i 号节点到 j 号节点的边的花费是 (i + j)，那么显然答案就是从 1 开始对每个节点建 n - 1 条边。

D

给出一颗树，每条边有容量和权值，叶子可以走到根节点，然后路径上的权值和乘走的流量就是对答案的贡献，问答案的最大值。

考虑每个叶子到根的权值和，递减排序。依次选取权值和最大的叶子，让他尽可能的走。这样计算出来就是最大的答案，这个贪心很显然就能想到是正确的。

这里需要用到树链剖分维护一条链的信息，选取一个叶子的时候，首先看他到根节点这条链上容量的最小值为多少，然后让他走完这些流量，最后让这条链删去这些流量。

E

给出 1 到 N 的数的一个排列，一个 Good 数的定义为前面至少有一个小于他的数，要求删掉一个数，使得剩下的 Good 数尽量的多，多解输出最小解。

这里我用单调栈维护了，其实只需要维护最小值和次小值就可以了。

对于每个数，我们考虑删除他之后会少几个 Good 数，我们维护一个单调栈和出栈元素的最小值，到 i + 1 位置时，我们首先让栈里大于 i + 1 位置的数出栈，如果队列里的元素只有一个并且出栈的元素没有小于 i + 1 位置的，那么必须由栈里的这个来成为小于 i + 1 位置的数，删掉栈里这个数之后失去的 Good 数的数量加一，然后 i + 1 位置的数入栈。

最后删掉最没有贡献的数就可以了，并考虑这个数是不是 Good 数。

F

容斥定理，考虑区间之间交的情况，首先加上全部区间长度相乘，然后减去第一个和第二个相等，第二个和第三个相等…然后加上第一个和第二个并且第三个相等…

可以手写一下，对拍验证…最后我也不知道有没有写对

G

A 和 B 进行 Nim 博弈，B 开局可以移除至多 D 堆，问 B 有多少种移除堆的方案能过胜利。

这里数据范围很小，至多 1000 堆，每堆大小至多 1000，D 至多 10 堆。

显然如果 B 要赢必须要保证所有堆的异或和为 0 。

依次从左到右考虑每堆选不选，设 $dp[i][j][k]$ 的值为考虑完第 i 堆，前 i 堆的异或和为 j，移了 D 堆的方案数。

那么 $\sum_{i=0}^ddp[n][0][i]$就是最终答案，转移如下

$dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j \oplus h_{i-1}][d-1]$

如果 k 等于 0 的话仅考虑 $dp[i - 1][j][k] $ 的转移。

热身赛：

当时榜炸掉了…然后完全没有跟榜，做题是按难度递减做的，先写了一发最难的 A 题，正解是区间 DP，然后以为是签到题，写了个假算法就交上去了。然后看了下 B 题是训练赛的原题，二维偏序或者主席树、线段树合并都可以写，于是上去就写了，然后拿了 A 区的第一个 B 题的气球（毒瘤开题）。然后做的 C，大概是我出的大一上学期期末考试题的变式 ？D 题我没看，队友说可以写就写完 A 了，应该是一个特别水的签到题。

最后 A 题也是完全没思路，我完全没往区间 DP 上想，其实这个热身赛的榜的前几名已经和正式赛的榜差不多了…

然后发现山大和中石油的强队有点多，起初我们还是以为山大和中石油只有一两个比我们强的，运气好还能捧个杯？（雾）结果比我们强和实力相当的大概有六七个，就有点绝望了，不过还好实力差距还不是很大。

正式赛：

首先先看的 C，标准的签到题，让队友敲的，结果 WA 了两次才 A，可以说是开局非常爆炸了，于是导致我后面交题也不怎么看罚时了（不知道算不算什么破釜沉舟背水一战），想着只能靠题数取胜了。

然后看的 B，理解错了题意，正确的题意是符合贪心性质的，可以写贪心，我大概是做了个 Hard Version，写了个最小费用流，非常熟练的抄完自己总结的板子，保存边的数量的变量没初始化 RE 了一发，然后由于不考虑罚时，于是改完就立刻交了一发就 A 了。

在我写 B 的时候队友就已经在看 F 题了（数据出错的那个题），等我写完他告诉了我一下容斥的做法，我觉得没什么问题就开始敲了，不过写的过程中感觉非常难写…看到榜单上 6 分钟就 AC 的，怀疑自己的做法是不是不对…然后让队友写了个对拍自己去重新想了一下思路，发现还是得写容斥，于是回来继续写，写完后又对拍了几组数据改了改就交了，然后肯定是 A 的，最后也不知道这个题有没有写对 ORZ

这时候另一个队友一直在读题，我敲完一道题基本上就可以接着看下一道题了，这时候一个队友在想 E 题，我去写 G 题，然后一眼看过去就是 NIM 博弈加 DP 记录方案数，不过这里数据越界改了好几次才过，不过改完一次就交一次不在乎罚时，所幸改的还算快。

在我改 G 题的时候让队友敲了下 E 题，NlogN 的复杂度 TLE 了，感觉必须得线性的算法才能过，这时候封榜还有半个小时，榜上已经有六题的了，于是决定让队友去其他的题了（B 和 D），然后我考虑这个题的答案限制条件比较少，应该用不到队友敲得逆序数之类的，于是正好我们都想到单调队列，于是先写了个单调队列，然后测了下样例对了，要交的时候还是不放心，因为如果这个 WA 的话我不能确定是算法错了还是代码细节错了，于是让队友出了下样例果然错了，后来多考虑了一个条件就 OK 了，然后提交 AC。

这时候队友说 B 题有思路了，不过是图论题还是让我敲，我一直感觉 1e8 的时间复杂度过不去，于是先让队友把板子抄上，然后自己想了下细节怎么处理，感觉没问题之后就开始上手做了，写完 debug 了 20 多分钟，队友板子抄错了两个地方，改完过了另一个队友出的特别强的样例（反转他说是比较强），提交就 AC 了。

这时候比赛结束还有四十分钟，榜上已经有七题的队伍了，加上我们罚时比较高，夺冠要在这 40 分钟 A 两题感觉希望不太大了，有点失望…队友在我写 B 题的时候已经想了下大概的 D 题做法，我问了他一下，感觉加上树链剖分就可以写了，于是拿过来之前直接整理的树链剖分板子就超了起来，心情比较差加上又特别累了，中间电脑还重启耽误了十多分钟，最后还有十分钟结束才写完，总共 200 多行代码，我当时就和队友说，这么长的代码要是不出点 Bug 什么的我都不信，结果运行没编译错误，然后输入样例结果却都是 0 … 非常紧急的改完之后还剩五分钟了，最终居然过了样例，当时 PC ^ 2 显示结束还有三分钟立刻就交了，之后就赶紧看代码还有没有错误。然后看着看着队友说有评测结果了，看了一下返回了一个 Yes，可以说是非常开心了。

总结：

这场比赛打起来还算是非常开心的，F 题出错了也没有耽误我们太长的时间，题目基本上都是看到了就有大概的思路和做法了，只有 E 和 F 想的时间长一点。整体发挥还算是不错，不过细节失误算是比较多，比如没初始化，数组越界，感觉就是 200 行代码居然没有细节错误，但是写的非常短很有自信的代码错了两三处，感觉非常奇怪…

ACM►字符串►后缀数组

后缀数组小结

后缀数组

后缀数组具体其实是指的 Rank， SA 和 height 数组，DA 和 DC3 只是计算的方式，并不是关键。

其中 Rank 数组的 Rank[i] 的含义是第 i 个后缀排名，SA[i] 的含义是排名第 i 的是哪一个后缀，height[i] 的含义是排名第 i 的后缀和排名第 i - 1 的后缀的最长公共前缀。

模板

DA 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int MAX = 200010;
const int SIGMA_SIZE = 1000010;

int cntA[MAX], cntB[MAX], sa[MAX], tsa[MAX], A[MAX], B[MAX], height[MAX], Rank[MAX];
int n, data[MAX];

int bucket[SIGMA_SIZE];

void get_SA(const int *ch) {
    for (int i = 0; i < SIGMA_SIZE; i++) bucket[i] = 0;
    for (int i = 1; i <= n; i++) bucket[ch[i - 1]]++;
    for (int i = 1; i < SIGMA_SIZE; i++) bucket[i] += bucket[i - 1];
    for (int i = n; i; i--) sa[bucket[ch[i - 1]]--] = i;
    Rank[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {
        Rank[sa[i]] = Rank[sa[i - 1]];
        if (ch[sa[i] - 1] != ch[sa[i - 1] - 1]) Rank[sa[i]]++;
    }
    for (int l = 1; Rank[sa[n]] < n; l <<= 1) {
        memset(cntA, 0, sizeof(cntA));
        memset(cntB, 0, sizeof(cntB));
        for (int i = 1; i <= n; i++) {
            cntA[A[i] = Rank[i]]++;
            cntB[B[i] = (i + l <= n) ? Rank[i + l] : 0]++;
        }
        for (int i = 1; i <= n; i++) cntB[i] += cntB[i - 1];
        for (int i = n; i; i--) tsa[cntB[B[i]]--] = i;
        for (int i = 1; i <= n; i++) cntA[i] += cntA[i - 1];
        for (int i = n; i; i--) sa[cntA[A[tsa[i]]]--] = tsa[i];
        Rank[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            Rank[sa[i]] = Rank[sa[i - 1]];
            if (A[sa[i]] != A[sa[i - 1]] || B[sa[i]] != B[sa[i - 1]]) Rank[sa[i]]++;
        }
    }
    for (int i = 1, j = 0; i <= n; i++) {
        if (j) j--;
        while (ch[i + j - 1] == ch[sa[Rank[i] - 1] + j - 1]) j++;
        height[Rank[i]] = j;
    }
}

不需要初始化，直接调用 get_SA() 传入数组地址即可，下标均从 1 到 n，n 代表长度。

DC3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int MAX = 200233;
const int maxn = MAX;

int n;
char data[MAX];

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[maxn], wb[maxn], wv[maxn], WS[maxn];
int Rank[MAX], height[MAX], r[MAX * 3], sa[MAX * 3];
int limit[MAX];

int c0(int *r, int a, int b) {
    return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2];
}

int c12(int k, int *r, int a, int b) {
    if (k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1);
    else return r[a] < r[b] || r[a] == r[b] && wv[a + 1] < wv[b + 1];
}

void sort(int *r, int *a, int *b, int n, int m) {
    int i;
    for (i = 0; i < n; i++) wv[i] = r[a[i]];
    for (i = 0; i < m; i++) WS[i] = 0;
    for (i = 0; i < n; i++) WS[wv[i]]++;
    for (i = 1; i < m; i++) WS[i] += WS[i - 1];
    for (i = n - 1; i >= 0; i--) b[--WS[wv[i]]] = a[i];
    return;
}

void dc3(int *r, int *sa, int n, int m) {
    int i, j, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p;
    int *rn = r + n;
    r[n] = r[n + 1] = 0;
    for (i = 0; i < n; i++) if (i % 3 != 0) wa[tbc++] = i;
    sort(r + 2, wa, wb, tbc, m);
    sort(r + 1, wb, wa, tbc, m);
    sort(r, wa, wb, tbc, m);
    for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
        rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
    if (p < tbc) dc3(rn, san, tbc, p);
    else for (i = 0; i < tbc; i++) san[rn[i]] = i;
    for (i = 0; i < tbc; i++) if (san[i] < tb) wb[ta++] = san[i] * 3;
    if (n % 3 == 1) wb[ta++] = n - 1;
    sort(r, wb, wa, ta, m);
    for (i = 0; i < tbc; i++) wv[wb[i] = G(san[i])] = i;
    for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
        sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
    for (; i < ta; p++) sa[p] = wa[i++];
    for (; j < tbc; p++) sa[p] = wb[j++];
    return;
}

void cal_height(int *r, int *sa, int n) {
    int i, j, k = 0;
    for (i = 1; i <= n; i++)
        Rank[sa[i]] = i;
    for (i = 0; i < n; height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1];
             r[i + k] == r[j + k]; k++);
}

不需要初始化，r 和 sa 数组开最大值的三倍，调用如下

1
2
3
r[n] = 0;
dc3(r, sa, n + 1, 256);
cal_height(r, sa, n);

r 数组下标从 0 开始，数组的后面加一个最小值，计算 sa 数字时让长度 + 1，这样求出的 Rank 和 SA 的取值都是 1 到 n 。

数组用法

强烈推荐集训队论文 《后缀数组——处理字符串的有力工具》

ACM►字符串►AC自动机

AC自动机（模板）

感谢&资料：

主要参考紫书的写法，其他的写法都用到了指针，不太喜欢指针…

因为紫书没有完整的代码，然后参考了一下 dalao 的博客。

简介：

AC自动机主要解决的是字符串匹配问题，不同于 KMP 的是，AC 自动机可以进行多个模式串的匹配。KMP 的失配指针是一个线性的数组，但是 AC 自动机是多个模式串匹配，所以适配指针是一个树型的结构。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>

using namespace std;

//字典树的最大节点个数
const int MAX = 250001;
const int N = 1000010;
//有多少个不同的字符
const int SIGMA_SIZE = 26;

//字典树的节点
int ch[MAX][SIGMA_SIZE];
//当前节点是否为一个模式串的结尾， 当前节点的上一个模式串结尾， fail指针
int val[MAX], last[MAX], f[MAX], sz;
int ANS;

void init() {
    sz = 1;
    memset(ch, 0, sizeof(ch));
    memset(val, 0, sizeof(val));
    memset(f, 0, sizeof(f));
    memset(last, 0, sizeof(last));
}

int idx(char c) {
    return c - 'a';
}

//更新答案
void add(int u) {
    while (u) {
        ANS += val[u];
        val[u] = 0;
        u = last[u];
    }
}

//添加模式串
void Creat(char *s) {
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = idx(s[i]);
        if (!ch[u][c]) ch[u][c] = sz++;
        u = ch[u][c];
    }
    val[u]++;
}


//获得fail指针
void getFail() {
    queue<int> q;
    for (int i = 0; i < SIGMA_SIZE; i++)
        if (ch[0][i]) q.push(ch[0][i]);

    while (!q.empty()) {
        int r = q.front(); q.pop();
        for (int c = 0; c < SIGMA_SIZE; c++) {
            int u = ch[r][c];
            if (!u) continue;
            q.push(u);
            int v = f[r];
            //和kmp相似，和根据父亲的fail指针获得当前的
            while (v && ch[v][c] == 0) v = f[v];
            f[u] = ch[v][c];
            //更新last
            last[u] = val[f[u]] ? f[u] : last[f[u]];
        }
    }
}

//进行匹配
void find(char * T) {
    int len = strlen(T), j = 0;
    for (int i = 0; i < len; i++) {
        int c = idx(T[i]);
        while (j && ch[j][c] == 0) j = f[j];
        j = ch[j][c];
        //如果当前是模式串的结尾，那么更新答案
        //else if 里是处理一个模式串包含另一个模式串的情况
        if (val[j]) add(j);
        else if (last[j]) add(last[j]);
    }
}

char str[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        int n;
        scanf("%d", &n);
        while (n--) {
            scanf("%s", str);
            Creat(str);
        }
        getFail();
        scanf("%s", str);
        ANS = 0;
        find(str);
        printf("%d\n", ANS);
    }
}

代码二

get_fail 改了下，预处理了需要跳到的位置，匹配是 O(文章长度的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>

using namespace std;

const int MAX = 250001;
const int N = 1000010;

const int SIGMA_SIZE = 26;

int ch[MAX][SIGMA_SIZE];
int val[MAX], last[MAX], f[MAX], sz;
int ANS;

void init() {
    sz = 1;
    memset(ch, 0, sizeof(ch));
    memset(val, 0, sizeof(val));
    memset(f, 0, sizeof(f));
    memset(last, 0, sizeof(last));
}

int idx(char c) {
    return c - 'a';
}

void add(int u) {
    while (u) {
        ANS += val[u];
        val[u] = 0;
        u = last[u];
    }
}

void creat(char *s) {
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = idx(s[i]);
        if (!ch[u][c]) ch[u][c] = sz++;
        u = ch[u][c];
    }
    val[u]++;
}

void get_fail() {
    queue<int> q;
    for (int i = 0; i < SIGMA_SIZE; i++)
        if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty()) {
        int r = q.front();
        q.pop();
        for (int c = 0; c < SIGMA_SIZE; c++) {
            int u = ch[r][c];
            if (!u) {
                ch[r][c] = ch[f[r]][c];
                continue;
            }
            q.push(u);
            int v = f[r];
            while (v && ch[v][c] == 0) v = f[v];
            f[u] = ch[v][c];
            last[u] = val[f[u]] ? f[u] : last[f[u]];
        }
    }
}

void find(char *T) {
    int len = strlen(T), j = 0;
    for (int i = 0; i < len; i++) {
        int c = idx(T[i]);
        j = ch[j][c];
        if (val[j]) add(j);
//        else if (last[j]) add(last[j]);
    }
}

char str[N];

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        init();
        int n;
        cin >> n;
        while (n--) {
            cin >> str;
            creat(str);
        }
        get_fail();
        cin >> str;
        ANS = 0;
        find(str);
        cout << ANS << endl;
    }
}
历程

2018年寒假集训

一、时间内容

2018年寒假，学校 ACM 算法实验室。2018年2月18日至2018年3月4日，共计16天，平均每天8小时，约 16 × 8 = 128 小时。

主要以学习算法提高自己的能力为目的，另外要负责17级新生的训练计划安排和辅导工作。

二、体验和经历

刚开始前几天就忙的不可开交，首先是要对17级参加集训的同学根据能力进行分组以适应不同的训练进度。

所以要准备一场分组测试赛，不过由于时间有限题目没有原创，直接用了之前的题目。整体上也算是非常坎坷，由于比赛前没有去实验室测试一下环境，导致501实验室好几天前就连不上网，到比赛当天也没有修复，于是只好紧记处理分配到其他的实验室。

比赛的题目总体上还是不错的，区分度非常好，将实验室划分到了三个组。第一组自然是面向接下来的天梯赛和以后的省赛区域赛的，学习内容主要是数据结构，包含链表栈队列树图论等内容；第二组是程序设计基础学的比较扎实的同学，直接开始学习程序设计下部分的内容（包括结构体链表贪心动态规划等内容），并且在最后学习了数据结构中的栈和一些排序算法。第三组是面向大部分的同学，主要由老师来讲，先进行一段程序设计基础的学习然后学习下部分的内容。

分配任务的时候，自己选了算是比较抽象的动态规划，觉得挺难讲的，但是幸好老师的PPT做的非常详细，加上平时晚上去实验室辅导一下，相信效果应该还可以。

然后就是自己的训练了，主要是比赛和CF训练为主。也算是把自己锻炼到了准紫名水平了。印象中主要学习了概率几何高斯消元。

概率刷的时候发现了一个通用套路，基本上都是用DP的思想去计算概率的，就做题分析方面，我的做法通常是画一颗树型的结构，通过这一次选 a 或 b来分支并计算概率，并通过这棵树发现一些有规律的地方，然后定义DP的状态，找出状态之间的关系，写出递推式并解决问题。大部分时候会发现这棵树有一部分分支是无穷的，举个例子来说：一个人有两道门，其中一道门通往出口，一道门又回到远点，选择一道门并进入要花费A分钟的时间，请问要出去花费时间的期望为多少？可以看出这道题如果画出树型的结构的话有一直出不去的情况，一直留在原地，然后计算这种情况，期望的和是一个变系数的等比数列，然后用高中的知识，等比数列错位相减求和。然后问题就圆满的解决了。

对于计算几何，算是更加系统的了一点。就算不系统的学，那些题也是能做，举个例子从高中以来一直习惯用斜率来表示一条直线，然后这样的话要考虑斜率为0的情况，做数学题的时候计算量非常少，也就是设一两个直线方程，最后特判掉就好了。但是写代码的时候需要一个通用的解决问题方式，做数学的时候只是解决了一个特定的问题，现在是要为一个更加抽象的问题设计算法，所以算法的通用性要优先于易读性。于是考虑用一个点和一个方向向量来表示一个直线更加合理。并且对于判断两直线是否平行用点的点积去计算，用叉积判断两个向量的位置关系等。并且计算几何的一些算法其实很简单容易理解（比起Splay，KDtree这样的数据结构），顺便学习了凸包，实现向量的旋转等，另外这里的旋转其实就是线代里面的一个矩阵，对i，j基向量进行了线性变换。

最后是高斯消元，高斯消元说简单也简单，说难也难，简单的来说，其实就是用矩阵将初中学的多元一次方程组系统化表示并求解。说难的话就是要处理好多的细节，并且一个题要想起来要用高斯消元来解决（这一点可能比较缺乏锻炼，因为之前做的题都是特定的专题里面的），高斯消元具体的来说，就是求解多元一次方程组，或者说是将矩阵化为最简形，求方程组的最大无关组，求矩阵的秩等…一般在代码上会有多种提现，由于计算机使用了浮点数来表示小数的原因，算是和表示整数使用了两种非常不同的形式，所以对于可以接受浮点误差的问题（比如概率期望），可以直接用浮点数去计算。

然后是比赛汇总：

第一场去的是哈尔滨，住了三晚上体验还行，热身赛随便打打的，只切了几个水题，然后热身赛状态算是最爆炸的一次，三个小时才出两个题，本来已经有打铁的打算了，封榜前铜牌倒数第五名。结果比赛完根本没滚榜，然后排名只下滑到了倒数第三，感觉就非常开心了。也算是人生第一块区域赛的牌子吧，不过这次比赛打的是真的惨。

出发前准备的算是挺充分，当时还一直纠结着哈尔滨冷不冷，要带多厚的衣服过去，最后就随便带了几件，然后出发当天去超市买了一堆的东西，给手机缓存了几部动漫（路人女主，末日时，来自深渊，笨女孩…）。得出经验，只需要提前半小时能够到达火车站就好了。

在火车上一晚上看完了笨女孩，然后白天的路上看完了末日时。期间还有打打王者荣耀和斗地主，感觉好颓啊，最逗的是一个别的队的傻子，和我们斗地主积分输成负的时候，就要清理下手机的数据，重新变成1000分。路上还算是挺好的，不过一天三顿吃泡面有点绝望，发现买的零食都不怎么好吃。另外值得一提的就是路上遇到了一个别人家的熊孩子，特别烦。

到了哈尔滨刚下车也不算太冷，在火车站刚下车就见识到了东北的民风彪悍，门卫大爷开玩笑都是 “你过来，看我不揍你！”。然后晚上就搭车去旅馆了，还算是顺利。（不过我们的房间厕所没有门是几个意思啊？！）

晚上一起去吃了夜宵（算是？），没好吃的然后回宿舍订了外卖，发现外卖能直接送到酒店的房间里，体验贼好！

第二天睡到了九点半（晚上终末少女的旅行更新了，然后看了一集），发现步行只需要半小时就到学校了，报名领取发票也挺顺利的，然后在门外的牌子前面合影就去吃饭了。伙食感觉还行，至少有不少肉，能吃饱…米饭给的是有点少。

下午就是一个关于游戏开发的演讲，然后不知不觉的睡着了…

回去的时候就没什么意思了，因为时间问题结果没去成中央大街，只买了点超市里散卖的红肠。

然后第二场紧接着去的秦皇岛，坐的火车居然和去哈尔滨的一样。感受就是这是去过最好吃的食堂，又便宜又好吃。热身赛没有什么印象了。然后正式赛的体验就是感觉在打一场 5 小时的 CF，几乎用不到数据结构。算是非常接近银的一次了，最后 A 题卡住了，没有 A 出了，明明思路和做法都有了，不知道哪里错误…比赛后也是感觉非常可惜，最后算是铜首吧。

第三次青岛站，感觉正式赛的题还没有热身赛有意思，热身赛遇到了一个字典树上维护信息，当时想到了可以这样做，复杂度什么的都证明的很正确，感觉挺爽的，虽然没敲出来，比赛回来就找了一个类似的题补掉了。热身赛算是毫无比赛体验了，前期两个水题，然后一个本来是字符串 Hash 的中档题大家都水了过去，最后三题凭罚时银了…热身赛的时候还是打算先练练手了，最后排名好像是在银牌区，算是认真打了下。最后在想 C 题，突然奇想用线段树的维护信息方式去写字典树，然后好像就可以做了，不过到比赛结束还没有调出来有点可惜，回来的后补掉了一个类似的题。

正式赛惯例还是我来敲签到题，这两场的发挥还算正常，做完签到题能够在银牌区，不过出打印图形的题的时候算是失误了一下，出的比较慢，当时好像在 90 名左右。之后就去看那个字符串题了，按照后缀数组的暴力做法让队友敲了一个半小时才调过了样例，然后我试了下造的大数据，发现 1000 的数据两就差不多 TLE 了，然后就交，这时候我一直在想简单的算法，感觉 A 的人那么多，不可能这么多队都会后缀数组，然后写了一个最差情况下可能 T 的算法，交上去就 A 了。这时候排名 50 左右，银牌是肯定稳了，毕竟一个小时不可能滚上去 50 多个队。最后一小时读了一个题，然后一点思路都没有，最后一个小时算是很绝望了

这场比赛感觉题出的是真的不好，前三题是一点难度都没有，只要手速快点，胆子大点就莫名其妙的前 100 名了，这样随随便便就拿到的名次感觉都对不起平时的训练。不过有银牌还是非常开心的，自我评价我们队的水平也就是介于铜牌和银牌之间。

第四场，CCPC Final，可以说是体验最好的一次了，在哈尔滨待了四天，逛了中央大街松花江教堂。热身赛差点爆零，当时就感觉这场比赛难度好恐怖了。正式赛体验还行，前期水题卡的时间有点长，不过后面中档题出的还算比较快，甚至还冲到了银牌区，不过还没居然卡在了我最喜欢的图论上…查分约束之前都没怎么刷过，感觉很可惜。如果能切掉这个题的话，可能也有银牌了。可以说是打的比较好的一次比赛了，中间和 dalao 们的排名差距很小。

最后是 ECL Final，食堂特别难吃！又贵又难吃，还一点肉都没有！热身赛这次爆零了，体验不是很好。正式赛前期简直爆炸，最简单的水题错了 3 发才过。到比赛中期感觉才上来，连过了几题才到了 100 多名。感觉会做的都做出来了，后面的题是真的心有余而力不足了。这次比赛感觉前面题的代码量太少，只靠思维猜结论…最后也是稳铜了。

感悟

总的来说还是先提升自身能力吧，接下来也没有组队的比赛了，补一下自己不擅长的数学几何之类的。然后比赛下来发现卡的并不是知识点，而是 CF 的那种题，明年之前打上紫名？另外队伍配合的并不好，比赛的时候一种感觉是在两个人打比赛…

ACM►计算几何

基础计算几何小结

前言

说是小结，其实这里只是备忘下，记录下几何题的工具函数。

向量和点

这里简单定义了一个点类，实现数乘，加减。说是点其实大部分时候是当做向量来用的，计算几何中为了方便经常会用向量来描述几何图形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}

    Point operator*(const double t) {
        return Point(x * t, y * t);
    }

    Point operator-(const Point t) {
        return Point(x - t.x, y - t.y);
    }

    Point operator+(const Point t) {
        return Point(x + t.x, y + t.y);
    }

    bool operator<(const Point t) {
        return dcmp(x - t.x) < 0 || dcmp(x - t.x) == 0 && dcmp(y - t.y) < 0;
    }
};

向量的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//点积
double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}
//叉积
double cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}
//向量的长度
double length(Point a) {
    return sqrt(dot(a, a));
}
//两个向量的夹角
double angle(Point a, Point b) {
    return acos(dot(a, b) / length(a) / length(b));
}
//将向量以起点为中心旋转，rad 为旋转的角度，弧度制
Point rotate(Point a, double rad) {
    return Point(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}

点与直线的关系

1
2
3
4
5
6
7
8
//点 q 是否在线段 p1、p2 上，这里包含了在端点的情况，如果不包含后面的点乘改成小于，如果考虑直线的话就不需要后面的点乘了
bool on_seg(Point p1, Point p2, Point q) {
    return dcmp(cross((p1 - q), (p2 - q))) == 0 && dcmp(dot((p1 - q), (p2 - q))) <= 0;
}
//求 p1、p2 和 q1、q2 两条直线的交点，注意两条直线（向量）叉乘不能等于 0，即先要判断平行
Point intersection(Point p1, Point p2, Point q1, Point q2) {
    return p1 + (p2 - p1) * (cross(q2 - q1, q1 - p1) / cross(q2 - q1, p2 - p1));
}

多边形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//求多边形面积，要保证点的顺序是顺时针或者逆时针
double polygon_area(vector<Point> data) {
    double area = 0;
    for (int i = 1; i < data.size() - 1; i++) {
        area += cross(data[i] - data[0], data[i + 1] - data[0]);
    }
    return area / 2;
}
//求凸包，并以顺时针的顺序返回凸包上的点
vector<Point> convex_hull(vector<Point> &data) {
    sort(data.begin(), data.end());
    vector<Point> rst;
    int m = 0;
    for (int i = 0; i < data.size(); i++) {
        while (m > 1 && dcmp(cross(rst[m - 1] - rst[m - 2], data[i] - rst[m - 2])) <= 0) rst.pop_back(), m--;
        rst.push_back(data[i]), m++;
    }
    int k = m;
    for (int i = data.size() - 2; i >= 0; i--) {
        while (m > k && dcmp(cross(rst[m - 1] - rst[m - 2], data[i] - rst[m - 2])) <= 0) rst.pop_back(), m--;
        rst.push_back(data[i]), m++;
    }
    rst.pop_back();
    return rst;
}