最近机器人队老师让我们 ACM 队出几个人去参加这次编程赛道，总共 1200 人，初赛 75 % 晋级，复赛前 30% 拿省一省二晋级（决赛 100% 获奖），可惜自己太菜距离晋级决赛差了1 分排名 300 错失杭州旅行的机会

A.懂的都懂—暴力

题意：有一张原图，其特征数据由 N 个小于 255 的非负整数组成（数值可能重复），给定的新图如果每个特征数据（也保证是小于 255 的非负整数）可以由原图中任意四个不同数据的平均值计算而来则认为是相似图片。判断给出的 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int maxn = 55;

int a[maxn];
bool vis[1025];

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        int tmp = a[i];
        for (int j = 1; j <= n; ++j) {
            tmp += a[j];
            if (tmp > 1020 || j == i) {
                tmp -= a[j];
                continue;
            }
            for (int k = 1; k <= n; ++k) {
                tmp += a[k];
                if (tmp > 1020 || (k == i || k == j)) {
                    tmp -= a[k];
                    continue;
                }
                for (int o = 1; o <= n; ++o) {
                    tmp += a[o];
                    if (tmp > 1020 || (o == i || o == j || o == k)) {
                        tmp -= a[o];
                        continue;
                    }
                    vis[tmp] = 1;
                    tmp -= a[o];
                }
                tmp -= a[k];
            }
            tmp -= a[j];
        }
    }
    while (k--) {
        bool flag = 1;
        int m;
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            int x;
            cin >> x;
            if (flag && !vis[x * 4]) {
                flag = 0;
            }
        }
        cout << (flag ? "Yes" : "No") << endl;
    }
}

B.芬兰木棋—贪心+map容器

题意：一个根据芬兰游戏改变简化的题。一个人叫哲哲站在 (0,0) 处，他的周围都放着许多木棋（保证没有位置重复或者在原点的），每个木棋上有个正整数代表分数。这个人每次选择一个方向，他有以下两种操作选择：击倒该方向上离着自己最近的木棋并获得木棋的分数；或者击倒该方向上离着自己最近的 k 个木桩自闭并获得击倒根数的分数（也就是 k 分）。现在这个人想拿到最多分并且求出拿到最多分数时需要最少操作次数

思路：最高分肯定是把所有木棋击倒，关键是怎么操作才能最少。可以将所有木棋按相对哲哲的方向分类并开邻接表存储相同方向的木棋。然后枚举每个方向处理：先把这个方向上的所有点根据到原点的距离排序，从前往后枚举，如果有连续的一段木棋的值全都是1，那么把它们一起击倒得到的收益和分别击倒得到的收益是一样的，可以合并击倒。如果单个木棋的p值大于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
typedef pair<int, int> pii;

map<pii, vector<pii> > mp;  //斜率邻接表存(距离,分数)

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        int xx = x, yy = y;
        if (x == 0)
            y /= abs(y);
        else if (y == 0)
            x /= abs(x);
        else {
            int gcd = __gcd(abs(x), abs(y));
            x /= gcd, y /= gcd;
        }
        mp[pii(y, x)].push_back(pii(xx * xx + yy * yy, z));
    }
    int ans = 0, cnt = 0;
    for (auto &e1 : mp) {
        sort(e1.second.begin(), e1.second.end());
        int tmp = 0;
        for (auto &e2 : e1.second) {
            if (e2.second == 1)
                ++tmp;
            else {
                ans = ans + tmp + e2.second;
                if (!tmp)
                    ++cnt;
                else
                    cnt += 2;
                tmp = 0;
            }
        }
        if (tmp) ans = ans + tmp, ++cnt;
    }
    cout << ans << ' ' << cnt << endl;
}

C.打怪升级—模拟思维+最短路打印路径

