WillHou's Blog
0%

【题解】AcWing 第73场周赛题解

发表于 分类于 Valine：
AcWing 第73场周赛题解

A. 数对

题目链接：AcWing 4704. 数对

没啥好说的，题目意思都给你写在脸上了。直接暴力 \(\mathcal{O}(N^2)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
const int N = 1009;
int n, d, ans, a[N];
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (abs(a[i] - a[j]) <= d)
                ans++;
    printf("%d", ans - n);
    // 最后 -n 是因为要除去 i==j 的情况
    return 0;
}

B. 矩阵

题目链接：AcWing 4705. 矩阵

旋转之后，顺时针遍历矩阵的最小字典序的排列是不变的。

所以只需要顺时针遍历这个矩阵，然后将其最小字典序的排列加入一个 set 容器中自动去重，最后输出这个容器的大小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int n;
string s, t;
set<string> SET;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        if (i != 1) cin >> s;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        s += t;
        string temp = s;
        for (int i = 1; i <= 4; i++) {
            rotate(temp.begin(), temp.begin() + 1, temp.end());
            s = min(s, temp);
        }
        SET.insert(s);
    }
    cout << SET.size();
    return 0;
}

C. 最短路程

题目链接：AcWing 4706. 最短路程

一眼思维题，模拟几组样例即可发现规律。

通过模拟一些树，即可发现：除了起点到终点的这些边走了一次，其他的边都被走了两次。所以，想要最终的路径长度最小，只需要保证 \(1\) 号点到终点路径最长即可。直接 \(\texttt{dfs}\) 求解，时间复杂度 \(\mathcal{O}(N)\)。

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
#include <iostream>
using LL = long long;
const int N = 1e5 + 9;
int n, hd[N];
LL ans;
struct Edge {
    int to, nx, wt;
} eg[N << 1];
void addE(int u, int v, int w, int c) {
    eg[c] = {v, hd[u], w}, hd[u] = c;
}
int dfs(int u, int fa) {
    int res = 0;
    for (int i = hd[u]; i; i = eg[i].nx) {
        int v = eg[i].to;
        if (v == fa) continue;
        res = std::max(res, dfs(v, u) + eg[i].wt);
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y, w; i < n; i++) {
        scanf("%d%d%d", &x, &y, &w);
        addE(x, y, w, i << 1);
        addE(y, x, w, i << 1 | 1);
        ans += w * 2;
    }
    printf("%lld\n", ans - dfs(1, 0));
    return 0;
}