Codeforces Round 894 (Div. 3)

A - Gift Carpet (CF1862 A)

题目大意

看是不是能拿出四列，按顺序出现"vika"四个字母。

解题思路

不解释

神奇的代码

#include <bits/stdc++.h>

using  i64 = long long;

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

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

    std::string res = "#vika";
    int pos = 1;

    for (int j = 1;j <= m;j ++) {
        for (int i = 1;i <= n;i ++) {
            if (a[i][j] == res[pos]) {
                pos ++;
                break;
            }
        }
    }

    if (pos == 5) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

B - Sequence Game (CF1862 B)

题目大意

解题思路

如果一段区间是递增的，就已经符合题意，不用动。 如果不是递增的，在前面复制一份就形成递增了。

神奇的代码

#include <bits/stdc++.h>

using  i64 = long long;

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

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

    std::vector<int> b;
    b.emplace_back(a.front());

    for (int i = 1;i < n;i ++) {
        if (a[i - 1] > a[i]) b.emplace_back(a[i]);        
        b.emplace_back(a[i]);
    }

    std::cout << b.size() << std::endl;

    for (int &item : b) {
        std::cout << item << ' ';
    }

    std::cout << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

C - Flower City Fence (CF1862 C)

题目大意

<++>

解题思路

树状数组维护一下每一列的方块数，然后和原数组比较就行。

神奇的代码

#include <bits/stdc++.h>
#include <cstddef>

using  i64 = long long;

template<typename T>
struct FenwickTree{
    int n;
    std::vector<T> bit;

    // constructors
    FenwickTree(int _n) : n(_n), bit(_n + 1) {}
    FenwickTree(std::vector<T> &a) : FenwickTree(a.size()){
        for(size_t i = 1;i <= a.size();i ++)
            update(i, a[i]);
    }

    // Operations
    T query(int idx){
        T res = 0;
        for(int i = idx;i != 0; i -= i & -i)
            res += bit[i];
        return res;
    }

    void update(int idx, int delta){
        for(int i = idx;i <= n;i += i & -i)
            bit[i] += delta;
    }

    T range_quary(int l, int r){
        return query(r) - query(l - 1);
    }

    void range_update(int l, int r, int delta){
        update(l, delta);
        update(r + 1, -delta);
    }
};

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

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

    if (a[1] > n) {
        std::cout << "NO" << '\n';
        return ;
    }

    FenwickTree<i64> bit(n);
    for (int i = 1;i <= n;i ++) {
        bit.range_update(1, a[i], 1);
    }

    for (int i = 1;i <= n;i ++) {
        i64 res = bit.query(i);
        if (res != a[i]) {
            std::cout << "NO" << '\n';
            return ;
        }
    }

    std::cout << "YES" << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

D - Ice Cream Balls (CF1862 D)

题目大意

<++>

解题思路

首先要最少，肯定所有数字不一样的时候最少。可以先二分来找到刚好\(C_i^2\)小于n的\(i\)。 然后考虑要添加到恰好n份，只需要添加$ n - C_i^i $个相同的数字即可。

神奇的代码

#include <bits/stdc++.h>

using  i64 = long long;

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

    auto check = [&](i64 x) {
        i64 res = x * (x - 1) / 2;
        return res >= n;
    };

    i64 l = 2, r = 2648956421;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    i64 res = l * (l - 1) / 2;
    if (res == n) {
        std::cout << l << '\n';
        return ;
    }

    if (res > n) {
        res = (l - 1) * (l - 2) / 2;
        std::cout << n - res + l - 1 << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

E - Kolya and Movie Theatre (CF1862 E)

题目大意

<++>

解题思路

注意到最后一场电影在第\(i\)天看，则少的舒适度一定为\(d * i\)。所以只需要求出前\(m\)大的数的和即可。 枚举\(i\), 维护以下\(1~i\)中的前\(m\)大数的和，最后求出最大值即可。

神奇的代码

#include <bits/stdc++.h>
#include <set>

using  i64 = long long;

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

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

    i64 ans = 0, sum = 0;
    std::multiset<int> st;
    for (int i = 1;i <= n;i ++) {
        if (a[i] <= 0) continue;
        st.insert(a[i]);
        sum += a[i];
        if (st.size() > m) {
            sum -= *st.begin();
            st.erase(st.begin());
        }
        ans = std::max(ans, sum - 1LL * i * d);
    }

    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

F - Magic Will Save the World (CF1862 F)

题目大意

<++>

解题思路

假设所有怪兽的总血量为\(s\)，其中有\(x\)滴血被水解决，剩下\(s - x\)血量用火解决。则答案为\(max(\frac{x}{w}, \frac{s - x}{f})\)。 用\(0/1\)背包预处理才出所有能取到的怪兽血量的集合，然后枚举更新答案即可。

神奇的代码

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int w, f, n;
        cin >> w >> f >> n;
        vector<int> s(n);
        int sum_s = 0;
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
            sum_s += s[i];
        }
        vector<bool> dp(sum_s + 1);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int w = sum_s; w - s[i] >= 0; --w) {
                dp[w] = dp[w] || dp[w - s[i]];
            }
        }
        int ans = 2e9;
        for (int i = 0; i <= sum_s; ++i) {
            if (dp[i]) {
                ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

---

G - The Great Equalizer (CF1862 G)

题目大意

<++>

解题思路

设\(d\)数组为原数组数组排序后的差， 猜的结论：\(ans = max(a) + max(d)\)

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::multiset<int> s, d{0};
    
    auto add = [&](int x) {
        auto it = s.insert(x);
        auto r = std::next(it);
        if (it != s.begin()) {
            d.insert(x - *std::prev(it));
        }
        if (r != s.end()) {
            d.insert(*r - x);
        }
        if (it != s.begin() && r != s.end()) {
            d.extract(*r - *std::prev(it));
        }
    };
    
    auto del = [&](int x) {
        auto it = s.find(x);
        auto r = std::next(it);
        if (it != s.begin()) {
            d.extract(x - *std::prev(it));
        }
        if (r != s.end()) {
            d.extract(*r - x);
        }
        if (it != s.begin() && r != s.end()) {
            d.insert(*r - *std::prev(it));
        }
        s.erase(it);
    };
    
    for (int i = 0; i < n; i++) {
        add(a[i]);
    }
    
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y;
        std::cin >> x >> y;
        x--;
        del(a[x]);
        a[x] = y;
        add(a[x]);
        int ans = *s.rbegin() + *d.rbegin();
        std::cout << ans << " \n"[i == q - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

---