题意：有 n 个点形成的无向带权连通图，路径上有怪物路路过时需要消耗能量击败他们同时可以得到价值。需要完成两件事：

  • 先确定一个合适的起点，要求这个起点到其他点的能量消耗最大值尽可能小，如果有多个这样的点选择靠前的点
  • 而后有 k 个点询问，帮助玩家确定从选定起点出发到指定询问点所需要走的路径，要求这个路径消耗的能量值尽可能小，如果有多条这样的路径选择获得价值最大的

思路：读懂题意赢了一半。虽然点有 1000 个但是给了五秒时间 floyd 和 dijkstra 都能过，按照题意先跑最短路求出每个点作为起点的情况从而解决问题一，然后在从选定起点回溯路径。右大腿队友用 floyd 过的非常快，我选的跑 n 边 dijkstra。由于开始无法选定起点，第二问打印路径如果再跑一边 dijkstra 就肯定超时所以多开一维数组记录每个点作为起点情况的所有最短路信息（经典空间换时间），可惜最后还是有个点超时（都用了堆优化），找左大腿队友看了半天没找到问题可能是前式链向星不好用？？

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
const int V = 1e3 + 5, E = 1e7 + 5;

int n, m, tot;
int head[V], pre[V][V];      //前式连向星和前继节点
int ans1[V][V], ans2[V][V];  //能量和收益
int to[E], nex[E], ene[E], val[E];

void init() {
    tot = 0;
    for (int i = 1; i <= n; ++i) head[i] = -1;
    memset(ans1, 0x3f, sizeof ans1);
}

struct node {
    int cost, earn, ver;
    bool operator<(const node &A) const {
        if (cost != A.cost) return cost < A.cost;
        return earn > A.earn;
    }
    node(int cost, int earn, int ver) : cost(cost), earn(earn), ver(ver) {}
};

void add(int u, int v, int c, int w) {
    ++tot;
    nex[tot] = head[u];
    head[u] = tot;
    to[tot] = v;
    ene[tot] = c;
    val[tot] = w;
}

void dijkstra(int start) {
    ans1[start][start] = ans2[start][start] = 0;
    priority_queue<node> que;
    que.push(node(0, 0, start));
    while (que.size()) {
        auto now = que.top();
        que.pop();
        if (now.cost > ans1[start][now.ver] || (now.cost == ans1[start][now.ver] && now.earn < ans2[start][now.ver])) continue;
        for (int i = head[now.ver]; ~i; i = nex[i]) {
            if (ans1[start][now.ver] + ene[i] < ans1[start][to[i]])
                ans1[start][to[i]] = ans1[start][now.ver] + ene[i], ans2[start][to[i]] = ans2[start][now.ver] + val[i], pre[start][to[i]] = now.ver, que.push(node(ans1[start][to[i]], ans2[start][to[i]], to[i]));
            else if (ans1[start][now.ver] + ene[i] == ans1[start][to[i]] && ans2[start][now.ver] + val[i] > ans2[start][to[i]])
                ans2[start][to[i]] = ans2[start][now.ver] + val[i], pre[start][to[i]] = now.ver, que.push(node(ans1[start][to[i]], ans2[start][to[i]], to[i]));
        }
    }
}

void print_road(int start, int now) {
    if (!pre[start][now]) return;
    print_road(start, pre[start][now]);
    cout << "->" << now;
}

void test_case() {
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; ++i) {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        add(u, v, c, w), add(v, u, c, w);
    }
    int pos, maxx = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
        dijkstra(i);
        int tmp = 0;
        for (int j = 1; j <= n; ++j) tmp = max(tmp, ans1[i][j]);
        if (tmp < maxx) maxx = tmp, pos = i;
    }
    cout << pos << endl;
    int k;
    cin >> k;
    while (k--) {
        int x;
        cin >> x;
        cout << pos;
        print_road(pos, x);
        cout << endl;
        cout << ans1[pos][x] << ' ' << ans2[pos][x] << endl;
    }
}

D.疫情防控—反向建图+并查集

