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

Codeforces Round 892 (Div.2)

时间:2023-08-13 12:11:55浏览次数:60  
标签:10 892 int mi Codeforces mid vec 数组 Div.2

A. United We Stand

image-20230813113018886

题解

  • 赛时想复杂了
  • 题目要求我们保证数组\(c\)中的数不是数组\(b\)中任意一个数的因子
  • 我们考虑将最小值置于数组\(b\)即可
const int N = 2e5 + 10, M = 4e5 + 10;

int n;
int a[N];

void solve()
{
    cin >> n;
    int mi = INF;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        mi = min(a[i], mi);
    }
    vector<int> b, c;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] == mi)
            b.push_back(a[i]);
        else
            c.push_back(a[i]);
    }
    if (b.size() == 0 || c.size() == 0)
        cout << -1 << endl;
    else
    {
        cout << b.size() << " " << c.size() << endl;
        for (auto x : b)
            cout << x << " ";
        cout << endl;
        for (auto x : c)
            cout << x << " ";
        cout << endl;
    }
}

B. Olya and Game with Arrays

image-20230813113327912

题解

  • 我们考虑贪心
  • 对于所有数组中的最小值来说,不管我们怎么移动,他对答案的贡献不变
  • 所以我们考虑将每个数组中的最小值移动到某一个数组中,使得次小值对答案产生贡献
  • 我们如何确定被移动到的是哪一个数组呢
  • 只要对次小值排序即可,对于存在最小的次小值的数组就是被移动到的数组
const int N = 2e5 + 10, M = 4e5 + 10;

int n;
vector<int> vec[N];

void solve()
{
    cin >> n;
    int mi = INF;
    vector<int> b;
    for (int i = 1; i <= n; ++i)
    {
        int k;
        cin >> k;
        vec[i].clear();
        for (int j = 1; j <= k; ++j)
        {
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
        sort(all(vec[i]));
        b.push_back(vec[i][1]);
        mi = min(mi, vec[i][0]);
    }
    sort(all(b));
    int ans = 0;
    ans += mi;
    for (int i = 1; i < b.size(); ++i)
        ans += b[i];
    cout << ans << endl;
}

C. Another Permutation Problem

image-20230813114248637

题解

  • 打表找规律
  • 发现除了\(n=2\)时都是先升序后降序的形式,例如\([1, 2,3,4,8,7,6,5]\)
  • \(O(n^2)\)枚举在哪个位置开始降序即可
const int N = 2e5 + 10, M = 4e5 + 10;

int n;
int a[N], b[N], c[N];

void solve()
{
    cin >> n;
    if (n == 2)
    {
        cout << 2 << endl;
        return;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int mx = 0, sum = 0;
        for (int j = 1; j <= i; ++j)
        {
            sum += j * j;
            mx = max(mx, j * j);
        }
        int t = n;
        for (int j = i + 1; j <= n; ++j)
        {
            sum += t * j;
            mx = max(mx, t * j);
            --t;
        }
        ans = max(ans, sum - mx);
    }
    cout << ans << endl;
}

D. Andrey and Escape from Capygrad

image-20230813114604485

\(1 \leq n, q\leq 2e5\)

题解

  • 显然越向右移动越好,所以我们肯定选择\(l_i \leq x \leq b_i\)中较大的\(b_i\)传送,因为只有\(b_j > l_i\)时才能传送,所以实际上的区间为\([l_i, b_i]\)
  • 所以问题转化为给定\(n\)个区间\([l_i,b_i]\),对于数轴上一点\(x > 0\),对于左端点\(l_i \leq x\)的区间,我们找到其最大的右端点
  • 所以我们先考虑将区间合并\(O(nlogn)\)
  • 然后离散化区间左端点和询问点
  • 然后线段树在左端点处单点修改加上右端点的值即可,维护区间最大值
const int N = 4e5 + 10, M = 4e5 + 10;

int n, q;
struct node
{
    int l, r, a, b;
    bool operator<(const node &t) const
    {
        return l < t.l;
    }
} line[N];
int l[N], r[N], tot, qry[N];

struct info
{
    int mx;
    friend info operator+(const info &a, const info &b)
    {
        info c;
        c.mx = max(a.mx, b.mx);
        return c;
    }
};
struct SEG
{
    info val;
} seg[N << 2];

void up(int id)
{
    seg[id].val = seg[lson].val + seg[rson].val;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].val.mx = 0;
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    up(id);
}

