首页 > 技术交流 > 百度开发笔试题解

百度开发笔试题解

头像
viia
编辑于 2019-09-18 17:53:29 APP内打开
赞 6 | 收藏 21 | 回复8 | 浏览1886
3小时2场重叠的笔试,百度是后一个..以为肯定做不完了.还好题目简单..
编程3个,2个签到一个hard..要是最后一题简单点就不写题解了..

1.给n,m,k,范围1e9,求满足条件的自然数a,b,(n-a)(m-b)<=k,且a+b最小
acm签到题的感觉..只在n,m中较小的一个减可以保证a+b最小,类似均值不等式的原理...就是和一定的时候2个数越接近积越大,反之也是。
n,m已经定了,要让他们的和减少最小的情况下积减少最大,就让他们的差值尽量大,所以全减到最小的上保证差值最大。
(n-a)*m<=k,移项出来O(1)的公式就行
#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
	int i, j;
	LL n, m, k;
	while (~scanf("%lld%lld%lld", &n, &m, &k))
	{
		if (n > m)
			swap(n, m);
		printf("%lld\n", n - k / m);
	}
	return 0;
}

2.给n个任务,每个任务一个ddl,一个完成该任务需要的时间,一次只能做一个任务直到做完,问可不可能每个任务都在ddl之前完成。范围2e5
贪心..对ddl排序,先做ddl小的就是最优解....
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node{ int a, b; }t[200005];
bool cmp(node x, node y)
{
	return x.b < y.b;
}
int main()
{
	int i, j;
	int n;
	scanf("%*d");
	while (~scanf("%d", &n))
	{
		for (i = 0; i < n; i++)
			scanf("%d%d", &t[i].a, &t[i].b);
		sort(t, t + n, cmp);
		LL sum = 0;
		for (i = 0; i < n; i++)
		{
			sum += t[i].a;
			if (sum > 1LL * t[i].b)
				break;
		}
		puts(i == n ? "Yes" : "No");
	}
	return 0;
}

3.给一个树,节点1-n,点1是黑色点n是白色其他无色,2个人轮流操作博弈,1号每轮选一个黑色点,染黑相邻无色的点,2号每轮选白点同样操作。(选的点必须有相邻的无色点)第一个操作不了的人输。问这场博弈谁赢...范围1e5
反正是树,就当做1是根节点。所以白色能染最高的白色点下的所有点,黑色能染剩下的点,所以关键是白色最高点多高,所以开局双方都在1-n的最短路上染,染相邻了局势就定了。
然后根据这个局势,算出来黑白能染色几次,染色多的赢。
分分钟口头ac..代码写了至少40分钟..写的非常难看,删删改改的..感觉有其他方法..
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node { int v, ne; }a[200005];
int k;
int h[100005];
int fa[100005];
bool vi[100005];
int color[100005];
int co1, co2;
void add(int u, int v)//初始k=1
{
	a[k].v = v, a[k].ne = h[u], h[u] = k++;
}
void find_fa(int x)
{
	vi[x] = 1;
	for (int i = h[x]; i; i = a[i].ne)
	{
		if (vi[a[i].v] == 0)
			fa[a[i].v] = x, find_fa(a[i].v);
	}
}
int get_dis(int x)
{
	if (fa[x] == 1)
		return 1;
	return get_dis(fa[x]) + 1;
}

void coloring1(int x)
{
	int flag = 0;
	for (int i = h[x]; i; i = a[i].ne)
	{
		int ne = a[i].v;
		if (color[ne] == 0)
		{
			color[ne] = 1;
			flag++;
			coloring1(ne);
		}
	}
	if (flag != 0)
		co1++;
}
void coloring2(int x)
{
	int flag = 0;
	for (int i = h[x]; i; i = a[i].ne)
	{
		int ne = a[i].v;
		if (color[ne] == 0)
		{
			color[ne] = 2;
			flag++;
			coloring2(ne);
		}
	}
	if (flag != 0)
		co2++;
}
int get_fa(int x, int count)
{
	if (count == 0)
		return x;
	return get_fa(fa[x], count - 1);
}
int main()
{
	int i, j;
	int n;
	scanf("%*d");
	while (~scanf("%d", &n))
	{
		k = 1;
		memset(h, 0, sizeof(h));
		memset(fa, 0, sizeof(fa));
		memset(vi, 0, sizeof(vi));
		memset(color, 0, sizeof(color));
		for (i = 1; i < n; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			add(x, y);
			add(y, x);
		}
		find_fa(1);
		int dis = get_dis(n);
		int fa2 = get_fa(n, (dis - 1) / 2);
		co1 = 0, co2 = 0;
		color[1] = 1, color[n] = 2;
		int it = n;
		for (i = 0; i < (dis - 1) / 2; i++)
		{
			color[fa[it]] = 2;
			it = fa[it];
		}
		coloring1(1);
		for (i = 1; i <= n; i++)
		{
			if (color[i] == 2)
				coloring2(i);
		}
		puts(co2 <= co1 ? "niuniu" : "niumei");
	}
	return 0;
}












8条回帖

回帖
加载中...
回帖

本文相关内容

相关热帖

近期热帖

热门推荐