题意：有 n 个机场，m 条航线，每天都会有一个机场被设为防控地区导致所连航线都无法正常运行，每天有 q 对旅客从 x 机场前往 y 机场，请计算每天有多少对旅客会受到影响无法完成行程（旅客只要能直达或者通过若干次中转就算成功旅行）

思路：其实就是求每天图发生变化后查询点对连通性关系。无法简单维护删边操作，如果反着考虑倒序建边这题只需要一遍并查集就可以了，同样离线倒着记录处理的每天答案。并查集维护从最后一天开始连通的点集，那么往前走一天相当于有一部分航线恢复正常，就把恢复的点连到并查集里，查询的点对只需要看下是否都在并查集里

由于这题既需要按照删边的逆向顺序来遍历边，还涉及查询每个点所连边，用前式链向星应该更好写一些

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
const int maxn = 2e5 + 5;

int n, m, d;
int fa[maxn];
bool vis[maxn];
vector<int> tmp, ans, G[maxn];
vector<pii> road, ask[maxn];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void join(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

void solve() {
    cin >> n >> m >> d;
    for (int i = 1; i <= n; ++i) fa[i] = i;  //init
    for (int i = 1; i <= m; ++i) {           //存边
        int u, v;
        cin >> u >> v;
        road.push_back(pii(u, v));
        G[u].push_back(v), G[v].push_back(u);
    }
    tmp.resize(d + 1);  //倒着离线操作
    for (int i = 1; i <= d; ++i) {
        int c, q;
        cin >> c >> q;
        tmp[i] = c, vis[c] = 1;         //中毒的城市
        for (int j = 1; j <= q; ++j) {  //记录询问
            int u, v;
            cin >> u >> v;
            ask[i].push_back(pii(u, v));
        }
    }
    for (auto &e : road) {  //先建立连接的城市
        int st = e.first, ed = e.second;
        if (!vis[st] && !vis[ed]) join(st, ed);
    }
    for (int i = d; i >= 1; --i) {  //倒着处理每一天
        int cnt = 0;                //记录答案
        for (auto &e : ask[i]) {    //询问
            int x = e.first, y = e.second;
            if (find(x) != find(y)) ++cnt;  //说明道路没有关闭
        }
        ans.push_back(cnt);
        for (auto &e : G[tmp[i]]) {  //处理新的路
            if (vis[e])
                continue;
            else
                join(tmp[i], e);
        }
        vis[tmp[i]] = 0;
    }
    for (auto it = ans.rbegin(); it != ans.rend(); ++it)
        cout << *it << endl;
}

比赛反思

初赛的时候就感觉做题特别吃力（出题人说相当于天梯赛 L2 难度），不出意料决赛没能晋级。其中暴露出来了许多问题，自从大二下开始把更多经历放在学习课程里，几乎做题精力都没了，组队训练也是全程划水看着大佬敲代码，自己真正动手做题的次数越来越少。决赛本来也有机会晋级，第二题就是 01 背包终极优化模板题，自己不久前还给学弟们讲的背包问题，可是比赛时就是没有想到那个常数优化留下了遗憾。

如今已经步入大三，距离考研也还剩大概 1 年多，回头看当初大一选择走上算法这条路不知道还留有多少纯真的热爱，是否背离了初心。在这个绩点皇帝盛行的时代，越来越多的人选择了中途退出，队里从原先40多个最终真正留下来的人也是寥寥几个，我这种卷心菜的算法能力原本绝对称不上合格竟然也莫名其妙当上了半年的队长，认识了一群热爱算法的大佬与学弟，亲身见证了许多竞赛的起起伏伏。我很庆幸短暂的大学时光能够收获这样一段难忘且快乐的回忆，干好一件事不容易，坚持做好更是难上加难。我斗胆认为自己正确的选择了一件事并坚持了下来，不管结局是否顺利如意，我还在路上，还在坚持，今后要脚踏实地更加认真踏实的准备即将到来的 XCPC 和蓝桥。