笔试时间：2024年09月25日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目：社交用户影响力计算

社交网络拓扑图中的节点表示社交网络中的用户，边表示两个用户之间的社交连接，边是无向的，两个用户最多只有一条直接相连的边。用户的影响力定义为:从某个社交网络用户开始，找出所有可以在K跳(直接或间接关系)内接触到的其他用户的总个数。请实现一个程序，计算给定社交网络中某个用户在k跳范围内的影响力。

解答要求：时间限制: C/C++1000ms,其他语言:2000ms内存限制: C/C++256MB,其他语言:512MB。

输入描述

第一行输入N MK(三个空格分隔的正整数):N代表社交网络连接总数，M代表需要计算影响力的用户编号，K代表计算影响力的范围。

1<=N,K<=1000，0<=M<1000

接下来的N行，每行两个整数X Y(0<=X,Y<=1000)，代表社交网络中一条直接连接的边，如”12“代表1号与2号用户互相直接连接。

用例确保输入有效，无需进行校验。

输出描述

输出M用户在K跳范围内的影响力。

样例输入一

5 0 2

0 1

1 2

2 3

3 4

4 0

样例输出一

4

样例输入二

8 0 3

0 1

0 2

0 3

3 4

2 5

5 4

2 3

1 5

样例输出二

5

参考题解

图论的遍历。使用dfs、bfs进行遍历，遍历的过程中记录下当前的步长，当步长超过了k则退出。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>

using namespace std;

vector<int> G[1010];
int ans = 0;

void dfs(int u, vector<bool>& vst, int stp, int K) {
    if (vst[u] || stp > K) return;
    vst[u] = true;
    ans++;
    for (int next : G[u]) {
        dfs(next, vst, stp + 1, K);
    }
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    vector<bool> vst(1010, false);
    dfs(M, vst, 0, K);

    cout << ans - 1 << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<Integer>[] G = new ArrayList[1010];
    static int ans = 0;

    static void dfs(int u, boolean[] vst, int stp, int K) {
        if (vst[u] || stp > K) return;
        vst[u] = true;
        ans++;
        for (int next : G[u]) {
            dfs(next, vst, stp + 1, K);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();

        for (int i = 0; i < 1010; i++) {
            G[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            G[x].add(y);
            G[y].add(x);
        }

        boolean[] vst = new boolean[1010];
        dfs(M, vst, 0, K);

        System.out.println(ans - 1);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

N,M,K = map(int, input().split())
G = [[] for _ in range(1010)]

for _ in range(N):
    x,y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
ans = 0
def dfs(u,vst,stp):
    if vst[u] or stp > K: return
    vst[u] = True
    global ans
    ans += 1
    for next in G[u]:
        dfs(next, vst, stp + 1)

dfs(M,[False]*(1010), 0)

print(ans-1)

第二题

题目：俄罗斯方块

在俄罗斯方块游戏中，只看下面1种大方块，由四个正方形小方块组成。现在，请计算在给定网格大小的情况下，最多可以放置多少个大方块。夏泳规则如下:1、网格为正芳形网络2、方块不能重香。3、方块不能超出网格的边界。4、网格中部分位置不能放罟方块。

解答要求：时间限制:C/C++1000ms 其他语言:2000ms，内存限制: C/C++256MB,基他语言:512MB

输入描述

n k

y1 x1

y2 x2

表示边长为n的正方形网格，有k个位置不能放置方块，接下来k行坐标对，y表示自上向下的第几行，x表示自左向右的第几列(坐标从0开始编号，左上角为00)。

n的范围:[1,8]

k的范围:[0,64]x、y的范围:[0,n)

输出描述

最多能放下多少大方块。

样例输入

2 0

样例输出

1

说明：只能放下1个

参考题解

回溯。dfs(x,y)函数表示从(x,y)出发，检查(x,y),(x+1,y),(x,y+1),(x+1,y+1)是否都为空，如果是则可以尝试去枚举。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k;
vector<vector<int>> grid(1010, vector<int>(1010, 0));
int ans = 0;

pair<int, int> cal(int x, int y) {
    if (y == n - 1) return {x + 1, 0};
    return {x, y + 1};
}

void dfs(int x, int y, int cnt) {
    if (x == n - 1) return;
    ans = max(ans, cnt);
    auto [nx, ny] = cal(x, y);
    dfs(nx, ny, cnt);
    if (x < n - 1 && y < n - 1) {
        if (grid[x][y] == 0 && grid[x + 1][y] == 0 && 
            grid[x][y + 1] == 0 && grid[x + 1][y + 1] == 0) {
            grid[x][y] = 1;
            grid[x + 1][y] = 1;
            grid[x][y + 1] = 1;
            grid[x + 1][y + 1] = 1;
            dfs(nx, ny, cnt + 1);
            grid[x][y] = 0;
            grid[x + 1][y] = 0;
            grid[x][y + 1] = 0;
            grid[x + 1][y + 1] = 0;
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        grid[x][y]