Codeforces Round 898 (Div. 4)

Shiroha白羽的博客

Shiroha · 2023-09-24 · via Shiroha白羽的博客

A. Short Sort

大致题意

有三张卡片，分别为 $a, b, c$，已经在桌面上乱序排好，最多交换两张卡片的位置，问是否能够变成有序的 $a, b, c$

思路

简单题，判断一下是不是至少有一位是保持 $a, b, c$ 的顺序即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        string  str;
        str.reserve(3);
        cin >> str;
        int cnt = 0;
        for (int i = 0; i < 3; ++i) cnt += str[i] == i + 'a';
        cout << (cnt == 1 || cnt == 3 ? "YES" : "NO") << endl;
    }
}

B. Good Kid

大致题意

有一个数组，允许你给其中一个值加一，问最终所有值的乘积最大是多少

思路

简单题，如果有两个及以上的 $0$，那么最终结果一定还是 $0$。如果只有一个 $0$，那就等于忽略这个 $0$ 即可，剩下的情况，因为加了之后的效果是 $\frac{x+1}{x}$，所以 $x$ 越小越好，那么让最小的值 $+1$ 即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        int p = 1, zero = 0, mi = INT_MAX;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            p *= (tmp == 0 ? 1 : tmp);
            zero += tmp == 0;
            mi = min(mi, tmp);
        }        if (zero >= 2) cout << 0 << endl;
        else if (zero == 1) cout << p << endl;
        else cout << (p / mi * (mi + 1)) << endl;
    }
}

C. Target Practice

大致题意

有一个飞镖靶，根据结果计算总分

思路

简单题，根据当前的下标距离四个边最小值是多少即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        string str;
        str.reserve(10);
        int ans = 0;
        for (int i = 0; i < 10; ++i) {
            cin >> str;
            for (int j = 0; j < 10; ++j) {
                if (str[j] == '.') continue;
                int code = min(min(i + 1, 10 - i), min(j + 1, 10 - j));
                ans += code;
            }
        }
        cout << ans << endl;
    }
}

D. 1D Eraser

大致题意

有一个串，其中有白色和黑色方块，每次可以选择连续 $k$ 个块让其变成白色，问最少几步可以全部变成白色

思路

简单题，从左往右考虑即可，毕竟最左边遇到的第一个黑色方块肯定需要消耗一次操作，为了最大化使用必定会让 $k$ 个的左边界是当前的黑色方块

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k;
        cin >> n >> k;
        string str;
        str.reserve(n);
        cin >> str;
        int last = -k - 1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (str[i] == 'W') continue;
            if (i - last + 1 <= k) continue;
            last = i;
            ans++;
        }
        cout << ans << endl;
    }
}

E. Building an Aquarium

大致题意

有一个线性水池，水池底部形状已知，最多可以使用 $x$ 个单位的水，问水池两边应该造多高才能尽可能容纳更多的水的同时，在水池满的时候不会使用超过给出的水

思路

简单题，二分答案即可

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, x;
        cin >> n >> x;
        vector<int> data(n);
        for (auto &item: data) cin >> item;
        int l = 0, r = 2e9 + 10LL;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            int sum = 0;
            for (auto &item: data) sum += item >= mid ? 0 : mid - item;
            if (sum > x) r = mid;
            else l = mid;
        }
        cout << l << endl;
    }
}

F. Money Trees

大致题意

给出一个数组，其每个值都有两个属性：$a, h$，需要找到一个连续的子数组，使得这个连续的子数组 $[l, r]$的 $h$ 值满足 $\forall i \in [l, r], h_{i-1} \space mod \space h_i = 0$，同时 $\sum_{i=l}^{r} a_i \leq x$

问最长的子数组的长度

思路

也是二分答案即可，毕竟在确定要找的最终串的长度的情况下，只需要 $O(n)$ 即可求出是否符合预期，注意平移区间的时候状态的转化

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k, ans = 0;
        cin >> n >> k;
        vector<int> a(n), h(n);
        for (auto &item: a) cin >> item;
        for (auto &item: h) cin >> item;
        for (auto &item: a) if (item <= k) ans = 1;
        int l = 0, r = n + 1;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (mid == 1) {
                if (ans >= 1) l = mid;
                else r = mid;
                continue;
            }
            int x = 0, y = 0, sum = 0;
            bool flag = false;            auto findNext = [&]() {
                x = y;
                y += 1;
                sum = a[x];
                while (y - x != mid && x < n && y < n) {
                    if (h[y - 1] % h[y] != 0) {
                        x = y;
                        y += 1;
                        sum = a[x];
                    } else {
                        sum += a[y];
                        y++;
                    }
                }
                if (y - x == mid && sum <= k) {
                    ans = max(ans, mid);
                    flag = true;
                }
                return y - x == mid;
            };
            auto move = [&]() {
                if (y == n) return false;
                if (h[y - 1] % h[y] != 0) return false;
                sum -= a[x];
                sum += a[y];
                y++;
                x++;
                if (sum <= k) {
                    ans = max(ans, mid);
                    flag = true;
                }
                return true;
            };
            while (findNext()) while (move());
            if (flag) l = mid;
            else r = mid;
        }
        cout << ans << endl;
    }
}

