百度24届暑期实习招聘研发A卷题解

第一题

标签：计数

题意：给一个数组a，元素分为RED和BLUE两类，求每一对RED、BLUE元素乘积和。

思路：很简单，就是每一个RED和BLUE相乘再相加，等价于 $\sum_{i\in red,j \in blue}{a[i]\times a[j]}=\sum_{i \in red}{a[i]}\times \sum_{j \in blue}{a[j]}$ （这个式子可能有错，但大题意思能理解就行）。因此只需要把RED和BLUE分别求和最后相乘就行。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int MOD = 1e9+7;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	int r = 0,b = 0;
	for(int i = 0 ; i < n ; i ++)
	{
		cin >> a[i];
	}
	cin >> s;
	for(int i = 0 ; i < n ; i ++)
	{
		if(s[i] == 'R')
		{
			r += a[i];
			r %= MOD;
		}
		else
		{
			b += a[i];
			b %= MOD;
		}
	}
	cout << (long long)r*b%MOD << "\n";
}

第二题

标签：贪心

题意：给一个浮点数0.xxx...，可以删除任意个0.后的数字，求删除后的最大值。（如0.1535可以删除1、3得到0.55）

思路：其实不难，我一开始以为是删除一个前缀导致我去写SA板子了，若各位感兴趣可以了解一下如果是删除前缀和不是删除任意个数字的话就变成了求字典序最大的后缀了（SA板子题）。继续讲解本题思路，每一位数值越大整体就越大，我们应该贪心的把数值大的留下来，然后再从后面留其次大的。举个例子，对于0.988987，我们应该先留下两个9得到0.99，再留下后面两位87这样可以得到0.9987是最大的。因此我们只需要把每一位的位置提取出来，从数值大的到数值小的，从位置小的到位置大的填充答案。维护当前位置pos，只有目标位置大于pos时我们才填充同时更新pos即可。

#include <bits/stdc++.h>
using namespace std;
string s;
vector<int>v[10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    string ans = "0.";
    for(int i = 2 ; i < s.size() ; i ++)
    {
    	v[s[i]-'0'].push_back(i);
    }
    int p = 0;
    for(int i = 9 ; i >= 0 ; i --)
    {
    	for(int j = 0 ; j < v[i].size() ; j ++)
    	{
    		int u = v[i][j];
    		if(u > p)
    		{
    			ans += char('0' + i);
    			p = u;
    		}
    	}
    }
    cout << ans << "\n";
}

第三题

标签：dfs、延迟下发

题意：给一颗根节点为1的树，每个节点有对应的权值 $a_{i}$ 。现在输入m次操作，每次操作选择一个子树 $i$ 并使当前子树的所有节点的权值乘以 $x$ 。求m次操作后，求所有子树权值乘积末尾0的数量。

思路：题目求的是末尾0的个数，且计算操作是乘积，因此对于权值只需要保留2、5两个因子就行。对于每一个节点我们保留四类信息，t表示当前权值因子2的个数、f表示当前权值因子5的个数、lt表示以当前节点为根节点的子树需要下发的2的个数、lf表示当前节点为根节点的子树需要下发的5的个数。（类似于线段树的lazy下发，但是线段树每次更新的时候可能就要下发，这里只有最后输出的时候才下发，所以很简单）。

下发就是直接让子节点的lazy数值加上父亲的lazy数值，同时让当前节点的t、f分别加上lt、lf即可。题目最后要求输出每一个子树节点乘积的0数，因此还需要上发，直接让父节点累加子节点一路递归上去就行。具体实现看代码一眼可知。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct P
{
    long long t, f;
    long long lt, lf;
} p[N];
int n;
vector<int> v[N];

void dfs(int x)
{
	p[x].t += p[x].lt;
	p[x].f += p[x].lf;
	for(int i = 0 ; i < v[x].size() ; i ++)
	{
		int u = v[x][i];
		p[u].lt += p[x].lt;
		p[u].lf += p[x].lf;
		dfs(u);
		p[x].t += p[u].t;
		p[x].f += p[u].f;
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        while (x % 2 == 0)
        {
            p[i].t++;
            x >>= 1;
        }

        while (x % 5 == 0)
        {
            p[i].f++;
            x /= 5;
        }
    }

    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y;

        cin >> x >> y;

        while (y % 2 == 0)
        {
            p[x].lt++;
            y >>= 1;
        }

        while (y % 5 == 0)
        {
            p[x].lf++;
            y /= 5;
        }

    }
    dfs(1);
    for(int i = 1 ; i <= n ; i ++)
    {
    	cout << min(p[i].t,p[i].f) << " ";
    }
}

#百度笔试#