Codeforces Round #570 (Div. 3)

原创于 2020-02-02 01:04:01 发布 · 353 阅读

0 ·

CC 4.0 BY-SA版权

Codeforces 专栏收录该内容

5 篇文章

订阅专栏

本文解析了Codeforces Round #570 (Div.3)的五道题目，包括数字位和的4倍数寻找、最大值B的求解、电量消耗策略、数列中不重复计数元素的最大数量以及物品选择策略，提供了详细的算法思路与代码实现。

Codeforces Round #570 (Div. 3)

A：

题意：求每一位数字之和，然后开始遍历直到能被4整除即可

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,i,s=0;
	scanf("%d",&a);
	i=a;
	while(1)
	{
		a=i;
		while(a!=0)
		{
			s=s+a%10;
			a=a/10;
 
		}
		if(s%4==0)
		{
			break;
		}
		i++;
		s=0;
	}
	printf("%d\n",i);
	return 0;
}

B：

题意：求最大值B，使得所有|B-ai|<=k;

代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int i,n,k;
		scanf("%d%d",&n,&k);
		int a[1002];
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		int max=a[0],min=a[0];
		for(i=1;i<n;i++)
		{
			if(a[i]>max)
			{
				max=a[i];
			}
			if(a[i]<min)
			{
				min=a[i];
			}
		}
		if(min+k>=max-k)
		{
			printf("%d\n",min+k);
		}
		else
		{
			printf("-1\n");
		}
	}
	return 0;
}

C：

题意：就是有q个查询，每个查询给定4个数字，k，n，a，b，k是电脑总电量，n是需要的轮次，a是一种消耗方式，b是一种消耗方式，a>b，就是当剩余电量大于a的时候，可以以a或b消耗电量，当剩余电量大于b的时候，可以以b消耗电量，最终要求消耗的轮次等于n，并且最后剩余的电量严格大于0。要求找到满足以上条件的，对a消耗的最大轮次。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll k, n, a, b;
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
	    scanf("%lld%lld%lld%lld", &k, &n, &a, &b);
	    if(k<=n*b)
	    {
		  printf("-1\n");
	    }
	    else
        {
            ll resz=k-n*b;
	        ll r=a-b;
	        ll w=(resz-1)/r;
	        w=min(w,n);
	        printf("%lld\n", w);
        }

	}
	return 0;
}

D：

题意：q次询问，每次询问给出n个数，让你从这给数列找一组数，使得没有出现相同次数的两种数，问最多多少个。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn = 2e5+100;
int dis[maxn];
int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int i,j;
        for(i=0; i<=n; i++)
            dis[i] = 0;
        for(i=1; i<=n; i++)
        {
            int x;
            scanf("%d",&x);
            dis[x]++;
        }
        long long ans=0;
        sort(dis+1,dis+n+1,cmp);
        ans +=dis[1];
        int pre=dis[1];
        for(i=2;i<=n; i++)
        {
            if(dis[i]==0||pre==0)
                break;
            if(dis[i]>=pre)
            {
                if(pre==0)
                    break;
                ans+=pre-1;
                pre=pre-1;
            }
            else
            {
                ans+=dis[i];
                pre=dis[i];
            }

        }
        printf("%lld\n",ans);
    }
    return 0;
}

E：

题意：

题意：给出n个物品，每个物品有两个属性：种类ai(1<=ai<=n)和标记bi(bi为0或者1)。要求选出最多数量的物品满足：各个种类之间的选取数量不同，并且使bi=1的物品尽可能多

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int maxn2=3e6+5;
struct pot
{
    int x;
    int y;
    bool operator<(const struct pot &aa)const{
        if(x!=aa.x)return x<aa.x;
        return y<aa.y;
}
}p[maxn];
int y2[maxn];
int a[maxn],x1[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            a[i]=p[i].x;
        }
        sort(a+1,a+1+n);
        int siz=unique(a+1,a+1+n)-(a+1);
        for(int i=1;i<=siz;i++)
        {
            x1[i]=y2[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            int pos=lower_bound(a+1,a+1+siz,p[i].x)-a;
            x1[pos]++;
            y2[pos]+=(p[i].y==1);
        }
        priority_queue<struct pot>pq;
        for(int i=1;i<=siz;i++)
        {
            pq.push({x1[i],y2[i]});
        }
        int ac1,ac2;
        ac1=ac2=0;
        int fr=-1;
        while(!pq.empty())
        {
            struct pot aa=pq.top();
            pq.pop();
            if(aa.x==fr)
            {
                if(aa.x-1>0)pq.push({aa.x-1,min(aa.y,aa.x-1)});
            }
            else
            {
                fr=aa.x;
                ac1+=aa.x;
                ac2+=aa.y;
            }
        }
        printf("%d %d\n",ac1,ac2);
    }
    return 0;
}