首页 > 其他分享 >Codeforces Round 914 (Div. 2)

Codeforces Round 914 (Div. 2)

时间：2023-12-11 16:01:41浏览次数：38  
标签：const int Codeforces long ++ dx using 914 Div

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;
}

标签：const,int,Codeforces,long,++,dx,using,914,Div
From： https://www.cnblogs.com/value0/p/17894627.html

相关文章

  • 232-父级div，包含子div，子div有点击事件，父div有点击事件，js如何实现，2个点击事件不干扰
    HTML结构<divid="parent"><divid="child"></div></div>JavaScript/jQuery代码：$(document).ready(function(){//父级div的点击事件处理程序$('#parent').on('click',function(){console.log(&#......
  • php 去除图片以及DIV的width、height、style
    1.去掉图片的宽高，去掉DIV的style样式$str='<divstyle="margin:0pxauto;width:740px;"><p><imgwidth="748"height="444"alt=""src="/images/upload/Image/manmiao_0001.jpg"/></p></div......
  • 图片铺满div元素不变形，超出部分隐藏，保留中心部分css代码
    在我们网站更新文章的时候，经常会插入图片，丰富信息。但是我们插入的图片长宽比例并不一定是固定的。我们在调用缩略图的时候，常常会出现图片变形的情况，高和宽不成比例。那么如何让图片不变形，又能铺满div元素呢？我们可以使用css代码中object-fit属性来实现。object-fit属性指定元素的......
  • CodeForces 575F Bulbo
    洛谷传送门CF传送门提供一个傻逼\(O(n^2)\)做法。首先考虑暴力dp，设第\(i\)轮后在\(j\)坐标上的最小花费为\(f_{i,j}\)，有：\[f_{i,j}=\minf_{i,k}+|j-k|+\begin{cases}l_i-j&j<l_i\\0&l_i\lej\ler_i\\j-r_i&j>r_i\end{cases}......
  • Codeforces Round 914 (Div. 2)
    CodeforcesRound914(Div.2)A.Forked!#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;voidsolve(){inta,b;intx,y;cin>>a>>b>>x>>y;map<pair<int,in......
  • [Codeforces] CF1793C Dora and Search
    CF1793CDoraandSearch题意给定一个长度为\(n\)的排列\(a\)，问是否存在正整数\(l,r\)使得\(a_l,a_r\)均不为\(a_{l...r}\)中的最大值或最小值。思路很明显的双指针，虽然我最开始的思路是二分预处理当前序列的最大值和最小值，并且一旦两段的\(l,r\)中有一个是最大或......
  • [Codeforces] CF1790D Matryoshkas
    CF1790DMatryoshkas题意ZYH的玩具有很多种类，每种玩具都是一段连续的区间（如\([3,4,5]\)）ZYH有很多种玩具，但是他不慎把所有玩具的元素乱序混合到了一起。例如玩具\([1,2,3,4]\)和玩具\([2,3]\)混合到一起后可能是\([2,2,3,4,3,1]\)。给定混合后的序列\(a\)，SA想知道Z......
  • Codeforces Round 803 (Div. 2)
    基本情况A题秒了。B题经典+2。（经典不开longlong）C题读错题，没得思路。B.RisingSandProblem-B-Codeforces思路好想，分类讨论找规律就行。这里还是要强调一下认真分析数据：InputThesecondlineofeachtestcasecontains\(n\)integers\(a_1,a_2,\ldots,a_n\)......
  • Codeforces Round 914 (Div. 2)
    基本情况脑子最卡的一集。A题读假题，卡了快一小时。B题代码太复杂，出错不好修改，一直调。虽然最后都出来了，但是没有剩下任何时间看后面题目了。A.Forked!Problem-A-Codeforces一开始不知道犯得什么病，觉得可以斜着走一格算作一步，然后情况就太多了，非常不好处理。后面突......
  • Codeforces Round 914 (Div. 2)
    C.ArrayGame题意：给定一个n的数组以及k的操作数，每次可以选择下表为i，j（i<j）得到一个abs（a[i]-a[j]）的数放在数组末尾，问你k次操作后，数组中最小的数是多少？思路：首先k>=3选相同的下表两次，一定结果是0，是最小。k==1遍历出下表两两相减的绝对值最小以及本身数组中最小的即可k==2要将数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99