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