Codeforces Round #827 (Div. 4) A-G

• 2022 年 10 月 29 日
• 筆記
• CF

比賽鏈接

A

題解

知識點：模擬。

時間複雜度 \(O(1)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b == c || a + c == b || b + c == a) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

題解

知識點：枚舉。

查重即可。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    set<int> st;
    bool ok = 1;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        if (st.count(x)) ok = 0;
        st.insert(x);
    }
    if (ok) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

題解

知識點：貪心。

行紅，列藍別搞錯。

時間複雜度 \(O(1)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

char dt[10][10];
bool solve() {
    for (int i = 1;i <= 8;i++)
        for (int j = 1;j <= 8;j++)
            cin >> dt[i][j];
    for (int i = 1;i <= 8;i++) {
        bool ok = 1;
        for (int j = 1;j <= 8;j++) ok &= dt[i][j] == 'R';
        if (ok) {
            cout << 'R' << '\n';
            return true;
        }
    }
    for (int j = 1;j <= 8;j++) {
        bool ok = 1;
        for (int i = 1;i <= 8;i++) ok &= dt[i][j] == 'B';
        if (ok) {
            cout << 'B' << '\n';
            return true;
        }
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

題解

知識點：枚舉，數論。

注意到 \(a_i \in [1,1000]\) ，因此貪心地記錄 \(a_i\) 最後一次的位置，枚舉 \([1,1000]\) 每個數的組合即可。

時間複雜度 \(O(n+1000^2)\)

空間複雜度 \(O(1000)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int vis[1007];
bool solve() {
    int n;
    cin >> n;
    memset(vis, 0, sizeof(vis));
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        vis[x] = max(vis[x], i);
    }
    int ans = -1;
    for (int i = 1;i <= 1000;i++) {
        if (!vis[i]) continue;
        for (int j = i;j <= 1000;j++) {
            if (!vis[j]) continue;
            if (__gcd(i, j) == 1) ans = max(ans, vis[i] + vis[j]);
        }
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

E

題解

知識點：二分，前綴和，枚舉。

預處理前綴和方便輸出答案，前綴最大值方便找到最大合法段，然後二分查詢第一個大於 \(x\) 的位置 \(i\) ，則 \([1,i-1]\) 都可以。

時間複雜度 \(O(n+q\log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a[200007], mx[200007];
bool solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        mx[i] = max(mx[i - 1], a[i]);
        a[i] += a[i - 1];
    }
    while (q--) {
        int x;
        cin >> x;
        int pos = upper_bound(mx + 1, mx + 1 + n, x) - mx - 1;
        cout << a[pos] << ' ';
    }
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

F

題解

知識點：貪心。

我們可以任意排列且 \(s,t\) 初始有 a ，那麼如果 \(t\) 具有超過 a 的字母，那麼一定可以有 \(s<t\) ；否則，如果 \(s\) 也沒有超過 a 的字母且 \(s\) 長度小於 \(t\) ，那麼一定可以有 \(s<t\) ；否則一定有 \(t<s\) 。

時間複雜度 \(O(q+\sum |s|)\)

空間複雜度 \(O(|s|)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int q;
    cin >> q;
    ll cnts = 0, cntt = 0;
    bool sbad = 0, tgood = 0;
    while (q--) {
        int d, k;
        string x;
        cin >> d >> k >> x;
        if (d == 1) {
            for (auto ch : x) {
                cnts += k * (ch == 'a');
                sbad |= ch != 'a';
            }
        }
        else {
            for (auto ch : x) {
                cntt += k * (ch == 'a');
                tgood |= ch != 'a';
            }
        }
        if (tgood) cout << "YES" << '\n';
        else if (!sbad && cnts < cntt) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

G

題解

知識點：位運算，貪心，枚舉。

用 \(val\) 記錄目前哪個位置還缺 \(1\) 。每次枚舉沒有取過的數字，找到一個數 \(a[pos]\) 使 a[pos] & val 最大，表示有效位組成最大的數字。然後取出來，並通過 val &= ~a[pos] 把 \(val\) 中對應的 \(1\) 刪除（把 \(a[pos]\) 取反，原來的 \(1\) 現在都為 \(0\) ，然後與 \(val\) 就能刪掉 \(val\) 對應的 \(1\)）。最後把 \(a[pos]\) 交換到末尾的有效數字，實現邏輯刪除。

因為 int 有 \(31\) 位，每次刪除刪的是結果最大的，最多刪除 \(31\) 次就能達到這個序列或的最大值。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int val = ~(1 << 31);
    for (int i = 1;i <= min(31, n);i++) {
        int pos = 1;
        for (int j = 1;j <= n - i + 1;j++) {
            if ((val & a[j]) > (val & a[pos])) pos = j;
        }
        cout << a[pos] << ' ';
        val &= ~a[pos];
        swap(a[n - i + 1], a[pos]);
    }
    for (int i = 1;i <= n - min(31, n);i++) cout << a[i] << ' ';
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}