Codeforces Round 784 (Div. 4)

发表于 2024-01-31 更新于 2024-07-19 分类于题解阅读次数：本文字数： 1.1k 阅读时长 ≈ 4 分钟

Sweat is the lubricant of success.

A. Division?

思路：

写判断结构即可

时间复杂度：\(O(1)\)

void solve() {
    int r;
    std::cin >> r;

    std::string ans;
    if (r >= 1900) {
        ans = "Division 1";
    } else if (r >= 1600 && r < 1900) {
        ans = "Division 2";
    } else if (r >= 1400 && r < 1600) {
        ans = "Division 3";
    } else {
        ans = "Division 4";
    }
    std::cout << ans << "\n";
}

B. Triple

思路：

输出任何一个出现次数大于3的数即可

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        cnt[x]++;
    }
    for (auto [x, y] : cnt) {
        if (y >= 3) {
            std::cout << x << "\n";
            return ;
        }
    }
    std::cout << "-1\n";
}

C. Odd/Even Increments

思路：

如果序列中出现某个数的下标的奇偶性相同，但这两个数的奇偶性不同，那么一定不行

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> odd, even;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        if (i % 2 == 0) {
            odd.push_back(x);
        } else {
            even.push_back(x);
        }
    }

    for (int i = 0; i < odd.size(); i++) {
        if ((odd[i] + odd[0]) % 2 == 1) {
            std::cout << "NO\n";
            return ;
        }
    }
    for (int i = 0; i < even.size(); i++) {
        if ((even[i] + even[0]) % 2 == 1) {
            std::cout << "NO\n";
            return ;
        }
    }
    std::cout << "YES\n";
}

D. Colorful Stamp

思路：

去重然后判断白色和白色之间是否存在单色的方块，例如WBW或者WRW
注意首尾特判

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    s.erase(std::unique(s.begin(), s.end()), s.end());

    if (s.size() == 1 && s[0] != 'W') {
        std::cout << "NO\n";
        return ;
    } else if (s.size() == 2) {
        if (s.find('W') != -1) {
            std::cout << "NO\n";
            return ;
        }
    }
    
    n = s.size();
    if ((s[0] != 'W' && s[1] == 'W') || (s[n - 1] != 'W' && s[n - 2] == 'W')) {
        std::cout << "NO\n";
        return ;
    }
    for (int i = 1; i + 1 < s.size(); i++) {
        if (s[i - 1] == 'W' && s[i] != 'W' && s[i + 1] == 'W') {
            std::cout << "NO\n";
            return ;
        }
    }
    std::cout << "YES\n";
}

E. 2-Letter Strings

思路：

由于字符数较少 \(a \sim k\) ，所以我们可以暴力枚举所有出现可能的字符串中，只有一个数相同的字符串个数且在序列中出现过

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;

    i64 ans = 0;
    std::vector cnt(12, std::vector<int>(12));
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < 2; j++) {
            for (char c = 'a'; c <= 'k'; c++) {
                if (c == s[j]) continue ;
                std::string t = s;
                t[j] = c;
                ans += cnt[t[0] - 'a'][t[1] - 'a'];
            }
        }
        cnt[s[0] - 'a'][s[1] - 'a']++;
    }
    std::cout << ans << "\n";
}

F. Eating Candies

思路：

用前缀和数组和二分维护头尾数量和小于n的最大相等值，或者用双指针维护也可以

时间复杂度：\(O(nlogn)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> s1(n + 1), s2(n + 1);
    for (int i = 1; i <= n; i++) {
        s1[i] = s1[i - 1] + a[i];
    }
    for (int i = n; i >= 1; i--) {
        s2[n - i + 1] = s2[n - i] + a[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int t = std::lower_bound(s1.begin(), s1.end(), s2[i]) - s1.begin();
        if (t + i > n) break;
        else {
            if (s1[t] == s2[i]) {
                ans = std::max(t + i, ans);
            }
        }
    }
    std::cout << ans << "\n";
}

G. Fall Down

思路：

记录每一个o，上面有多少个*即可，将整个图案向下扩展一层o，然后模拟即可

时间复杂度：\(O(n \times m)\)

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector g(n + 1, std::vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> g[i][j];
        }
    }
    for (int i = 0; i < m; i++) {
        g[n][i] = 'o';
    }

    std::vector<std::vector<int>> stone(m + 1);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'o') {
                stone[j].push_back(i);
            }
        }
    }

    std::vector w(n + 1, std::vector<int>(m));
    for (int i = 0; i < m; i++) {
        if (stone[i].size() > 0) {
            for (auto x : stone[i]) {
                for (int j = x - 1; j >= 0; j--) {
                    if (g[j][i] == '*') {
                        w[x][i]++;
                    } else if (g[j][i] == 'o') {
                        break;
                    }
                }
            }
        }
    }

    std::vector ans(n + 1, std::vector<char>(m, '.'));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'o') {
                ans[i][j] = 'o';
            }
            if (w[i][j] != 0) {
                int t = w[i][j], p = i - 1;
                while (t--) {
                    ans[p][j] = '*';
                    p--;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cout << ans[i][j];
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

H. Maximal AND

思路：

或 \((OR)\) ：\(0 \odot 1 = 1 \space\space\space\space\space\space\space 1 \odot 1 = 1\)
与 \((AND)\) ：\(0 \otimes 1 = 0 \space\space\space\space\space\space\space 1 \otimes 1 = 1\)
异或 \((XOR)\) ：\(0 \oplus 1 = 0 \space\space\space\space\space\space\space 0 \oplus 0 = 1 \space\space\space\space\space\space\space 1 \oplus 1 = 1\)
枚举所有数位中 \(1\) 的数量，然后贪心的补充最大数位即可，每满足一个数位等于 \(n\)，就将这个数位设为 \(1\)，然后输出答案即可

时间复杂度：\(O(n)\)

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n), bit(31);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];

        for (int j = 0; j < 31; j++) {
            if ((a[i] >> j) & 1) {
                bit[j]++;
            }
        }
    }

    int ans = 0;
    for (int i = 30; i >= 0; i--) {
        int t = bit[i];
        if (k >= n - t) {
            k -= n - t;
            ans |= 1 << i;
        } 
    }
    std::cout << ans << "\n";
}