2020 年百度之星·程序设计大赛 - 初赛一
[toc]
6743 Drink
题解：
每一种饮料求一个卡路里，取最小值
第一看以为是背包，其实出题人在第二层
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int dp[10005];
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
int main()
{
int t,e,f,m,n,pi,wi;
t=read();
while(t--)
{
scanf("%d%d",&n,&m);
//m=read();
int sum=10000;
for(int i=1;i<=n;i++)
{
wi=read();
pi=read();
int a;
if(m%wi==0)a=m/wi;
else a=m/wi+1;
sum=min(a*pi,sum);
}
printf("%d\n",sum);
//cout<<dp[m]<<endl;
}
return 0;
} 6744 GPA
题解：
给的一个分数范围，我们要让分数总和最高，就要找怎么给四个成绩赋分最有价值。一个分数区间对应的绩点是一样的，那我们就取分数区间的最低分即可，[95,100]都对应4.3，那我们就取95就行
具体做法我是这样的，用一个数组来村每个区间的最小数，用另一数组来存每个区间最小数对应的绩点，然后四个for循环暴力完事
代码：
#include<iostream>
#include<cstdio>
using namespace std;
double a[104];
int b[]={0,0,60,62,65,67,70,75,80,85,90,95};
void init()
{
a[0]=0;a[60]=1.0;a[62]=1.7;a[65]=2.0;a[67]=2.3;a[70]=2.7;a[75]=3.0;
a[80]=3.3;a[85]=3.7;a[90]=4.0;a[95]=4.3;
}
int main()
{
int t;
init();
scanf("%d",&t);
while(t--)
{
double sum=0;
int x;
scanf("%d",&x);
for(int i=1;i<=11;i++)
{
for(int j=1;j<=11;j++)
{
for(int k=1;k<=11;k++)
{
for(int w=1;w<=11;w++)
{
if(b[i]+b[j]+b[k]+b[w]<=x)
{
double ans=a[b[i]]+a[b[j]]+a[b[k]]+a[b[w]];
if(ans>sum)sum=ans;
}
}
}
}
}
printf("%.1f\n",sum);
}
} 6745 Dec
题解：
对于a和b，a和b的答案一定是在a-1，b或者a，b-1的基础上来的，如果a和b本身是互质则在前面的基础上+1，否则不加。
所以dp递推就行
看看数据，所以dp要预处理，然后直接输出答案
代码：
#include<iostream>
#include<cstdio>
#include <bitset>
using namespace std;
bitset<10000010> g;
int n,m,x,dp[1004][1005],top=0;
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=1002;i++)
for(int j=1;j<=1002;j++)
{
if(dp[i][j])continue;
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(gcd(i,j)==1)dp[i][j]++;
}
while(t--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",dp[a][b]);
}
} 
京公网安备 11010502036488号