Codeforces Round 928 (Div. 4)

Shiroha白羽的博客

Shiroha · 2024-04-20 · via Shiroha白羽的博客

A. Vlad and the Best of Five

大致题意

给出五个字母，其中只有 A/B，问那个字母出现次数多

思路

简单题，统计一下就行

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        string str;
        str.resize(5);
        cin >> str;
        int cnt[2] = {};
        for (auto &i: str) ++cnt[i - 'A'];
        cout << (cnt[0] > cnt[1] ? 'A' : 'B') << endl;
    }
}

B. Vlad and Shapes

大致题意

检查一个图案是不是正方形还是三角形

思路

三角形不好检查，检查正方形就行，即四个角落都是染色的即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<string> data(n);
        for (auto &i: data) i.resize(n), cin >> i;
        int d[4] = {0, n, 0, n};
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            if (data[i][j] == '0') continue;
            d[0] = max(d[0], i);
            d[1] = min(d[1], i);
            d[2] = max(d[2], j);
            d[3] = min(d[3], j);
        }
        if (data[d[0]][d[2]] == '1' && data[d[1]][d[2]] == '1' && data[d[0]][d[3]] == '1' && data[d[1]][d[3]] == '1')
            cout << "SQUARE" << endl;
        else cout << "TRIANGLE" << endl;
    }
}

C. Vlad and a Sum of Sum of Digits

大致题意

计算 $1, n$ 之间的所有值，将其的每一个 10 进制的值相加后再相加得到的结果

思路

暴力即可，注意打表

AC code

using namespace std;void solve() {
    vector<int> data(2e5 + 10, 0);
    for (int i = 1; i < data.size(); ++i) {
        data[i] = data[i - 1];
        int t = i;
        while (t) {
            data[i] += t % 10;
            t /= 10;
        }
    }
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        cout << data[n] << endl;
    }
}

D. Vlad and Division

大致题意

给出 $n$ 个值，将其变成多个组，满足任意一个组内的任意两个值，满足他们两个值的任意比特位都不一样

思路

每个组里最多两个值，即必须是 $a_i ^ a_j = 0x7fffffff$

AC code

using namespace std;void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        map<int, int> st;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ++st[tmp];
        }
        int ans = 0;
        while (!st.empty()) {
            auto iter = st.begin();
            int a = iter->first;
            if (iter->second == 1) st.erase(iter);
            else --iter->second;
            int b = (~a) ^ (1 << 31);
            iter = st.find(b);
            if (iter != st.end()) --iter->second;
            if (iter != st.end() && iter->second == 0) st.erase(iter);
            ++ans;
        }
        cout << ans << endl;
    }
}

E. Vlad and an Odd Ordering

大致题意

有 $1, 2, 3, \dots, n$ 个数，先从小到大取出所有的奇数排成一排，
然后再取出剩下值中的，满足是一个奇数乘上一个 $2$ 的值，从小到大排成一排
然后再取出剩下值中的，满足是一个奇数乘上一个 $3$ 的值，从小到大排成一排

依此类推，直到用完，问第 $k$ 个值是多少

思路

实际上没有 $3$ 的机会了，同样的也没有 $5$ 的机会了

其实就是二进制里，把最后一位是 $1$ 的取走，然后取倒数第二位是 $1$ 的，依此类推

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        int s = 1;
        while (true) {
            int t = (n + 1) / 2;
            if (k <= t) {
                break;
            }
            k -= t;
            n -= t;
            s <<= 1;
        }
        cout << (k * 2 - 1) * s << endl;
    }
}

F. Vlad and Avoiding X

大致题意

一个 $7 \times 7 的矩阵，开始的时候一些方格已经被染成黑色，要让中间不出现 X 形状的图案，问至少需要染白多少个方格$

思路

暴力就行了

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        vector<string> data(7);
        for (auto &i: data) i.resize(7);
        for (auto &i: data) cin >> i;
        constexpr int arr[3][2] = {0, 0, 1, -1, 1, 1};
        int ans = 49;
        function<void(int)> dfs = [&](int s) {
            if (s >= ans) return;
            for (int i = 1; i < 6; ++i) for (int j = 1; j < 6; ++j)
                if (data[i - 1][j - 1] == 'B' && data[i - 1][j + 1] == 'B' &&
                    data[i + 1][j - 1] == 'B' && data[i + 1][j + 1] == 'B' && data[i][j] == 'B') {
                    for (auto &ar: arr) {
                        data[i + ar[0]][j + ar[1]] = 'W';
                        dfs(s + 1);
                        data[i + ar[0]][j + ar[1]] = 'B';
                    }
                    return;
                }
            ans = min(ans, s);
        };        dfs(0);
        cout << ans << endl;
    }
}

G. Vlad and Trouble at MIT

大致题意

有一棵树，有些节点上的人要播放音乐，有一些节点上的人要睡觉，有一些则无所谓

现在需要创建一些墙使得放英语的人不会吵到睡觉的人，音乐会随着树的边传播，墙只能创建在边上，问最少需要多少个墙

思路

树上搜索即可，如果当前节点是要播放音乐的，那么和它的所有要播放音乐或者无所谓的节点都可以连在一块，反之也一样。
但是如果是无所谓的人，那么就要看它的直接孩子节点中要播放音乐的多还是要睡觉的多了

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        string str;
        str.resize(n);
        for (int i = 1; i < n; ++i) {
            int tmp;
            cin >> tmp;
            g[tmp - 1].push_back(i);
        }
        cin >> str;        int ans = n - 1;
        function<int(int)> dfs = [&](int c) {
            if (g[c].empty()) {
                return str[c] == 'P' ? 1 : (str[c] == 'C' ? 2 : 0);
            }
            int cnt[3] = {};
            for (const auto &n: g[c]) ++cnt[dfs(n)];
            if (str[c] == 'P') {
                ans -= cnt[1] + cnt[2];
                return 1;
            } else if (str[c] == 'S') {
                ans -= cnt[0] + cnt[2];
                return 0;
            } else {
                if (cnt[0] > cnt[1]) {
                    ans -= cnt[0] + cnt[2];
                    return 0;
                } else if (cnt[1] > cnt[0]) {
                    ans -= cnt[1] + cnt[2];
                    return 1;
                } else {
                    ans -= cnt[0] + cnt[2];
                    return 2;
                }
            }
        };
        dfs(0);
        cout << ans << endl;
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客

A. Vlad and the Best of Five

大致题意

思路

AC code

B. Vlad and Shapes

大致题意

思路

AC code

C. Vlad and a Sum of Sum of Digits

大致题意

思路

AC code

D. Vlad and Division

大致题意

思路

AC code

E. Vlad and an Odd Ordering

大致题意

思路

AC code

F. Vlad and Avoiding X

大致题意

思路

AC code

G. Vlad and Trouble at MIT

大致题意

思路

AC code