Kickstart 2021 Round A

发表于 更新于 分类于 阅读次数：

比赛链接：Kickstart 2021 Round A

K-Goodness String

统计 \(S_i \neq S_{N-i+1}\) 的个数记为 \(C\)，目标分数为 \(K\)，故至少要改 \(|C - 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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000 + 5;

int T, N, K;
char s[MAX_N];

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &N, &K);
        getchar();
        scanf("%s", s);

        int cnt = 0;
        for (int i = 0; i < N / 2; ++i) {
            if (s[i] != s[N - i - 1]) {
                ++cnt;
            }
        }

        printf("Case #%d: %d\n", cs, abs(cnt - K));
    }

    return 0;
}

L Shaped Plots

统计每个格子四个方向连续的 \(1\) 的个数。对于每个格子形成的 \(L\) 有四种情况：

  • \(L\) 的尖角朝右上
  • \(L\) 的尖角朝右下
  • \(L\) 的尖角朝左上
  • \(L\) 的尖角朝左下

对于每种情况，记长边为 \(l\)，短边为 \(s\)。

  • 如果在长边上构造 \(L\) 的长边，短边上构造 \(L\) 的短边，那么这个点的贡献是 \[ \max \{ \min \{ \lfloor \frac{l}{2} \rfloor , s \} - 1, 0 \} \]
  • 如果在短边上构造 \(L\) 的长边，长边上构造 \(L\) 的短边，那么这个点的贡献是 \[ \max \{ \lfloor \frac{s}{2} \rfloor, 0 \} \]
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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000 + 5;

int T, R, C;
int cell[MAX_N][MAX_N];
int LR[MAX_N][MAX_N], RL[MAX_N][MAX_N], UD[MAX_N][MAX_N], DU[MAX_N][MAX_N];

void calculate_lr() {
    for (int i = 0; i < R; ++i) {
        LR[i][0] = cell[i][0];
        for (int j = 1; j < C; ++j) {
            LR[i][j] = cell[i][j] ? LR[i][j - 1] + cell[i][j] : 0;
        }
    }
}

void calculate_rl() {
    for (int i = 0; i < R; ++i) {
        RL[i][C - 1] = cell[i][C - 1];
        for (int j = C - 2; j >= 0; --j) {
            RL[i][j] = cell[i][j] ? RL[i][j + 1] + cell[i][j] : 0;
        }
    }
}

void calculate_ud() {
    for (int j = 0; j < C; ++j) {
        UD[0][j] = cell[0][j];
        for (int i = 1; i < R; ++i) {
            UD[i][j] = cell[i][j] ? UD[i - 1][j] + cell[i][j] : 0;
        }
    }
}

void calculate_du() {
    for (int j = 0; j < C; ++j) {
        DU[R - 1][j] = cell[R - 1][j];
        for (int i = R - 2; i >= 0; --i) {
            DU[i][j] = cell[i][j] ? DU[i + 1][j] + cell[i][j] : 0;
        }
    }
}

long long grid_contribute(int x, int y) {
    long long contribute = 0;
    int l = max(x, y), s = min(x, y);

    contribute += max(min(l / 2, s) - 1, 0);
    contribute += max(s / 2 - 1, 0);

    return contribute;
}

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &R, &C);
        
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                scanf("%d", &cell[i][j]);
            }
        }

        calculate_lr();
        calculate_rl();
        calculate_du();
        calculate_ud();

        long long ans = 0;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                ans += grid_contribute(LR[i][j], UD[i][j]);
                ans += grid_contribute(LR[i][j], DU[i][j]);
                ans += grid_contribute(RL[i][j], UD[i][j]);
                ans += grid_contribute(RL[i][j], DU[i][j]);
            }
        }

        printf("Case #%d: %lld\n", cs, ans);
    }

    return 0;
}

Rabbit House

