首页 > 代码库 > Educational Codeforces Round 21 A-E题题解

Educational Codeforces Round 21 A-E题题解

2024-10-18 18:55:01   210人阅读

A题      ............太水就不说了，贴下代码

#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m;
int main()
{
    int i,j;
    scanf("%d",&n);
    int nn=n;
    int cnt=1;
    while(nn>=10)
    {
        nn/=10;
        cnt*=10;
    }
    printf("%d\n",cnt*(nn+1)-n);
}

B题    开始没看懂题什么意思（英语渣），然后看着样例找到了规律，就AC了

　　   题意是计算上升和下降的序列数之和，再除以n-k+1即可，相当于求其中每k个数的和的平均值！

 

#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m,k;
double arr[200005];
double sum[200005];
int main()
{
    int i,j;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)scanf("%lf",&arr[i]);
    sum[0]=0;
    for(i=1;i<=n;i++)sum[i]=sum[i-1]+arr[i];
    double ans=0;
    for(i=0;i+k<=n;i++)
    {
        ans+=sum[i+k]-sum[i];
    }
    ans/=((n-k+1));
    printf("%.10f\n",ans);
}

C 题     题目的意思是主人有n个茶杯，每个茶杯有容量。现在给一壶茶，总量为w。希望倒茶满足条件：每杯茶要超过容量的一半，并且w被倒光，茶杯内的茶水为整数，容量大的杯子内的茶不允许比容量小的杯子内的茶水少。

先给每个茶杯倒一半的水，然后把剩下的水尽量倒到容量大的茶杯里，倒完为止

#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m,w;
int arr[105];
typedef struct node
{
    int id,val,lim;
    friend bool operator<(node a,node b){return a.lim<b.lim;}
}node;
node axx[105];
int main()
{
    int i,j;
    scanf("%d%d",&n,&w);
    int lim=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
        lim+=(arr[i]+1)/2;
    }
    if(w<lim)printf("-1\n");
    else
    {
        w-=lim;
        for(i=0;i<n;i++)axx[i].id=i,axx[i].val=(arr[i]+1)/2,axx[i].lim=arr[i];
        sort(axx,axx+n);
        for(i=n-1;i>=0&&w>0;i--)while(axx[i].lim>axx[i].val&&w>0)axx[i].val++,w--;
        for(i=0;i<n;i++)arr[axx[i].id]=axx[i].val;
        for(i=0;i<n;i++)
        {
            if(i)printf(" ");
            printf("%d",arr[i]);
        }
        printf("\n");
    }
}

D 题    给你一个序列ai，首先你可以让序列中的一个数移动到这个序列的任何一个位置，然后让你求是否存在一个前缀，使得前缀和等于序列中其余的数的和

解法:扫一遍求前缀和，扫x时有三种情况是yes，第一，1~x的前缀和恰好等于序列总和的一半；第二，存在前缀序列中某一个数跳到了后缀里，使得新的前缀和满足条件，

即(1~x+1前缀和-跳出去的数的值)=序列总和的一半；第三，存在后缀序列中某一个数跳到了前缀里，使得新的前缀和满足条件，即(1~x-1前缀和+跳进来的数的值)=序列总和的一半，

只要用map来维护前缀和后缀中存在的数即可

#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
int n,m;
ll arr[1000005];
ll sum[1000005];
map<ll,int>dui1,dui2;
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%I64d",&arr[i]);
    dui1.clear();
    dui2.clear();
    sum[0]=0;
    for(i=1;i<=n;i++)sum[i]=sum[i-1]+arr[i];
    if(sum[n]&1)
    {
        printf("NO\n");
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(!dui2.count(arr[i]))dui2[arr[i]]=1;
            else dui2[arr[i]]++;
        }
        for(i=1;i<n;i++)
        {
            dui1[arr[i]]=1;
            dui2[arr[i]]--;
            if(sum[i]==sum[n]/2)
            {
                printf("YES\n");
                return 0;
            }
            else if(dui1.count(arr[i+1]+sum[i]-sum[n]/2))
            {
                printf("YES\n");
                return 0;
            }
            else if(dui2[-sum[i]+arr[i]+sum[n]/2]>0)
            {
                printf("YES\n");
                return 0;
            }
        }
        printf("NO\n");
    }
    return 0;
}

E题   题意是一个01背包，坏消息是n<=100000,m<=300000,好消息是w=1,2,3...这个题直接O(nm)去做肯定不行，模拟比赛的时候我心存侥幸大范围贪心，小范围dp，然后果断WA了....

正解是三分法，首先我们把物品以w=1,2,3分类，然后分别排序，并求出前缀和，然后枚举取用w=3的物品的个数，然后 三分2的个数， 1的个数也就知道了 。而2的个数和是一个单峰函数，

所以可以用三分法

#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
vector<ll>arr[4];
ll sum[4][300005];
ll n,m;
bool cmp(ll a,ll b){return a>b;}
ll getans(ll tri,ll dob){return sum[3][tri]+sum[2][dob]+sum[1][m-tri*3-dob*2];}
int main()
{
    ll i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        ll w;
        ll val;
        scanf("%I64d%I64d",&w,&val);
        arr[w].push_back(val);
    }
    for(i=1;i<=3;i++)sort(arr[i].begin(),arr[i].end(),cmp);
    for(i=1;i<=3;i++)
    {
        sum[i][0]=0;
        for(j=1;j<=arr[i].size();j++)sum[i][j]=sum[i][j-1]+arr[i][j-1];
        for(j=arr[i].size()+1;j<=m;j++)sum[i][j]=sum[i][j-1];
    }
    ll maxn=0;
    for(i=0;i<=arr[3].size();i++)
    {
        if(3*i>m)break;
        ll l=0,r=(m-3*i)/2;
        while(r-l>2)
        {
            ll rmid=(r*2+l)/3;
            ll lmid=(l*2+r)/3;
            ll ans1=getans(i,lmid);
            ll ans2=getans(i,rmid);
            if(ans1>ans2)r=rmid;
            else l=lmid;
            maxn=max(maxn,ans1);
            maxn=max(maxn,ans2);
        }
        for(j=l;j<=r;j++)maxn=max(getans(i,j),maxn);
        //printf("%I64d\n",maxn);
    }
    printf("%I64d\n",maxn);
    return 0;
}

 

Educational Codeforces Round 21 A-E题题解


联系
我们