百度之星第二场（前四道签到题）
如果你需要查看题目，
请点击下方↓
百度之星第二场题目
因为是水题嘛，所以就不多赘述了。
官方题解也早就出了，如果想看更为标准的解析
请移步下方↓
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