用大根堆维护所有位置的高度，从最高的开始出堆，每个出堆的元素拓展周围的四个元素：

  • 如果已经满足高度差小于等于 \(1\)，则不管
  • 如果不满足的，则把新元素的高度改成老元素 \(-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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300 + 5;

int T, R, C;
int grid[MAX_N][MAX_N];

struct Position {
    int x, y, g;

    friend bool operator < (const Position &u, const Position &v) {
        return u.g < v.g;
    }
};

priority_queue<Position> q;

int check_position(int x, int y, int v) {
    
    if (!(x >= 0 && x < R && y >= 0 && y < C)) {
        return 0;
    }
    // printf("(x = %d, y = %d, v = %d)\n", x, y, v);

    int contribution = 0;

    // v >= grid[x][y]
    if (v - grid[x][y] > 1) {
        contribution += (v - grid[x][y] - 1);
        grid[x][y] = v - 1;
        q.push({x, y, grid[x][y]});
    }

    return contribution;
}

int main() {
    scanf("%d", &T);
    
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &R, &C);

        while (!q.empty()) {
            q.pop();
        }

        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                scanf("%d", &grid[i][j]);
                q.push({i, j, grid[i][j]});
            }
        }

        long long ans = 0;

        while (!q.empty()) {
            auto f = q.top();
            q.pop();

            if (f.g != grid[f.x][f.y]) {
                continue;
            }

            ans += check_position(f.x - 1, f.y, f.g);
            ans += check_position(f.x + 1, f.y, f.g);
            ans += check_position(f.x, f.y + 1, f.g);
            ans += check_position(f.x, f.y - 1, f.g);
        }

        printf("Case #%d: %lld\n", cs, ans);
    }

    return 0;
}

Checksum

把行号和列号看作节点，如果 \(A(i, j) = -1\) 就在 \(i\) 和 \(j\) 之间建边，权为 \(B(i, j)\)。因此，如果某一个点只有一条边，说明该行 / 列只有一个元素未知，可以直接推断出来。如果某个点没有边，说明该行 / 列没有未知元素。我们知道「可推断」的前提条件是该行 / 列只有一个元素是未知的，我们可以先通过「推断」删除图中所有度为 \(1\) 的节点，接着又多了一批新的度为 \(1\) 的节点。因此如果一直这么删下去，可以把整张图删完，就说明所有的未知点都可以通过推断得到，但是有可能删不完——因为可能存在环。只有图是一棵树的时候，才能删完，即可以推断得到所有点。因此我们要把图中删去一些边，使得剩下的边变成一棵树，我们要让删除的边的权的总和最小。

记所有边的权值和为 \(t\)，图的最大生成树为 \(m\)，则删除边的最小权值和为 \(t - m\)。

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500 + 5;

int T, N, _;
int A[MAX_N][MAX_N], B[MAX_N][MAX_N];

struct Edge {
    int from, to, v;

    friend bool operator < (const Edge &u, const Edge &v) {
        return u.v > v.v;
    }
};

vector<Edge> edges;

struct DisjointSet {
    // r + c => MAX_N * 2
    int f[MAX_N * 2];

    void init(int n) {
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
    }

    int find(int u) {
        return f[u] == u ? u : f[u] = find(f[u]);
    }

    void merge(int u, int v) {
        f[find(u)] = find(v);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }
} d;

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d", &N);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                scanf("%d", &A[i][j]);
            }
        }

        for (int i= 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                scanf("%d", &B[i][j]);
            }
        }

        for (int i = 0; i < 2 * N; ++i) {
            scanf("%d", &_);
        }

        long long tot = 0;
        edges.clear();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == -1) {
                    edges.push_back({i, j + N, B[i][j]});
                    tot += B[i][j];
                }
            }
        }

        // MAXIMUM spanning tree
        d.init(2 * N + 5);
        long long mst = 0;
        sort(edges.begin(), edges.end());
        for (const Edge &e: edges) {
            if (!d.same(e.from, e.to)) {
                mst += e.v;
                d.merge(e.from, e.to);
            }
        }

        printf("Case #%d: %lld\n", cs, tot - mst);
    }

    return 0;
}