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;
}