Codeforces Round 799 (Div. 4)

发表于 2024-03-25 更新于 2024-05-07 分类于题解阅读次数：本文字数： 1.5k 阅读时长 ≈ 5 分钟

In the middle of every difficulty lies opportunity.

A. Marathon

思路：

模拟即可

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

void solve() {
       int a[4];
       for (int i = 0; i < 4; i++) {
           std::cin >> a[i];
       }
       int x = a[0];
       std::sort(a, a + 4);
       for (int i = 0; i < 4; i++) {
           if (a[i] == x) {
               std::cout << 4 - i - 1 << "\n";
               return ;
           }
       }
}

B. All Distinct

思路：

要保证最后的序列个数都是唯一的，所以我们可以一开始把所有数量多于 2 的数字都删的只剩 2，然后根据最后个数为 2 的个数的奇偶性判断即可

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

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

    std::vector<int> a(n);
    std::map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        cnt[a[i]]++;
    }
    for (auto &[x, y] : cnt) {
        if (y > 2) {
            y %= 2;
            if (y == 0) {
                y = 2;
            }
        }
    }
    int ct = 0;
    for (auto [x, y] : cnt) {
        if (y > 1) ct++;
    }
    int ans = cnt.size() + (ct & 1 ? -1 : 0);
    std::cout << ans << "\n";
}

C. Where's the Bishop?

思路：

直接找 g[i + 1][j + 1] 和 g[i + 1][j - 1] 和 g[i - 1][j + 1] 是否为 # 即可

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

void solve() {
    std::vector<std::string> g(9);
    for (int i = 1; i <= 8; i++) {
        std::cin >> g[i];
        g[i] = '&' + g[i];
    }

    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
            if (g[i + 1][j + 1] == g[i - 1][j + 1] && g[i + 1][j + 1] == '#' &&
                g[i + 1][j + 1] == g[i + 1][j - 1] && g[i + 1][j + 1] == '#') {
                std::cout << i << " " << j << "\n";
                return ;
            }
        }
    }
}

D. The Clock

思路：

按照规则模拟即可

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

void solve() {
    int h, m, d;
    scanf("%d:%d %d", &h, &m, &d);

    int ans = 0, f = 0;
    int h1 = h * 60 + m;
    std::set<std::string> vis;
    for (int i = h1; ; i += d) {
        int a = i / 60, b = i % 60;
        a %= 24;
        if (a == h && b == m && f) break;
        std::string sa = std::to_string(a);
        std::string sb = std::to_string(b);
        f = 1;
        if (sa.size() != 2) {
            sa = '0' + sa;
        }
        if (sb.size() != 2) {
            sb = '0' + sb;
        }
        std::string tmp = sa + std::string(sb.begin(), sb.end());
        if (tmp == std::string(tmp.rbegin(), tmp.rend())) {
            if (vis.count(tmp)) continue ;
            vis.insert(tmp);
            ans++;
        }
    }
    std::cout << ans << "\n";
}

E. Binary Deque

思路：

因为每次是删除头部和尾部，所以我们用一个前缀和维护区间 1 的个数，然后二分右端点，然后进行取 min进行找最小值即可

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

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

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

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

    if (s[n] < S) {
        std::cout << "-1\n";
        return ;
    }
    int ans = 2E9;
    for (int i = 1; i <= n; i++) {
        int l = 1, r = n;
        while (l <= r) {
            int mid = l + r >> 1;
            auto check = [&](int x) {
                int v = s[x] - s[i - 1];
                return v > S;
            };
            if (check(mid)) {
                r = mid - 1;
            } else {
                l = mid + 1;    
            }
        }
        ans = std::min(ans, i + n - l);
    }
    std::cout << ans << '\n';
}

F. 3SUM

思路：

