Dashboard - Codeforces Round 827 (Div. 4) - Codeforces

A Sum

简单题

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b == c || a + c == b || b + c == a)cout << "YES" << endl;
    else cout << "NO" << endl;
}

B Increasing

用个桶存一下看看有没有重复的元素，有一定不行

void solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        mp[x]++;
    }
    for (auto [x, y]: mp) {
        if (y > 1) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

C Stripes

判断每一行和每一列有没有8个B或R的就行

char g[N][N];

void solve() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> g[i][j];
        }
    }
    for (int i = 0; i < 8; i++) {
        int cnt = 0;
        for (int j = 0; j < 8; j++) {
            if (g[i][j] == 'R')cnt++;
        }
        if (cnt == 8) {
            cout << 'R' << endl;
            return;
        }
    }
    for (int i = 0; i < 8; i++) {
        int cnt = 0;
        for (int j = 0; j < 8; j++) {
            if (g[j][i] == 'B')cnt++;
        }
        if (cnt == 8) {
            cout << 'B' << endl;
            return;
        }
    }
}

D Coprime

vp的时候二逼了，想复杂了，重复的数没有意义，用map村每个元素坐标的最大值就行，再\(O(\)\(x^{2}\)\()\)直接暴力的判断一下就可以了

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mp[a[i]] = max(i, mp[a[i]]);
    }
    int ans = 0;
    for (auto [x, y]: mp) {
        for (auto [i, j]: mp) {
            if (gcd(x, i) == 1)ans = max(ans, y + 1 + j + 1);
        }
    }
    if (ans == 0)ans = -1;
    cout << ans << endl;
}

E Scuza

题意：有q此询问，每次给出可以走上多高的楼梯，问最多可以走到多高的距离

思路：我们可以先把每个楼梯进行求前缀和，再进行前缀最大值处理，用每次给的值去再前缀最大的数组里二分，找到第一个大于的值，前一个位置的前缀和就是答案

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i], s[i] = s[i - 1] + a[i];
    for (int i = 2; i <= n; i++)a[i] = max(a[i], a[i - 1]);
    while (q--) {
        int k;
        cin >> k;
        if (k >= a[n])cout << s[n] << ' ';
        else if (k < a[1])cout << 0 << ' ';
        else {
            int pos = upper_bound(a.begin() + 1, a.end(), k) - (a.begin() + 1);
            cout << s[pos] << ' ';
        }
    }
    cout << endl;
}

F Smaller

题意：给你两个字符串\(S\)和\(T\)初始值都为a，每次会对其中一个字符串进行扩展，意思就是再原先的字符串上加给的字符串，问两个重新排列\(S\)和\(T\)，能否是\(S\)的字典序小于\(T\)

思路：用两个map记录两个字符串出现的字母种类和数量，只要\(T\)的最大字母不为a就可以，否则如果\(S\)的a的数量小于\(T\)的数量并且两个的最大字母都是a可以，否则不行，，如果\(S\)的a的数量大于等于\(T\)的数量不可以

void solve() {
    string s = "a", t = "a";
    map<char, int> mps, mpt;
    mps['a']++;
    mpt['a']++;
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        string str;
        cin >> n >> k >> str;
        for (auto i: str) {
            if (n == 1)mps[i] += k;
            if (n == 2)mpt[i] += k;
        }
        char opt = 'a';
        char ops = 'a';
        for (auto [x, y]: mpt)opt = max(opt, x);
        for (auto [x, y]: mps)ops = max(ops, x);
        if (opt == 'a') {
            if (ops != 'a')cout << "NO" << endl;
            else {
                if (mps['a'] < mpt['a'])cout << "YES" << endl;
                else cout << "NO" << endl;
            }

        } else cout << "YES" << endl;
    }
}

G Orray

题意：给你一组数，让你把他们重新排列以后是的前缀或数组的字典序最大
思路：要让字典序最大，所以我们尽可能让前面的数变大，在二进制下面我们就是让数的每一位尽可能都变成1，那我们最多会操作31次，int的最大二进制位数是31位，所以我们暴力的去找31次再数组里还没有用用过的值和目前的值或起来的最大值就行了，剩下的数随便输出没有关系

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<bool> vis(n + 1, false);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < 31; i++) {
        int res = ans;
        int idx=-1;
        for (int j = 0; j < n; j++) {
            if (vis[j])continue;
            if ((a[j] | ans) > res) {
                res = (ans | a[j]);
                idx = j;
            }
        }
        if(idx==-1)break;
        vis[idx] = true;
        ans |= a[idx];
        cout << a[idx] << ' ';
    }
    for (int i = 0; i < n; i++)if (!vis[i])cout << a[i] << ' ';
    cout << endl;
}