Codeforces Round 914 (Div. 2)

Shiroha白羽的博客

Shiroha · 2024-02-15 · via Shiroha白羽的博客

A. Forked!

大致题意

棋盘上有一个皇后和一个国王，且骑士的移动方式是给出的 “日” 字形式，存在几个位置，使得骑士可以同时吃国王和皇后

思路

虽然不是 “日” 字，但是一个骑士最多也就只能走 8 个位置，所以暴力枚举就行

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int a, b, xk, yk, xq, yq;
        cin >> a >> b >> xk >> yk >> xq >> yq;
        const int arr[4][2] = {1, 1, 1, -1, -1, 1, -1, -1};
        set<pair<int, int>> s;
        for (const auto ar: arr) {
            s.insert({xk + a * ar[0], yk + b * ar[1]});
            s.insert({xk + b * ar[0], yk + a * ar[1]});
        }        int ans = 0;
        for (const auto ar: arr) {
            if (s.count({xq + a * ar[0], yq + b * ar[1]})) {
                s.erase({xq + a * ar[0], yq + b * ar[1]});
                ++ans;
            }
            if (s.count({xq + b * ar[0], yq + a * ar[1]})) {
                s.erase({xq + b * ar[0], yq + a * ar[1]});
                ++ans;
            }
        }
        cout << ans << endl;
    }
}

B. Collecting Game

大致题意

有一个数组，选择其中的一个值作为初始值，然后每次进行如下操作：

选择一个剩下的值，满足其小于当前的值
删除它，并把其值加到当前值上

问每一位的值作为初始值的情况下，最多可以干掉多少值

思路

因为每一个值都可以干掉它以及比它小的值，所以只需要这些值加起来比恰好大于它的值还要大的话，那么就可以继续增大

而最终的结果一定是卡在某个值处，使得所有逼比它小的值加起来都没有它大，那么这个时候，比它小的那个值必然只能消除到这个位置

依次类推，只需要依次找到满足 $\sum_{i=1}^x a_i < a_{x+1}$ 即可，那么必然可以类似前缀和一样处理就行

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<pair<int, int>> data(n);
        for (auto& [fst, snd]: data) cin >> fst;
        for (int i = 0; i < n; ++i) data[i].second = i;
        sort(data.begin(), data.end());
        vector<int> ans(n);
        int l = 0, sum = 0;
        while (l < n) {
            int r = l + 1;
            sum += data[l].first;
            while (r < n && sum >= data[r].first) {
                sum += data[r].first;
                ++r;
            }
            for (int i = l; i < r; ++i) ans[data[i].second] = r - 1;
            l = r;
        }
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
    }
}

C. Array Game

大致题意

有一个数组，允许你每次选择其中的两个值，把它们的差值加入到队列中，问经过 $k$ 次操作后，数组中最小的值最小可能是多少

思路

如果操作三次，那么可以连续两次拿同两个值，然后再让结果的那两值的差值加入数组，那么必然得到 $0$，即最小的值

所以问题只需要考虑一次操作和两次操作即可

一次操作很简单，$n^2$ 暴力扫就行了

二次操作也很简单，$n^2$ 暴力扫的同时，将结果和原始数组中看看，是否有足够相近的值

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        set<int> s;
        vector<int> data(n);
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            data[i] = tmp;
            s.insert(tmp);
        }
        if (k >= 3) {
            cout << 0 << endl;
            continue;
        }
        if (k == 0) {
            cout << *s.begin() << endl;
            continue;
        }
        int ans1 = *s.begin(), ans2 = *s.begin();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int tmp = abs(data[i] - data[j]);
                auto riter = s.upper_bound(tmp);
                auto liter = riter;
                if (liter != s.begin()) --liter;
                if (riter == s.end()) --riter;
                ans1 = min(ans1, tmp);
                ans2 = min(min(ans2, tmp), min(abs(*riter - tmp), abs(*liter - tmp)));
            }
        }
        if (k == 1) cout << ans1 << endl;
        else cout << ans2 << endl;
    }
}

D2. Set To Max (Hard Version)

大致题意

有一个数组，允许每次操作选择一个区间 $[l, r]$，使得 $a_i \leftarrow max(a_{l \dots r}), \forall i \in [l, r]$

问只操作数组 $a$ 的情况下是否有可能做到

思路

首先，数组 $a$ 里面的每一个值，必然有其最大的作用范围，毕竟是取区间最大，可以通过两次单调栈的方式来找到每个值可以作用到的最大区间

然后只需要找到每一个值所来自哪个值的效果即可，可以用双指针在两个数组上移动即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> a(n), b(n), la(n, 0), ra(n, n);
        int r = n - 1;
        for (auto& i: a) cin >> i;
        for (auto& i: b) cin >> i;
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && a[st.top()] < a[i]) {
                ra[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) st.pop();        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && a[st.top()] < a[i]) {
                la[st.top()] = i + 1;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) st.pop();
        bool flag = true;
        for (int i = n - 1; i >= 0; --i) {
            while (r >= 0 && (a[r] != b[i] || la[r] > i || ra[r] <= i)) --r;
            if (a[r] != b[i] || la[r] > i || ra[r] <= i) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

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

推荐订阅源

Shiroha白羽的博客

A. Forked!

大致题意

思路

AC code

B. Collecting Game

大致题意

思路

AC code

C. Array Game

大致题意

思路

AC code

D2. Set To Max (Hard Version)

大致题意

思路

AC code