G. ABBC or BACB

大致题意

有一个字符串，由 $A, B$ 两个字母组成，每次可以将 $AB$ 转为 $BC$，或者将 $BA$ 转为 $CB$，问最多可以操作几次

思路

很显然，如果是一串联系的 $A$，然后其中一侧有一个 $B$，那么这种情况下的答案就是 $A$ 的数量

那么将整个数组拆成所有连续的 $A$ 段，然后为每个 $A$ 段找合理的 $B$ 即可。比如如果整个字符串开头或者结尾是 $B$，那么必然可以为每个 $A$ 段找到一个 $B$。除开上面的情况，只需要看看 $B 的数量是否大于等于 $A$ 段的数量即可，因为如果等于或者超过也必然可以分割。如果还不行，那么只能舍弃价值最低的 $A$ 串了

AC code

void solve() {
    int _;
    cin >> _;
    string str;
    str.reserve(2e5 + 10);
    for (int ts = 0; ts < _; ++ts) {
        cin >> str;
        if (str.front() == 'B' || str.back() == 'B') {
            int cnt = 0;
            for (auto &item: str) cnt += item == 'A';
            cout << cnt << endl;
            continue;
        }        vector<int> part(1, 0);
        int cntB = 0;
        for (char &i: str) {
            cntB += i == 'B';
            if (i == 'B') {
                if (part.back() != 0) part.push_back(0);
            } else part.back()++;
        }
        int tot = 0, mi = INT_MAX;
        for (auto &item: part) {
            tot += item;
            mi = min(mi, item);
        }
        if (cntB < part.size()) tot -= mi;
        cout << tot << endl;
    }
}

H. Mad City

大致题意

有一个图，$n$ 个点，$n$ 条边，有两个人分别从 $a, b$ 出发，其中前者希望追赶后者，而后者希望摆脱前者的追捕，问能否追上

思路

首先，$n$ 个点和 $n$ 条边，那就意味着必然图中必然存在环。而两人速度相同，如果同时都在环上，那肯定追不到。所以必须要在后者进入环之前抓到，也就是提前或者刚好到达环上的某一个点。所以只需要找出后者刚进入环的时间点和位置，看看前者能否在指定时间内达到即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, a, b;
        cin >> n >> a >> b;
        vector<int> deg(n + 1, 0);
        vector<bool> vis(n + 1, false);
        struct node {
            int v, n;
        };
        vector<node> edge(n * 2);
        vector<int> head(n + 1, -1);
        for (int i = 0; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            edge[i << 1] = {v, head[u]};
            edge[(i << 1) | 1] = {u, head[v]};
            head[u] = i << 1;
            head[v] = (i << 1) | 1;
            deg[u]++;
            deg[v]++;
        }        // find circle
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (deg[i] == 1) q.push(i);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            vis[cur] = true;
            for (int i = head[cur]; i != -1; i = edge[i].n)
                if ((--deg[edge[i].v]) == 1 && !vis[edge[i].v]) q.push(edge[i].v);
        }
        // begin for b run away
        int cost1, cost2 = INT_MAX, target;
        queue<pair<int, int>> qs;
        vector<bool> flag(n + 1, false);
        qs.emplace(b, 0);
        flag[b] = true;
        while (!qs.empty()) {
            auto cur = qs.front();
            qs.pop();
            if (!vis[cur.first]) {
                cost1 = cur.second;
                target = cur.first;
                break;
            }
            for (int i = head[cur.first]; i != -1; i = edge[i].n)
                if (!flag[edge[i].v]) {
                    qs.emplace(edge[i].v, cur.second + 1);
                    flag[edge[i].v] = true;
                }
        }
        while (!qs.empty()) qs.pop();
        for (int i = 0; i <= n; ++i) flag[i] = false;
        qs.emplace(a, 0);
        flag[a] = true;
        while (!qs.empty()) {
            auto cur = qs.front();
            qs.pop();
            if (cur.first == target) {
                cost2 = cur.second;
                break;
            }
            for (int i = head[cur.first]; i != -1; i = edge[i].n)
                if (!flag[edge[i].v]) {
                    qs.emplace(edge[i].v, cur.second + 1);
                    flag[edge[i].v] = true;
                }
        }
        cout << (cost1 < cost2 ? "YES" : "NO") << endl;
    }
}

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

推荐订阅源

Shiroha白羽的博客

A. Short Sort

大致题意

思路

AC code

B. Good Kid

大致题意

思路

AC code

C. Target Practice

大致题意

思路

AC code

D. 1D Eraser

大致题意

思路

AC code

E. Building an Aquarium

大致题意

思路

AC code

F. Money Trees

大致题意

思路

AC code

G. ABBC or BACB

大致题意

思路

AC code

H. Mad City

大致题意

思路

AC code