Educational Codeforces Round 112(Div.2)

题目列表

1.A
2.B
3.C

这几篇题解都是我从自己的CSDN里搬来的，不然显得我没打过ACM www

1.A

原题链接

题目大意

有三种方案做蛋糕，15分钟做6块蛋糕、20分钟做8块蛋糕、25分钟做10块蛋糕，输入人数，求做出大于等于人数的蛋糕数的最短时间。

解题思路

看上去像是背包贪心，但发现这三种方法的性价比是一样的。由找规律发现由6，8，10可以组成大于等于6的所有偶数，所以答案就出来了。我刚刚开始做的时候没有去找规律，认为选择一种方案会影响整体最优解，于是求了下6，8，10的最小公倍数，这样就可以避免这种影响了，于是我打了个离线表，一交wa了，小丑竟是我自己，赛后看数据是121的时候我的程序输出了315，显然认为最小公倍数就不受影响的思路是错误的，6 8 10是可以组合出122的…

AC代码

#include<bits/stdc++.h>
using namespace std;
//int d[120]={0, 15, 15, 15, 15, 15, 15, 20, 20, 25, 25, 30, 30, 35, 35, 40, 40, 45, 45, 50, 50, 55, 55, 60, 60, 65, 65, 70, 70, 75, 75, 80, 80, 85, 85, 90, 90, 95, 95, 100, 100, 105, 105, 110, 110, 115, 115, 120, 120, 125, 125, 130, 130, 135, 135, 140, 140, 145, 145, 150, 150, 155, 155, 160, 160, 165, 165, 170, 170, 175, 175, 180, 180, 185, 185, 190, 190, 195, 195, 200, 200, 205, 205, 210, 210, 215, 215, 220, 220, 225, 225, 230, 230, 235, 235, 240, 240, 245, 245, 250, 250, 255, 255, 260, 260, 265, 265, 270, 270, 275, 275, 280, 280, 285, 285, 290, 290, 295, 295, 300};
int main(){
    int t;
    scanf("%d",&t);
    int n;
    long long tmp;
    long long ans;
    while(t--){/*
        scanf("%lld",&tmp);
        n=tmp%120;
        ans=tmp/120*300;
        ans+=d[n];
        printf("%lld\n",ans);*/
        cin>>tmp;
        if(tmp<6)
            cout<<15<<endl;
        else{
            ans=(tmp+1)/2*5;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

2.B

原题链接

题目大意

一个桌子上放着一个矩形，要往桌子上再放一个矩形，求能否放下那个矩形，如果能第一个矩形需要移动的距离是多少。

解题思路

算出第一个矩形的长度和宽度，如果两个矩形的长和宽同时大于桌子的长宽，那么肯定是放不下的；用贪心的直觉，要想移动最小，那么第二个矩形肯定要放在四个角上，第一个矩形肯定只有横向和纵向移动，所以枚举四个点取最小值。这题目刚刚开始看上去挺吓人的，输出这里写了个1e-6的精度，以为是什么几何加二分题直接skip，后来看看还是可以写的，这题面纯属吓唬人。写是能写，但是大概我几何天赋不好，几个条件对着草稿看半天才写出来…

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    int W,H,x1,y1,x2,y2;
    int w,h;
    int w1,h1;
    int minn;
    while(t--){
        scanf("%d%d%d%d%d%d%d%d",&W,&H,&x1,&y1,&x2,&y2,&w,&h);
        w1=x2-x1;
        h1=y2-y1;
        minn=100000000;
        if(w1>W||h1>H||w>W||h>H||(w1+w>W && h1+h>H)){
            printf("-1\n");
        }
        else{
            if((x1>=w)||(y1>=h)||(H-y2>=h)||(W-x2>=w))
                printf("0\n");
            else{
                if(w+w1<=W){
                    minn=min(minn,abs(w-x1));
                    minn=min(minn,abs(W-w-x2));
                }
                if(h+h1<=H){
                    minn=min(minn,abs(H-h-y2));
                    minn=min(minn,abs(h-y1));
                }
                printf("%d\n",minn);
            }
        }
    }
    return 0;
}

3.C

原题链接

题目大意

给出一个2 * m的矩形，alice和bob轮流从(1,1)走到(2,m)，他们只能向下或者向左移动，alice走到终点的路上拿走路径上的分数，bob走到终点路上捡起路径上的分数，alice想要让bob捡到的分数最小，而bob想让他的分数最大，求出最终的答案。

解题思路

如图，alice要从(1,1)到(2,m)，因为只能向左或者向下，所以她的路径能把整张图剩下分数分成两个部分，而alice要让bob的分数最小，就是要让剩下两个部分的最大值取到最小。在这里插入图片描述

所以枚举往下的点，打一个前缀和后缀表遍历取最大值的最小值即可，时间O(N)。

刚刚开始读题读了半天都不懂，以为alice是要让她自己的分数最小，后来读懂了想了好几条思路，不是tle就是wa了，比赛后两三分钟交了一发终于ac了，感觉主要是B题耽误了太多时间，害。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int b[maxn];
int sa[maxn];
int sb[maxn];
int main(){
    int t;
    scanf("%d",&t);
    int m;
    int i,j,k;
    int maxx,mi,ans;
    int s1,s2;
    while(t--){
        scanf("%d",&m);
        for(i=0;i<m;i++)
            scanf("%d",&a[i]);
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        sb[0]=b[0];
        sa[m-1]=a[m-1];
        for(i=1;i<m;i++){
            sb[i]=b[i]+sb[i-1];
            sa[m-1-i]=a[m-1-i]+sa[m-i];
        }
        ans=min(sa[1],sb[m-2]);//~~~~
        for(i=1;i<m-1;i++){
            ans=min(ans,max(sa[i+1],sb[i-1]));
        }
        if(m==1){
            printf("0\n");
        }
        else if(m==2){
            printf("%d\n",min(a[1],b[0]));
        }
        else{
            printf("%d\n",ans);
        }
    }
    return 0;
}

2021/08/12

> CLICK TO back <