2020 年百度之星·程序设计大赛

Drink

Accepts: 1896

Submissions: 4596

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

12
5

解题思路：因为n种饮料种每种饮料的补充水分x和和包含的卡路里都不同，所以从头到尾遍历看哪种饮料消耗的卡路里最少(注意这里是 一种饮料一直喝)
我们便可以的到如下代码：

#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,t;
int x[105],y[105];
int main(void)
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&x[i],&y[i]);
        }
        int sum=INF;//初始化总卡路里
        for(int i=0;i<n;++i)
        {
            if(m%x[i])//如果不能被整除
            sum=min(sum,m/x[i]*y[i]+y[i]);
            else//能被整除
            sum=min(sum,m/x[i]*y[i]);
        }
        printf("%d
",sum);
    }
    
    return 0;
}

开始没看到一种饮料一直喝，还以为是完全背包问题(不会写)，结果后来发现是个大水题 T_T

GPA

传送门

Accepts: 1554

Submissions: 3947

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

0.0
17.2


解题思路：仔细分析其实我们不需要哪个分数区间，我们只需要区间的最小的值代表那个绩点，也就是说 95~100 -> 4.3 在最优的情况下，其实我们不需要在意在区间取值，95就能表示绩点4.3
总共有四个成绩，十一个分数段，那么就有两种循环方式，第一个是对分数段循环，第二个就是对四个成绩循环。
解法1：

#include<cstdio>
#include<iostream>
using namespace std;
int t,x,key;
int main(void)
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&x);
        double sum=0,sum2;
        for(int a=0;a<5;++a)
        {
            if(a*95>x)
            break;
            for(int b=0;b<5;++b)
            {
                if(a*95+b*90>x)
                break;
                for(int c=0;c<5;++c)
                {
                    if(a*95+b*90+c*85>x)
                    break;
                    for(int d=0;d<5;++d)
                    {
                        if(a*95+b*90+c*85+d*80>x)
                        break;
                        for(int e=0;e<5;++e)
                        {
                            if(a*95+b*90+c*85+d*80+e*75>x)
                            break;
                            for(int f=0;f<5;++f)
                            {
                                if(a*95+b*90+c*85+d*80+e*75+f*70>x)
                                break;
                                for(int g=0;g<5;++g)
                                {
                                    if(a*95+b*90+c*85+d*80+e*75+f*70+g*67>x)
                                        break;
                                    for(int h=0;h<5;++h)
                                    {
                                        if(a*95+b*90+c*85+d*80+e*75+f*70+g*67+h*65>x)
                                            break;
                                        for(int i=0;i<5;++i)
                                        {
                                            if(a*95+b*90+c*85+d*80+e*75+f*70+g*67+h*65+i*62>x)
                                            break;
                                            for(int j=0;j<5;++j)
                                            {
                                                key=a*95+b*90+c*85+d*80+e*75+f*70+g*67+h*65+i*62+j*60;
                                                sum2=a*4.3+b*4.0+c*3.7+d*3.3+e*3.0+f*2.7+g*2.3+h*2.0+i*1.7+j*1.0;
                                                if(key<=x)
                                                {
                                                    sum=max(sum,sum2);
                                                }
                                                else
                                                break;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        printf("%.1lf
",sum);
    }
    return 0;
}

解法2：

#include<cstdio>
#include<iostream>
using namespace std;
int a[11]={95,90,85,80,75,70,67,65,62,60,0};
double b[11]={4.3,4.0,3.7,3.3,3.0,2.7,2.3,2.0,1.7,1.0,0};
int main(void)
{
    
    int x,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&x);
        double sum=0;
        for(int i=0;i<11;++i)
        {
            for(int j=0;j<11;++j)
            {
                for(int k=0;k<11;++k)
                {
                    for(int l=0;l<11;++l)
                    {
                        int s=a[i]+a[j]+a[k]+a[l];
                        if(s<=x)
                        {
                            sum=max(sum,b[i]+b[j]+b[k]+b[l]);
                        }
                    }
                }
            }    
        }
        printf("%.1lf
",sum);
    }
    return 0;
}

Dec

传送门

Accepts: 1284

Submissions: 4572

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)



样例解释
2 3 -> 1 3 -> 1 2 -> 1 1


解题思路：这道题开始可能会有人觉得这是数学题目，其实不然，再通过仔细阅读题目之后，我们能发现一个问题数据有1e6组而且a和b刚好小于等于1e3，这不就明显摆着动态规划嘛
由于每次从a,b两个数中选一个然后减一，那么我们就能把这个问题拆成小问题，a和b的互质的数就去找 a-1和b互质的数，a和b-1互质的数，然后选出最大的值赋给dp[a][b]，但是要注意a和b本身就互质的情况
由于1和其他数字都互质所以我们可以初始化dp[i][1]=dp[1][i]=i。
状态转移方程式为：
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
&&if(gcd(i+1,j+1)==1)
dp[i+1][j+1]++;
我们可以得到如下代码：

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1002
int t,a,b;
int dp[maxn][maxn];
int main(void)
{
    for(int i=1;i<maxn;++i)
    dp[i][1]=dp[1][i]=i;
    for(int i=1;i<maxn;++i)
    {
        for(int j=1;j<maxn;++j)
        {
            if(__gcd(i+1,j+1)==1)
            {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])+1;
            }
            else
            {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        printf("%d
",dp[a][b]);
    }
    return 0;
}

这里有个比较玄学的问题，就是maxn的大小，如果maxn大于等于1005就会T(我习惯开1005)，换句话说maxn的值只能取1001，1002，1003，1004(亲身试过的T^T)

这是1005的那一发，当时还以为这不是动归的题，，，

然后最后时间快截止了改了下maxn的大小改成了1002

2020 年百度之星&#183;程序设计大赛

Drink

GPA

Dec

2020 年百度之星·程序设计大赛