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

Codeforces Round 892 (Div. 2)

时间:2023-08-13 16:23:12浏览次数:47  
标签:892 int max Codeforces cin seg ++ 区间 Div

手速慢了,掉分

C. Another Permutation Problem

Problem - C - Codeforces

题意

给定一个正整数\(n\),设序列\(p\)为\(n\)的排列,求\(\sum_{i=1}^{n}p_i \times i-max_{j=1}^np_j\times j\)的最大值。

思路

打表可知,答案的排列一定为翻转一部分后缀。暴力枚举要翻转的后缀即可。

代码

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

    int ans = 0;
    for(int i = 1; i < n; i++) {
        ans += i * i;
    }

    for(int i = 0; i < n; i++) {
        int x = 0, y = 0, mx = 0;
        for(int j = 1; j <= i; j++) {
            x += j * j;
            mx = max(mx, j * j);
        }
        
        for(int j = n, k = i + 1; j > i; j--, k++) {
            y += k * j;
            mx = max(mx, k * j);
        }

        ans = max(ans, x + y - mx);
    }

    cout << ans << "\n";
}

D. Andrey and Escape from Capygrad

Problem - D - Codeforces

题意

给定一些包含区间,\([l, r]\)包含区间\([a,b]\),如果一个人在区间\([l,r]\)内,那么他可以传送到区间\([a,b]\)中的任意点。现给定一些坐标,求从该总表出发,最大能传送到的坐标在哪里。

思路

题意可简化为有若干个区间\([l,b]\),在区间\([l,b]\)内可传送到端点\(b\),求最大能传送到的坐标。

先合并重合的区间,再对于每个询问的坐标,二分找到所在的区间。若该坐标不在任何区间,则答案为它自已。

代码

void solve() {
    int n;
    cin >> n;
 
    vector<array<int, 2>> seg(n);
    for(int i = 0; i < n; i++) {
        int l, r, a, b;
        cin >> l >> r >> a >> b;
        seg[i] = {l, b};
    }
 
    sort(seg.begin(), seg.end());
 
    vector<array<int, 2>> a;
    for(int i = 0; i < n; i++) {
        if(!a.empty() && a.back()[1] >= seg[i][0]) {
            a.back()[1] = max(a.back()[1], seg[i][1]);
        } else {
            a.push_back({seg[i][0], seg[i][1]});
        }
    }
 
    int q;
    cin >> q;
 
    while(q--) {
        int x;
        cin >> x;
 
        int p = lower_bound(a.begin(), a.end(), array{x + 1, 1}) - a.begin() - 1;
        if(p >= 0) {
            x = max(x, a[p][1]);
        }
        cout << x << " ";
    }
 
    cout << "\n";
}

标签:892,int,max,Codeforces,cin,seg,++,区间,Div
From: https://www.cnblogs.com/cenqi/p/17626698.html

相关文章

  • Codeforces Round 892 div2.C
    这C真的魔幻,官方题解完全和写的不一样,太玄学了,打表发现的规律这是打表代码:intmain(){cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)a[i]=i;LLans=0;do{autob=a;LLsum=0,mx=0;......
  • Codeforces Round 892 (Div.2)
    A.UnitedWeStand题解赛时想复杂了题目要求我们保证数组\(c\)中的数不是数组\(b\)中任意一个数的因子我们考虑将最小值置于数组\(b\)即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intmi=INF;for(inti......
  • Codeforces Round 874 G题解
    做不动那么多题了,来个GG就是问你一棵树能切成多少个大小为3的链,想了半天,想过dp啥的,但是后来发现这个贪心就好了,可以证明贪心找不到的,其他方法也找不到好久没复健了,这是第一次,感觉以后要多做题才可以#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(4e......
  • 【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    T1签到。T2送分题。T3大模拟,但是TLE两个点。#include<bits/stdc++.h>#definelllonglong#defineintlonglong#definereregisterusingnamespacestd;constintN=1e5+5,INF=0x3f3f3f3f;intn;queue<string>Q;map<string,int>zt;//0不在;1排队;2游玩;......
  • 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\)位的数字的其中一位,而对于不同的方案,其二进制位不完全相同,则每一个方案对应的花费一定不同,......