Codeforces Round 914 (Div. 2)

A - Forked!

解题思路:

枚举皇后和国王能被骑士吃到的位置，重合的点数就是答案。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;

void solve()
{
    ll a, b, x1, x2, y1, y2;
    cin >> a >> b >> x1 >> y1 >> x2 >> y2;
    map<pii, bool> q;
    vector<ll> dx, dy;
    ll ans = 0;
    if (a != b)
    {
        dx.push_back(-a);
        dx.push_back(a);
        dx.push_back(b);
        dx.push_back(-b);
        dy.push_back(-a);
        dy.push_back(a);
        dy.push_back(b);
        dy.push_back(-b);
        for (int i = 0; i < 4; i++)
        {
            if (abs(dx[i]) == a)
            {
                for (int j = 2; j < 4; j++)
                {
                    q[{x1 + dx[i], y1 + dy[j]}] = true;
                }
            }
            else
            {
                for (int j = 0; j < 2; j++)
                {
                    q[{x1 + dx[i], y1 + dy[j]}] = true;
                }
            }
        }

        for (int i = 0; i < 4; i++)
        {
            if (abs(dx[i]) == a)
            {
                for (int j = 2; j < 4; j++)
                {
                    if (q[{x2 + dx[i], y2 + dy[j]}])
                    {
                        ans++;
                    }
                }
            }
            else
            {
                for (int j = 0; j < 2; j++)
                {
                    if (q[{x2 + dx[i], y2 + dy[j]}])
                    {
                        ans++;
                    }
                }
            }
        }
    }
    else
    {
        dx.push_back(a);
        dx.push_back(-a);
        dy.push_back(a);
        dy.push_back(-a);
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                q[{x1 + dx[i], y1 + dy[j]}] = true;
            }
        }
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                if (q[{x2 + dx[i], y2 + dy[j]}])
                {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

B - Collecting Game

解题思路：

排序。排完序数组\(a\)，前缀和数组为\(s\).

对于\(a[i]\)，起码能删除\(i - 1\)个，也就是前\(i - 1\)个，后面一直往后走，直到\(a[j] > s[j- 1]\)，我们能删的就是\(j - 2\)个。

所以，可以从后往前遍历。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;

void solve()
{
    ll n;
    cin >> n;
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a.begin() + 1, a.end());
    vector<int> ans(n + 1);
    vector<ll> s(n + 1);
    vector<ll> v;
    for (int i = 1; i <= n; i++)
    {
        s[i] = a[i].fi + s[i - 1];
    }
    ans[a[n].se] = n - 1;
    for (int i = n - 1; i; i--)
    {
        if (s[i] < a[i + 1].fi)
        {
            ans[a[i].se] = i - 1;
        }
        else
        {
            ans[a[i].se] = ans[a[i + 1].se];
        }
    }
    // cout << endl;
    // for (int i = 1; i <= n; i++)
    // {
    //     auto idx = lower_bound(v.begin(), v.end(), i) - v.begin();
    //     cout << idx << ' ' << a[i].fi << ' ' << v[idx] << endl;
    //     if (i != v[idx])
    //     {
    //         ans[a[i].se] = v[idx] - 2;
    //     }
    //     else
    //     {
    //         ans[a[i].se] = v[idx] - 1;
    //     }
    // }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

C - Array Game

解题思路:

注意数据范围。\(O(n^2log(n^2))\)能过。

• \(k \geq 3\)：答案为0.\(c = a - b,a - c = b, b - b = 0\)。
• \(k = 1\)：我们从原数组和最小差中找答案。
• \(k = 2\)：计算所有元素两两相减的差值，对于每一个元素二分查找最大的比他小的数和最小的比他大的数，分别相减取最小值即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    ll mina = 1e18 + 10;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        mina = min(a[i], mina);
    }
    if (k >= 3)
    {
        puts("0");
        return;
    }
    if (k == 1)
    {
        sort(a.begin() + 1, a.end());
        for (int i = 1; i < n; i++)
        {
            mina = min(mina, a[i + 1] - a[i]);
        }
        cout << mina << endl;
    }
    else
    {
        sort(a.begin() + 1, a.end());
        for (int i = 1; i < n; i++)
        {
            mina = min(mina, a[i + 1] - a[i]);
        }
        // unordered_map<ll, bool> q;
        // for (int i = n; i; i--)
        // {
        //     for (int j = n; j > i; j--)
        //     {
        //         if (q[a[j] - a[i]] == true || q[2 * a[i]] == true)
        //         {
        //             puts("0");
        //             return;
        //         }
        //     }
        //     q[a[i]] = true;
        // }
        vector<ll> v;
        set<ll> s;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                s.insert(abs(a[i] - a[j]));
            }
        }
        // cout << mina << endl;
        for (int i = 1; i <= n; i++)
        {
            auto it = s.lower_bound(a[i]);
            if (it != s.end())
            {

                auto r = *it;
                // cout << "r:" << r << endl;
                mina = min(abs(r - a[i]), mina);
            }
            if (it != s.begin())
            {
                it--;
                auto l = *(it);
                // cout << "l:" << l << endl;
                mina = min(abs(l - a[i]), mina);
            }
        }
        cout << mina << endl;
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

