AcWing 第1場周賽

競賽 - AcWing

3577 選擇數(shù)字

3577. 選擇數(shù)字 - AcWing題庫

樸素

暴力兩層循環(huán)

#include <cstdio>
#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 101;
int a[N], b[N];

int main() {
    int n, m;
    cin >> n;
    unordered_set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        s.insert(b[i]);
    }
    // ^ 兩層遍歷
    for (int i = 0; i < n; i++)
        for (int k = 0; k < m; k++) {
            if (!s.count(a[i] + b[k])) {
                cout << a[i] << " " << b[k] << endl;
                return 0;
            }
        }

    return 0;
}

優(yōu)美

兩個數(shù)組的最大值相加一定是新數(shù)

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 101;
int a[N], b[N];

int main() {
    int n, m, a_max = 0, b_max = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a_max = max(a[i], a_max);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        b_max = max(b[i], b_max);
    }
    cout << a_max << " " << b_max;
    return 0;
}

3578 ?最大中位數(shù)

3578. 最大中位數(shù) - AcWing題庫

整數(shù)二分問題。求中位數(shù)，并依次遞增，計算所需的操作次數(shù)。求最后一個操作次數(shù)總和 <= k 的中位數(shù)值

• 如果 mid - a[i] < 0 ，意味著該數(shù)比中位數(shù)大，不需要操作
• int 范圍 2.174e9，二分過程中計算 (l+r) 可能超過 2.174e9，改用 long 存儲

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int a[N], n;
long k;

long check(long mid) {
    long res = 0;
    for (int i = n >> 1; i < n; i++) {
        res += (mid - a[i] > 0 ? mid - a[i] : 0);
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    long l = a[n >> 1], r = 2e9;
    while (l < r) {
        long mid = l + r + 1 >> 1;
        if (check(mid) <= k)
            l = mid;
        else
            r = mid - 1;
    }
    cout << l;
    return 0;
}

2579 ??數(shù)字移動

AcWing 3579. 數(shù)字移動 - AcWing

每個點的出度和入度都為 1，每組交換都會形成一個閉環(huán)。每個環(huán)的節(jié)點數(shù)就是每個元素回到原來位置需要經(jīng)過的交換次數(shù)

采用并查集維護各個連通塊（環(huán)）的連通性，然后在并查集的根節(jié)點額外維護該并查集的節(jié)點個數(shù)

難點文章來源地址http://www.zghlxwxcb.cn/news/detail-695074.html

• 合并兩個根節(jié)點的時候，把其中一個根節(jié)點維護的并查集元素數(shù)量s[pu]累加到另一個并查集的根節(jié)點中
• 最后輸出包含 i 的連通塊數(shù)量，也就是 s[find(i)]

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

using namespace std;
const int N = 2e5 + 10;
int p[N], s[N];  // s 記錄每個連通塊的數(shù)量
int t, n;

int find(int u) {
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main() {
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            s[i] = 1;
        }
        for (int u = 1; u <= n; u++) {
            int x;
            cin >> x;
            int px = find(x), pu = find(u); 
            if (px != pu) { // 使px跟pu在同一個連通塊
                s[px] += s[pu];
                p[pu] = px;
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << s[find(i)] << " ";
        }
        cout << endl;
    }

    return 0;
}

到了這里，關(guān)于C++ 算法競賽、01 周賽篇 | AcWing 第1場周賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！