由于需要保证三个数的和的最后一位是 3，可以发现，这个只和每个数的个位有关，所以，我们只需要把每一个数按照个位数字存在一起，然后枚举最后一位数字是多少即可，这样时间复杂度为 \(O(n + 9^3)\)

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

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

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

    std::map<int, std::vector<int>> mp;
    for (int i = 0; i < n; i++) {
        mp[a[i] % 10].push_back(a[i]);
    }

    for (int i = 0; i < 10; i++) {
        if ((i * 3) % 10 == 3) {
            if (mp[i].size() >= 3) {
                std::cout << "YES\n";
                return ;
            }
        }
        for (int j = 0; j < 10; j++) {
            if (i == j) continue ;
            if ((i + j * 2) % 10 == 3) {
                if (mp[i].size() >= 1 && mp[j].size() >= 2) {
                    std::cout << "YES\n";
                    return ;
                }
            }
            for (int k = 0; k < 10; k++) {
                if (k == i || k == j) continue ;
                if ((i + j + k) % 10 == 3) {
                    if (mp[i].size() >= 1 && mp[j].size() >= 1 && mp[k].size() >= 1) {
                        std::cout << "YES\n";
                        return ;
                    }
                }
            }
        }
    }
    std::cout << "NO\n";
}

G. 2^Sort

思路：

要使整个序列是严格递增，因为一个区间是按位每次多乘以 2，所以它满足单调性，我们可以进行双指针扫描
只要在这个区间里，\(a_{pre} < a_{i} \times 2\)，就继续扫描

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

void solve() {
    int n, k;
    std::cin >> n >> k;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    int cur = 0, ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] < 2 * a[i + 1]) {
            cur++;
            ans += (cur >= k);
        } else {
            cur = 0;
        }
    }
    std::cout << ans << "\n";
}

H. Gambling

思路：

因为题目要表明，当我们猜中一次，就可以使得本金 \(\times 2\)，所以，我们要求的就是一个众数减去非众数值最大的区间
我们要求一个区间内的众数的数量减去非众数的数量最大

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

解法一：map 维护每个元素的下标

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

    std::map<int, std::vector<int>> mp;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        mp[x].push_back(i + 1);
    }

    int mx = 0, ans, l, r;
    for (auto [x, a] : mp) {
        int t = -2E9, pos = -1;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] - 2 * i > t) {
                t = a[i] - 2 * i;
                pos = a[i];
            }
            int now = 2 * i - a[i] + t + 1;
            if (now > mx) {
                mx = now, ans = x, l = pos, r = a[i];
            }
        }
    }
    std::cout << ans << " " << l << " " << r << "\n";
}

解法二：线段树 进行动态区间修改

constexpr int N = 2E5 + 10;
struct node {
    int val, sum; // val 区间和  sum 最大子段和
    int l, r; // l 包含左端点的最大字段和  r 包含右端点的最大子段和
}tr[N << 2];

void pushup(node &u, node &lson, node &rson) {
    u.val = lson.val + rson.val;
    u.sum = std::max(lson.r + rson.l, std::max(lson.sum, rson.sum));
    u.l = std::max(lson.l, lson.val + rson.l);
    u.r = std::max(rson.r, rson.val + lson.r);
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {-1, -1, -1, -1};
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void modify(int u, int l, int r, int x, int v) {
    if (l == r) {
        tr[u] = {v, v, v, v};
        return ;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
        modify(u << 1, l, mid, x, v);
    } else {
        modify(u << 1 | 1, mid + 1, r, x, v);
    }
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

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

    build(1, 1, n);
    std::vector<int> a(n + 1);
    std::map<int, std::vector<int>> mp;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        mp[x].push_back(i + 1);
        a[i + 1] = -1;
    }

    int mx = 0, ans;
    for (auto [x, a] : mp) {
        for (int i : a) {
            modify(1, 1, n, i, 1);
        }
        if (tr[1].sum > mx) {
            mx = tr[1].sum;
            ans = x;
        }
        for (int i : a) {
            modify(1, 1, n, i, -1);
        }
    }

    int l = 1, r;
    for (int x : mp[ans]) {
        a[x] = 1;
    }
    int s = 0;
    for (int i = 1; i <= n; i++) {
        if (s < 0) {
            s = 0;
            l = i;
        }
        s += a[i];
        if (s == mx) {
            r = i;
            break;
        }
    }
    std::cout << ans << " " << l << " " << r << "\n";
}