欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

百度之星第二场(前四道签到题)

程序员文章站 2022-04-01 18:55:08
如果你需要查看题目,请点击下方↓百度之星第二场题目因为是水题嘛,所以就不多赘述了。官方题解也早就出了,如果想看更为标准的解析请移步下方↓http://bestcoder.hdu.edu.cn/Poker这题其实很好想,我的思路是先把每次需要交的费用m先取出来,然后在用剩下的钱除以实际消耗的,就能得到次数y,最后因为事先取出m块钱,所以再从y次的基础上增加一次,就是最后的答案了。其中要注意的坑就是如果拥有的钱不足以支付一次的消耗,就需要特判 (用人话将就是一次也玩不起,就不要玩了,穷鬼不配玩游...

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