2024牛客寒假算法基础集训营2

发表于 更新于 分类于 阅读次数： 本文字数： 748 阅读时长 ≈ 3 分钟
It is not our abilities that show what we truly are, it is our choices. — Harry Potter and the Chamber of Secrets

A. Tokitsukaze and Bracelet

思路：

  • 打表累加即可

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int r = 0;
    std::unordered_map<int, int> h;
    for (int i = 29; i <= 32; i++) {
        h[i] = r;
    }
    r++;
    for (int i = 34; i <= 40; i += 2) {
        h[i] = r;
    }
    h[45] = 2;
    h[100] = 0, h[150] = 1, h[200] = 2;

    for (int i = 0; i < n; i++) {
        int ans = 0;
        int a, b, c;
        std::cin >> a >> b >> c;

           ans += h[a];
           ans += h[b];
           ans += h[c];
        std::cout << ans << "\n";
    }

    return 0;
}

B. Tokitsukaze and Cats

思路：

  • 搜一下当前哪个点的旁边有多少 个点相邻，然后这个数量和答案的关系是 ​

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, k;
    std::cin >> n >> m >> k;

    std::queue<std::array<int, 3>> q;
    std::vector g(n + 4, std::vector<char>(m + 4, '*'));
    for (int i = 0; i < k; i++) {
        int a, b;
        std::cin >> a >> b;
        g[a][b] = '#';
        q.push({a, b, 0});
    }

    int ans = 0;
    std::array<int, 4> dx {-1, 1, 0, 0}, dy {0, 0, 1, -1};
    std::vector vis(n + 4, std::vector<int>(m + 4));
    while (q.size()) {
        auto [x, y, w] = q.front();
        q.pop();

        if (w == 1) break;

        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x, b = dy[i] + y, c = w;
            if (a < 0 || a > n + 2 || b < 0 || b > m + 2) continue ;
            if (vis[a][b]) continue ;
            if (g[a][b] == '#') ans -= 1;
            vis[x][y] = true;
            q.push({a, b, c + 1});
        }
    }

    std::cout << k * 4 + ans << "\n";
    
    return 0;
}

E. Tokitsukaze and Eliminate (easy)

思路：

  • 由于就两个颜色，直接用双端队列模拟即可

时间复杂度：

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
void solve() {
    int n;
    std::cin >> n;

    std::deque<int> a, b;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;

        if (x == 1) {
            a.push_back(i);
        } else {
            b.push_back(i);
        }
    }

    int ans = 0;
    while (a.size() && b.size()) {
        int t = std::min(a.back(), b.back());
        bool f = false;
        if (a.back() == t) {
            a.pop_back();
            while (b.size() && b.back() > t) {
                b.pop_back();
                f = true;
            }
            if (f) ans++;
        } else if (b.back() == t) {
            b.pop_back();
            while (a.size() && a.back() > t) {
                a.pop_back();
                f = true;
            }
            if (f) ans++;
        }
    }
    ans += a.size() + b.size();
    std::cout << ans << "\n";
}

F. Tokitsukaze and Eliminate (hard)

思路：

时间复杂度：

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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    std::vector<std::vector<int>> g(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        g[a[i]].emplace_back(i);
    }

    std::priority_queue<std::pair<int, int>> q;
    for (int i = 1; i <= n; i++) {
        if (g[i].size()) {
            q.emplace(-g[i].back(), i);
        }
    }

    int cur = n, res = 0;
    while (q.size()) {
        auto [x, y] = q.top();
        q.pop();

        x *= -1;
        if (x > cur)  continue ;
        res++;
        while (cur >= x) {
            g[a[cur]].pop_back();
            if (!g[a[cur]].empty()) {
                q.emplace(-g[a[cur]].back(), a[cur]);
            }
            cur--;
        }
    }
    std::cout << res << "\n";
}

I. Tokitsukaze and Short Path (plus)

思路：

  • 可以发现这公式就是把那个点 了，然后结果就是后 个数的和与 ​ 的和

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        a[i] *= 2;
        s[i + 1] = s[i] + a[i];
    }

    i64 res = std::accumulate(a.begin() + 1, a.end(), 0LL);
    for (int i = 1; i < n; i++) {
        res += (s[n] - s[i]) + 1LL * (i - 1) * a[i];
    }
    std::cout << res << "\n";
}

J. Tokitsukaze and Short Path (minus)

思路：

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    i64 res = 0;
    for (int i = 0; i < n; i++) {
        res += 1LL * std::min(a[i], 2 * a[0]) * (n - i - 1);
    }
    std::cout << 4 * res << "\n";
}