void change(int id, int l, int r, int x, int val)
{
    if (l == r)
    {
        seg[id].val.mx = val;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(lson, l, mid, x, val);
    else
        change(rson, mid + 1, r, x, val);
    up(id);
}

info query(int id, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
    {
        return seg[id].val;
    }
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(lson, l, mid, ql, qr);
    else if (ql > mid)
        return query(rson, mid + 1, r, ql, qr);
    else
        return query(lson, l, mid, ql, qr) + query(rson, mid + 1, r, ql, qr);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int l, r, a, b;
        cin >> l >> r >> a >> b;
        line[i] = {l, r, a, b};
    }
    // 区间合并
    sort(line + 1, line + n + 1);
    tot = 0;
    int st = line[1].l, ed = line[1].b;
    line[n + 1] = {INF, INF, INF, INF};
    for (int i = 2; i <= n + 1; ++i)
    {
        auto [L, R, a, b] = line[i];
        if (L > ed)
        {
            tot++;
            l[tot] = st, r[tot] = ed;
            st = L, ed = b;
        }
        else
            ed = max(ed, b);
    }
    vector<int> vec;
    auto find = [&](int x)
    {
        return lower_bound(all(vec), x) - vec.begin() + 1;
    };
    for (int i = 1; i <= tot; ++i)
        vec.push_back(l[i]);
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        cin >> qry[i];
        vec.push_back(qry[i]);
    }
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());
    int m = vec.size() + 10;
    build(1, 1, m);
    for (int i = 1; i <= tot; ++i)
        change(1, 1, m, find(l[i]), r[i]);
    for (int i = 1; i <= q; ++i)
    {
        int x = find(qry[i]);
        int mx = query(1, 1, m, 1, x).mx;
        cout << max(mx, qry[i]) << " ";
    }
    cout << endl;
}

标签:10,892,int,mi,Codeforces,mid,vec,数组,Div.2
From: https://www.cnblogs.com/Zeoy-kkk/p/17626367.html

相关文章

  • Codeforces Round 874 G题解
    做不动那么多题了,来个GG就是问你一棵树能切成多少个大小为3的链,想了半天,想过dp啥的,但是后来发现这个贪心就好了,可以证明贪心找不到的,其他方法也找不到好久没复健了,这是第一次,感觉以后要多做题才可以#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(4e......
  • Codeforces Round 799 (Div. 4)(vp)
    CodeforcesRound799(Div.4)AMarathonvoidsolve(){vector<int>a(4);intgoal;cin>>goal;intans=0;for(inti=0;i<3;i++){intx;cin>>x;if(goal<x)ans++;}co......
  • Codeforces 1854E - Game Bundles
    都这么会乱搞的吗/xia随机生成若干\(<30\)的数直到它们当中和为\(60\)的子集个数\(>k\)为止。删去最后一个元素。然后考虑贪心确定\(>30\)的部分,具体方法是按照\(dp_{60-x}\)从大到小贪心选,如果剩余子集个数\(\gedp_{60-x}\)就在序列中加入\(x\)。如此随机化直到找......
  • CodeForces 1610F Mashtali: a Space Oddysey
    洛谷传送门CF传送门比较有启发性的题。首先,设\(a_u\)为与点\(u\)相连的边权和,答案的上界显然是\(\sum\limits_{i=1}^n[a_u\bmod2=1]\)。之后我们把P7816「Stoi2029」以父之名第一篇题解的做法搬过来,也就是:建一个虚点向原图度数为奇数的点连边权为\(1\)的边......
  • 【题解】Educational Codeforces Round 147(CF1821)
    自己做出来了A-E,F算是搞懂GF后第一道符合我这个菜鸡水平的实战,可惜的是根本没意识到可以GF。A.Matching题目描述:整数模板是每位均为数字或问号的字符串。如果可以用数字替换模板中的每个问号,从而获得该正整数(严格大于\(0\))的十进制表示形式,且不带任何前导零,则该正整数......
  • Codeforces Round 874 (Div. 3) 题解
    A.MusicalPuzzle字符串\(s\)的不同的长度为\(2\)的子串个数就是答案可以用set处理B.RestoretheWeather将\(a\)数组排序后,在\(b\)数组中找到第一个大于等于\(a_i-k\)的元素与\(a_i\)对应即可可以用multiset实现(用multiset自带的lower_bound()比较好,......
  • Codeforces Round 878 (Div. 3) 题解
    A.CipherShifer从头开始扫一遍即可,扫到两个相同的表示某一个字符的解密结束B.BinaryCafe首先,我们不妨把题意转换为有多少种不同的花钱方案因为每一种咖啡就是一个二进制有\(k\)位的数字的其中一位,而对于不同的方案,其二进制位不完全相同,则每一个方案对应的花费一定不同,......
  • 【题解】Educational Codeforces Round 148(CF1832)
    A.NewPalindrome题目描述:给你一个由小写字母组成的回文字符串,问你是否能在重排其之后构造出另一个与原串不同的回文字符串。多测,\(t\le1000,2\le|s|\le50\)题目分析:考虑其实就是前\(\lfloor\frac{n}{2}\rfloor\)个位置存在两种或以上的不同字符,因为这样直接交换对......
  • Codeforces 1857E:Power of Points 区间?
    1857E.PowerofPointsDescription:\(n\)个数:\(x_1,···,x_n\),从左向右扫,当\(s=x_i\)时,可以将这\(n\)个数分为若干个闭区间\([s,x_1],[s,x_2],···,[s,x_n]\)(当然如果\(x_i<s\),则区间形如\([x_i,s]\))对于每一个\(s\in(x_1,···,x_n),\)有一个整数\(p\),记\(f_......
  • Codeforces Round 881 (Div. 3)
    A.SashaandArrayColoring为了让贡献最大,每种颜色只能染两个数显然这两个数为最大值与最小值、次大值与次小值、第三大值与第三小值……以此类推即可B.LongLong为了让和最大,我们需要的就是把所有负数变成正数那么第一问的答案就是\(\sum_{i=1}^n|a_i|\)此外,因为每次变......