D1 - Set To Max (Easy Version)

解题思路:

\(n\)很小，直接暴力。

对于每个\(b[i]\)，我们往两边扩，如果找到\(a[j] == b[i]\)就说明有解。找的过程中如果有\(a[j] > b[i]\)或者\(b[j] < b[i]\)就停止扩展。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;

void solve()
{
    ll n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), l(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    vector<bool> st(n + 1, false);
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == b[i])
        {
            st[i] = true;
        }
        for (int j = i - 1; j; j--)
        {
            if (a[i] == b[j] && a[j] < b[j])
            {
                st[j] = true;
            }
            else if (b[j] < a[i] || a[j] > a[i])
            {
                break;
            }
        }
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] == b[j] && a[j] <= b[j])
            {
                st[j] = true;
            }
            else if (b[j] < a[i] || a[j] > a[i])
            {
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

D2 - Set To Max (Hard Version)

解题思路:

优化上述思路：

分别找到左右第一个\(a[j] = b[i]\),我们查询区间最大\(a[j]\)和最小\(b[j]\)。若出现\(max(a[j]) == b[i]\)并且\(min(b[j]) >= b[i]\)则有解。

静态区间最值查询可用\(st\)表。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;

void solve()
{
    ll n;

    cin >> n;
    vector<int> a(n + 1), b(n + 1), l(n + 1, 1), r(n + 1, n);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    vector<vector<int>> f(n + 1, vector<int>(22)), g(n + 1, vector<int>(22));
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = a[i];
        g[i][0] = b[i];
    }
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto qa = [&](int l, int r)
    {
        int len = r - l + 1;
        int k = log(len) / log(2);
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    };
    auto qb = [&](int l, int r)
    {
        int len = r - l + 1;
        int k = log(len) / log(2);
        return min(g[l][k], g[r - (1 << k) + 1][k]);
    };
    set<int> sa[n + 1], sb[n + 1];
    for (int i = 1; i <= n; i++)
    {
        sa[a[i]].insert(i);
        // sb[b[i]].insert(i);
    }
    // cout << sa[2].size() << endl;
    for (int i = 1; i <= n; i++)
    {
        bool f = false;
        auto it = sa[b[i]].lower_bound(i);
        if (it != sa[b[i]].end())
        {
            int r = *it;
            if (qa(i, r) == b[i] && qb(i, r) >= b[i])
            {
                f = true;
            }
        }
        if (it != sa[b[i]].begin())
        {
            it--;
            int l = *it;
            if (qa(l, i) == b[i] && qb(l, i) >= b[i])
            {
                f = true;
            }
        }
        if (!f)
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• CF914C
• vue3 获取循环的div的总宽度
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• div滚动加载数据
• CF914E
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP

Codeforces Round 914 Divcodeforces round 914 div codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div codeforces round 915 div codeforces round 917 div codeforces round 912 div codeforces round 901 div