百度历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、混战世界

【题目描述】战乱年代，整个世界各个军阀的兵团混战，你是PZ军团的战略参谋，你手下有n（保证为3的倍数）个士兵，第i个士兵的物理攻击数值为Ai，魔 法攻击数值为Bi，你需要将这些士兵三等分为三个连，第一个连需要去物理空间参加物理对抗战争，战斗力估值W1为士兵的物理攻击数值之 和；第二个连需要去魔法空间参加魔法对抗战争，战斗力估值W2为士兵的魔法攻击数值之和；第三个连需要去虚幻空间参加物理魔法兼备的综 合对抗战争，战斗力估值W3为所有士兵的物理攻击数值、魔法攻击数值之和除以2。你希望W1+W2+W3最大，这样才最有可能胜利。

输入描述:

第一行一个整数n，保证为3的倍数。（3≤n≤100000） 第二行n个整数，第i个数表示Ai。 第三行n个整数，第i个数表示Bi。（1≤Ai, Bi≤1000）

输出描述:

一个小数，表示最大数值和，保留两位小数（四舍五入）。

输入样例:

6

1 7 3 4 5 9

2 3 9 4 3 3

输出样例:

35.00

【解题思路】

设一个人的物理值为A，魔法值为B。

派去一连可得A的贡献，二连可得(A+B)/2，三连可得B。

去一连与去二连相比差了A-(A+B)/2 = (A-B)/2，同理，去二连比去三连也差了(A-B)/2。

这样，可以根据每个人的A-B数值进行排序，较大者去一连，较小者去三连，中间的去二连。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N], id[N], n;
inline bool cmp(int x, int y) {
    return a[x] - b[x] > a[y] - b[y];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 1; i <= n; ++i)
        scanf("%d", b + i);
    for (int i = 1; i <= n; ++i)
        id[i] = i;
    sort(id + 1, id + n + 1, cmp);
    int k = n / 3;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (i <= k) ans += a[id[i]] * 2;
        else if (i <= k * 2) ans += a[id[i]] + b[id[i]];
        else ans += b[id[i]] * 2;
    }
    printf("%.2f\n", ans / 2.0);
    return 0;
}

2、字符串计数

【题目描述】给定一个仅由小写字母组成且长度不超过106的字符串，将首字符移到末尾并记录所得的字符串，不断重复该操作，虽然记录了无限个字符串， 但其中不同字符串的数目却是有限的，那么一共记录了多少个不同的字符串？

输入描述:

输入给定的字符串。

输出描述:

输出记录的不同字符串的数目。

输入样例:

abab

输出样例:

2

【解题思路】

利用kmp算法的next数组，可以求出字符串的最小循环周期T，这就是答案。

也可以将字符串在后面复制一次，用字符串hash和std::map统计。

【参考代码】

#include <bits/stdc++.h>
#define N 1000007
using namespace std;
char s[N];
int nxt[N];
int main() {
    scanf("%s",s);
    int n=strlen(s);
    nxt[0]=-1;
    for(int i=0,j=-1; i<n;)
        if(j==-1 || s[i]==s[j])nxt[++i]=++j;
        else j=nxt[j];
    if(n%(n-nxt[n]))printf("%d",n);
    else printf("%d",n-nxt[n]);
}

3、表兄弟 

【题目描述】每个人的家族关系可以表示成为一棵树，显而易见，家族关系中不会有环的存在。 假设家族关系树中的每条边的权值都为1， 我们称x是y的k祖先，当且仅当在家族关系树中x是y的祖先且x到y的距离是k。 我们称x和y为k表兄弟，当且仅当x和y的k祖先为同一人。 现在给出一个家族关系，共有n个家族成员，因为历史记录的缺失，所有可能并不知道有些人的父亲是谁(最后的结果可能是 若干个树)，给出m个询问，每个询问包含一个x和一个k，请你找出x成员的k表兄弟的数量。

输入描述:

输入第一行是一个整数n(1≤n≤105）表示家族关系树中成员数量。 第二行有n个数，中间用空格隔开，第i个数fi表示i号成员的父亲为fi，如果fi为0，表示不知道i号成员父亲是谁。 第三行包含一个整数m（1≤m≤105） ,表示询问的数量。 接下来有m行，每行有两个正整数x，k，中间用空格隔开，表示询问x成员的k表兄弟有多少个。

输出描述: 

对于每一个询问，输出一个整数，表示x成员的k表兄弟数量，中间用空格隔开。

输入样例: 

10

0 1 2 0 1 5 6 3 3 0

1 0

9 1

5 4

2 2

10 1

8 4

7 1

3 2

5 2

4 2

3 1

输出样例: 

1 0 0 0 0 0 1 0 0 0

【解题思路】

利用倍增法可以在O(logn)的时间内找到u点的k祖先anc。

问题转化为求anc的所有k后代。

可以先求出这个森林的dfs序，然后将同一深度的点存到一个std::vector中。

对于一个祖先anc，在深度为dep[u]的vector中二分查找in[anc]和out[anc]，即可求得所有的k后代，减去u本身就是u的k表兄弟数量。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
vector <int> v[N],d[N];
int n,m,pa[N],par[N][23],h[N],st[N],fi[N],x1,y2,x,y,p,cnt=0;
void dfs(int s) {
    int y;
    st[s]=++cnt;
    d[h[s]].push_back(st[s]);
    for(int i=0; i<v[s].size(); i++) {
        y=v[s][i];
        h[y]=h[s]+1;
        dfs(y);
    }
    fi[s]=cnt;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> pa[i];
        if(pa[i]!=0) {
            v[pa[i]].push_back(i);
            par[i][0]=pa[i];
        } else
            par[i][0]=i;
    }
    cnt=0;
    for(int i=1; i<=n; i++) {
        if(pa[i]==0) {
            h[i]=0;
            dfs(i);
        }
    }
    for(int i=1; i<=20; i++) {
        for(int j=1; j<=n; j++) {
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    cin >> m;
    for(int i=1; i<=m; i++) {
        cin >> x >> p;
        y=x;
        for(int j=20; j>=0; j--)
            if(p & (1<<j))
                y=par[y][j];
        if(h[x]-p<0) {
            cout << 0 << ' ';
            continue;
        }
        x1=st[y];
        y2=fi[y];
        x1=lower_bound(d[h[x]].begin(),d[h[x]].end(),x1)-d[h[x]].begin();
        y2=upper_bound(d[h[x]].begin(),d[h[x]].end(),y2)-d[h[x]].b