百度之星第二场(前四道签到题)
如果你需要查看题目,
请点击下方↓
百度之星第二场题目
因为是水题嘛,所以就不多赘述了。
官方题解也早就出了,如果想看更为标准的解析
请移步下方↓
http://bestcoder.hdu.edu.cn/
Poker
这题其实很好想,我的思路是先把每次需要交的费用m先取出来,然后在用剩下的钱除以实际消耗的,就能得到次数y,最后因为事先取出m块钱,所以再从y次的基础上增加一次,就是最后的答案了。其中要注意的坑就是如果拥有的钱不足以支付一次的消耗,就需要特判 (用人话将就是一次也玩不起,就不要玩了,穷鬼不配玩游戏) ,也就是n<m时的情况。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
double a=2.0;
int main()
{
int t,x,y;
double ans,n,m,p,sum=0;
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf",&n,&m,&p);
if(n<m)
{
printf("0\n");
continue;
}
sum=n-m;
y=sum;
ans=m*p/100;
x=ans;
if(ans>x)
x++;
y/=x;
y++;
printf("%d\n",y);
}
return 0;
}
Distance
我记得19年百度之星好像也出过一次类似的题目,(当时太菜没做出来QAQ,今天!一雪前耻!!!)
我的思路是这样的:
假设有 1 2 3 4 5 5个数在数轴上,从1开始向着更大的数前进(请自行脑补滑动变阻器),那么会有1→2、1→3、1→4、1→5 四种路线,而所有的路线都必须经过1和2之间的距离也就是4×(2-1)=4
然后从第2点开始,会有2→3、2→4、2→5三条线,这三条线都会经过2和3之间的距离,也就是3×(3-2)=3,但是从1开始走的1→3、1→4、1→5,也会经过这段距离,即又是3×(3-2)=3,然后我们将他们合并同类项,变成了(1/2)→3、(1/2)→4、(1/2)→5,就是 2×3×(3-2)
不难看出,就是选择某点x,那么能够路过x与x+1点之间路径的道路,就是x及其之前的点的数与x之后点的数的积,用人话讲就是:“把一堆点分成两部分,x及其之前,x之后,然后把它们的个数相乘,最后再乘上x与x+1的距离”
然后每个点都这么求一下,最后计算总和,就解出来啦 \ (^ o ^) / ~
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long n,sum=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
for(long long i=1;i<n;i++)
{
sum+=(a[i+1]-a[i])*(i*(n-i));
}
printf("%lld\n",sum);
}
return 0;
}
Covid
这题其讲的是病毒的传播 (结合实事,讲究),但是数据量和现实可没法比 (对面400万了,能比吗?真要算早MLE了)
我做了两张表
- 表格dt是人的编号和时间,记录某人某事在某地
(有写作文内味儿了) - 表格pt是地点和时间,记录某地某时出现感染者,到过该地区的人均被感染
然后用时间做自变量,在时间轴上看每个人在某个时刻都在哪个地方 (老时间管理大师了) 然后康康他们有没有被感染,感染就OMG一下,这个函数是用来把这个人剩下的时间所到过的地点都标记感染,等到健康的人在相应的时间到达相应的地点,就记录感染,然后把这个人剩下的时间地点也扩散一下,最后的最后就输出人就好了。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int dt[20005][105],pt[15][105],gr[200005],tmax;
void omg(int id,int t)
{
for(int o=t;o<=tmax;o++)
{
if(dt[id][o]!=0)
pt[dt[id][o]][o]=1;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
tmax=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int it;
scanf("%d",&it);
for(int j=1;j<=it;j++)
{
int x,y;
scanf("%d%d",&x,&y);
dt[i][x]=y;
if(x>tmax)tmax=x;
}
}
omg(1,1);
gr[1]=1;
for(int i=1;i<=tmax;i++)
{
for(int j=1;j<=n;j++)
{
if(pt[dt[j][i]][i]==1)
{
gr[j]=1;
omg(j,i+1);
}
}
}
printf("1");
for(int i=2;i<=n;i++)
{
if(gr[i])printf(" %d",i);
}
printf("\n");
for(int i=1;i<=n;i++)
{
gr[i]=0;
for(int j=1;j<=tmax;j++)
{
dt[i][j]=0;
}
}
for(int i=1;i<=10;i++)
for(int j=1;j<=tmax;j++)
pt[i][j]=0;
}
return 0;
}
Car
这道题没啥好说的,数据量不大,一发dfs就过了。
下面是AC代码:
##include<bits/stdc++.h>
using namespace std;
int a[15],b[10],da,xiao;
void dfs(int k)
{
if(k==10)
{
xiao=99999;
for(int o=1;o<6;o++)
{
if(xiao>b[o])xiao=b[o];
}
if(xiao>da)
{
da=xiao;
/* for(int o=1;o<=5;o++)
{
printf("%d ",b[o]);
}
printf("\n");*/
}
return;
}
for(int o=1;o<=5;o++)
{
b[o]+=a[k];
dfs(k+1);
b[o]-=a[k];
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,x,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x%10]++;
}
dfs(0);
m=n-da;
printf("%d\n",m);
da=0;
for(int i=0;i<10;i++)
{
a[i]=0;
}
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_43813647/article/details/107588412