百度开发笔试题解
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;
}
