[数据结构与算法]Codeforces Round #784 (Div. 4)题解 （第一次AK cf （XD

虽然是Div.4，但是第一次AK，还是有点小激动

A. Division?

模拟

#include <bits/stdc++.h>
using namespace std;

string f(int n) {
    if (n <= 1399) return "Division 4";
    if (n <= 1599) return "Division 3";
    if (n <= 1899) return "Division 2";
    return "Division 1";
}

void solve() {
    int n;
    cin >> n;
    cout << f(n) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

B. Triple

ans初始化为-1，map统计

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;

void solve() {
    mp.clear();
    int n;
    cin >> n;
    int ans = -1;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ++mp[a];
        if (mp[a] >= 3) ans = a;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C. Odd/Even Increments

统计奇数位上是不是都是奇数或都是偶数，偶数位上也是如此，若存在奇偶性不一致则NO

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int oo = 0, jj = 0;
    for (int i = 0; i < n; i++) {
        if ((i & 1) && (a[i] & 1)) jj++;
        if (!(i & 1) && !(a[i] & 1)) ++oo;
    }
    if ((jj == 0 || jj == n / 2) && (oo == 0 || oo == n / 2 + (n & 1)))
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D. Colorful Stamp

按W分段，每段若出现只出现B或只出现R，则NO

#include <bits/stdc++.h>
using namespace std;
string s;

void solve() {
    int n;
    cin >> n;
    cin >> s;
    int r = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') ++r;
        if (s[i] == 'B') ++b;
        if (s[i] == 'W' || i == n - 1) {
            if ((r > 0 && !b) || (b > 0 && !r)) {
                cout << "NO\n";
                return;
            }
            r = 0, b = 0;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

E. 2-Letter Strings

一开始想歪了，以为字典树

开个map存第一个字符为a-z的串个数，同样开个map存第二个字符为a-z的串个数，最后开个map存每种字符串出现次数，遍历每种串，与当前该种串能成对个串数为（第一个字符和当前串相同但第二个字符不同的 加上 第二个字符和当前串相同但第一个字符不同的）乘上 该种串的数量，用前面map存的信息来计算，但这样统计，每个串对会统计2次，最后ans/2即可

#include <bits/stdc++.h>
using namespace std;

#define ll long long

// ll trie[1000005][31];
map<char, ll> mp1, mp2;
map<string, ll> mp;
// ll cnt;
// char s[5];
string s;
void solve() {
    mp.clear();
    mp1.clear();
    mp2.clear();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s;
        ++mp1[s[0]];
        ++mp2[s[1]];
        ++mp[s];
        // insert(s, 2);
    }
    ll ans = 0;
    for (auto v : mp) {
        ans += (mp1[v.first[0]] - v.second) * v.second;
        ans += (mp2[v.first[1]] - v.second) * v.second;
    }
    ans /= 2;
    cout << ans << '\n';
    // for(int i=0;i<)
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

F. Eating Candies

前后两个指针往中间走，当两边吃的糖果一样多就更新答案，优先走吃的少的，当吃的一样多，优先走大堆的

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 0, r = n - 1;
    ll lw = a[0], rw = a[n - 1];
    ll ans = 0;
    while (1) {
        if (l == r) break;
        if (lw == rw) ans = l - 0 + 1 + n - r;
        if (l == r - 1) break;
        if (lw > rw) {
            --r;
            rw += a[r];
        } else if (rw > lw) {
            ++l;
            lw += a[l];
        } else {
            if (a[l + 1] > a[r - 1]) {
                ++l;
                lw += a[l];
            } else {
                --r;
                rw += a[r];
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

G. Fall Down

从每列最下往上找石子，有就将他下落到不能落之处

#include <bits/stdc++.h>
using namespace std;
char s[55][55];

int n, m;
void d(int x, int y) {
    for (int i = x + 1; i < n; i++) {
        if (s[i][y] == '.') {
            s[i][y] = '*';
            s[i - 1][y] = '.';
        } else
            break;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        // cout << s[i] << '\n';
    }
    for (int i = 0; i < m; i++) {
        for (int j = n - 1; j >= 0; j--) {
            if (s[j][i] == '*') {
                d(j, i);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << s[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

H. Maximal AND

统计n个数每位出现的次数，贪心从$2^{30}$往$2^0$依次满足，满足第i位加上$2^i$需要$n?coun{t}_i$步，$coun{t}_i$为n个数种$2^i$这位出现的次数

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
void solve() {
    mp.clear();
    int n, k;
    cin >> n >> k;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        int idx = 0;
        while (a) {
            if (a & 1) ++mp[idx];
            ++idx;
            a >>= 1;
        }
    }
    int ans = 0;
    for (int i = 30, t = 1 << 30; i >= 0; i--, t >>= 1) {
        int q = n - mp[i];
        if (k >= q) {
            k -= q;
            ans += t;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

阅读世界，共赴山海

423全民读书节，邀你共读