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总结
推荐阅读
-
Educational Codeforces Round 55 (Rated for Div. 2) B
-
Educational Codeforces Round 55 (Rated for Div. 2)
-
【扫描线+计数去重】Codeforces Round #672 (Div. 2) D. Rescue Nibel!
-
Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems 矩阵优化
-
【Educational Codeforces Round 53 (Rated for Div. 2)】
-
Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities
-
Educational Codeforces Round 53 (Rated for Div. 2)
-
Educational Codeforces Round 53 (Rated for Div. 2)D(模拟)
-
Educational Codeforces Round 53 (Rated for Div. 2) D - Berland Fair
-
Educational Codeforces Round 53 (Rated for Div. 2)