Codeforces round 784 (Div. 4) (AK CF (XD) for the first time)

Although it is Div.4, But for the first time AK, Still a little excited

A. Division?

simulation

#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 Initialize to -1,map Statistics

#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

Whether the odd numbers are all odd or even , The same is true in even bits , If there is parity inconsistency, then 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

Press W piecewise , If each paragraph appears, only B Or just R, be 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

At first, I thought it was wrong , Think the dictionary tree

Open a map Save the first character as a-z The number of strings , Also open a map Save the second character as a-z The number of strings , Finally open a map Save the number of occurrences of each string , Traverse each string , The number of strings that can be paired with the current type of string is （ The first character is the same as the current string, but the second character is different add The second character is the same as the current string, but the first character is different ） Multiply The number of such strings , Use the front map The stored information to calculate , But such statistics , Each string pair will count 2 Time , Last ans/2 that will do

#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

The front and back pointers go to the middle , When both sides eat the same amount of candy, update the answer , Give priority to those who eat less , When you eat as much , Give priority to a lot of

#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

Look for stones from the bottom up of each column , If so, drop him where he can't fall

#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

Statistics n Number of occurrences per person , Greedy to follow $2^{30}$ Go to $2^0$ Meet in turn , Satisfy the i Place plus $2^i$ need $n-coun{t}_i$ Step ,$coun{t}_i$ by n Number of species $2^i$ The number of times this person appears

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