AcWing 第87场周赛题解

T1 移动棋子

算出为 \(1\) 的点离 \((3, 3)\) 的距离即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int px = -1, py = -1;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            int x;
            cin >> x;
            if (x) px = i, py = j;
        }
    }
    cout << abs(px - 3) + abs(py - 3) << '\n';
    return 0;
}

T2 打怪兽

可以从 \(1\) 枚举到 \(n\) 表示要打多少个怪兽。

因为你要打 \(t\) 个怪兽，并不管顺序，所以我们可以对 \([1, t]\) 这一段进行排序，然后计算 \(a[t], a[t - 2], a[t - 4], \dots\) 即可（因为你要干掉第 \(t\) 个怪兽的时候，必须要使用 \(a[t]\) 的法力值，因为排过序，所以连着 \(t - 1\) 一起干掉就可以了，对于编号小于 \(t\) 的也可以这么干）。

注意每一次都进行快速排序反而会更慢，我们采用插入排序，每次插入新来的数字即可，插入的时间复杂度: \(O(n)\)。

总时间复杂度：\(O(n^2)\)。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int a[N];

bool check(int k) {
    a[0] = -0x3f3f3f3f;
    int p = k;
    while (a[p] < a[p - 1]) {
        swap(a[p], a[p - 1]);
        p--;
    }
    int res = 0;
    for (int i = k; i >= 1; i -= 2) res += a[i];
    if (res <= m) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        if (!check(i)) {
            cout << i - 1 << '\n';
            return 0;
        }
    }
    cout << n << '\n';
    return 0;
}

T3 最远距离

请看：

我们规定，如果一个无向连通图满足去掉其中的任意一条边都会使得该图变得不连通，则称该图为有效无向连通图。

去掉一条边就不连通了，这不就是树吗？

（否则如果是图（就是不是树的图）的话，一定有环，拆了一条边从另一端还可以去，就不会不连通了）。

那么最长距离就变为：树的直径了。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

struct Edge {
    int to, next;
}e[M];

int head[N], idx;

void add(int a, int b) {
    idx++, e[idx].to = b, e[idx].next = head[a], head[a] = idx;
}

void dfs(int u, int fa, int& maxver, int& maxstep, int step) {
    if (maxstep < step) {
        maxstep = step;
        maxver = u;
    }
    for (int i = head[u]; i; i = e[i].next) {
        int to = e[i].to;
        if (to == fa) continue;
        dfs(to, u, maxver, maxstep, step + 1);
    }
}

int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    // dfs(1, 0);
    int mv = 0, ms = 0, mv1 = 0, ms1 = 0;
    dfs(1, 0, mv, ms, 1);
    dfs(mv, 0, mv1, ms1, 1);
    cout << ms1 - 1 << '\n';
    return 0;
}