欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Educational Codeforces Round 55 (Rated for Div. 2)

程序员文章站 2024-03-19 09:16:34
...

看淡人生之后的第一场vp,写了三个题,现在最好能做到无差别补题,不能碰见不喜欢做的题就放了


Vasya and Book
每次只能翻d页,到头尾的时候不能再翻了,问从x页翻到y页,最少用多少次,或者翻不到的话输出-1
对于x直接能翻到y的情况,就直接更新最小值。
之后我们判断,y到第一页和第n页能不能到,能的话,就可以先从x翻到不能翻,之后跳过去,记录最小值。
Vova and Trophies
只进行一次交换操作,让操作之后的序列‘G’的连续长度最长。
我们分情况考虑这个问题
如果只有一段G,那么答案就是这个段的长度
如果有两个以上的段,那么任何一个段都可以从其他段借一个过来,所以是所有段长度+1的最大值。
有种特殊的情况,经过一次交换可以让两个段接在一次,如果只有两个段,那么这个操作是没必要的,再大于3个段的时候,就可以让两个段接在一次。
C. Multi-Subject Competition
n个人,m中不同的能力,每个人对于某个个能力有一个能力值,现在选出一个让所有能力值相加最大的方案,选择的人中,每个能力的人数是相同的。
首先先对每个能力可以选择的人从大到小排个序,然后我们对于每一种能力,累计一下这个类选i个人的时候,得到的正的能力值。然后对于每个类别都做一次,相当于所有的类都选的时候,我们对于每个类选择k个人的时候的最大值。

#include <bits/stdc++.h>
#include <cstring>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define All(x) (x).begin(),(x).end()
using namespace std;
const ll INF = (1LL<<60)-1LL;
const int MAXN = 1e5 + 5;
vector<int> can[MAXN];
ll sum[MAXN];
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        can[x].pb(y);
    }
    for(int i = 1;i<=n;i++)
    {
        sort(All(can[i]),greater<int>());
    }
    int mnl = n;
    for(int i =1;i<=n;i++)
    {
        ll now = 0;
        int len = 0;
        for(int x : can[i])
        {
            now += x;
            if(now >= 0)
            {
                sum[++len] += now;
            }
        }
    }
    ll ans = 0;
    for(int i = 1;i<=m;i++) ans = max(ans,sum[i]);
    cout<<ans<<endl;
    return 0;
}

上一篇: 2019.6.26 JZ DAY2总结

下一篇: