昨天 11:03 北京理工大学算法工程师发布于江苏

关注

【秋招笔试】09.25华子秋招(已改编)-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

alt

🌈 华子秋招笔试，来啦！！！

🍥 本次的第一题有坑，二三两题倒是比较经典

1️⃣ 粉丝反馈第一题在考试的时候只能拿28分，没过全，但大致是思路是bfs/dfs没跑了，不清楚是不是后台数据出错啦

2️⃣ 数据范围很小直接暴力dfs即可，枚举每个位置放或不放

3️⃣ 非常经典的题了，双向dfs(折半搜索)+二分，但直接暴力dfs也能过不少啦

🪙 01.社交网络影响力计算评测链接🔗

问题描述

在一个社交网络中，用户之间存在着各种社交连接。我们可以将社交网络看作一个无向图，其中节点表示用户，边表示用户之间的社交连接。两个用户之间最多只有一条直接相连的边。

定义用户的影响力为：从该用户开始，在 $K$ 跳（包括直接和间接关系）内可以接触到的其他用户的总数。

现在给定一个社交网络，请你计算指定用户在 $K$ 跳范围内的影响力。

输入格式

第一行包含三个正整数 $N$ 、 $M$ 、 $K$ ，分别表示社交网络中的连接总数、需要计算影响力的用户编号和计算影响力的跳数范围。其中 $1 \leq N, K \leq 1000$ ， $0 \leq M < 1000$ 。

接下来的 $N$ 行，每行包含两个整数 $X$ 和 $Y$ （ $0 \leq X, Y \leq 1000$ ），表示社交网络中的一条直接连接，即用户 $X$ 和用户 $Y$ 之间存在直接连接。

输入数据保证合法，无需进行额外校验。

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

$1 \leq N, K \leq 1000$
$0 \leq M < 1000$
$0 \leq X, Y \leq 1000$

题解

BFS/DFS

从指定的用户 $M$ 开始进行 BFS，同时记录已访问过的节点数量。当访问到距离用户 $M$ 超过 $K$ 跳的节点时，就可以停止遍历，因为再继续遍历也不会增加 $K$ 跳范围内的影响力值。

最终，已访问过的节点数量就是用户 $M$ 在 $K$ 跳范围内的影响力值。

Python

from collections import deque

def calculate_influence(n, m, k, connections):
    # 构建邻接表表示的无向图
    graph = [[] for _ in range(n)]
    for x, y in connections:
        graph[x].append(y)
        graph[y].append(x)
    
    # 初始化队列和访问标记数组
    queue = deque([(m, 0)])  # (用户编号, 跳数)
    visited = [False] * n
    visited[m] = True
    influence = 0
    
    # 执行 BFS 遍历
    while queue:
        user, depth = queue.popleft()
        influence += 1
        if depth == k:
            continue
        for neighbor in graph[user]:
            if not visited[neighbor]:
                queue.append((neighbor, depth + 1))
                visited[neighbor] = True
    
    return influence - 1

# 读取输入
n, m, k = map(int, input().split())
connections = [tuple(map(int, input().split())) for _ in range(n)]

# 计算影响力并输出结果
print(calculate_influence(1000, m, k, connections))

Java

import java.util.*;

public class Solution {
    public static int calculateInfluence(int n, int m, int k, int[][] connections) {
        // 构建邻接表表示的无向图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : connections) {
            int x = edge[0], y = edge[1];
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        
        // 初始化队列和访问标记数组
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{m, 0});  // (用户编号, 跳数)
        boolean[] visited = new boolean[n];
        visited[m] = true;
        int influence = 0;
        
        // 执行 BFS 遍历
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int user = node[0], depth = node[1];
            influence++;
            if (depth == k) {
                continue;
            }
            for (int neighbor : graph.get(user)) {
                if (!visited[neighbor]) {
                    queue.offer(new int[]{neighbor, depth + 1});
                    visited[neighbor] = true;
                }
            }
        }
        
        return influence - 1;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int[][] connections = new int[n][2];
        for (int i = 0; i < n; i++) {
            connections[i][0] = scanner.nextInt();
            connections[i][1] = scanner.nextInt();
        }
        scanner.close();
        
        // 计算影响力并输出结果
        System.out.println(calculateInfluence(1000, m, k, connections));
    }
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int calculateInfluence(int n, int m, int k, const vector<pair<int, int>>& connections) {
    // 构建邻接表表示的无向图
    vector<vector<int>> graph(n);
    for (const auto& edge : connections) {
        int x = edge.first, y = edge.second;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    // 初始化队列和访问标记数组
    queue<pair<int, int>> q;
    q.emplace(m, 0);  // (用户编号, 跳数)
    vector<bool> visited(n, false);
    visited[m] = true;
    int influence = 0;
    
    // 执行 BFS 遍历
    while (!q.empty()) {
        auto [user, depth] = q.front();
        q.pop();
        influence++;
        if (depth == k) {
            continue;
        }
        for (int neighbor : graph[user]) {
            if (!visited[neighbor]) {
                q.emplace(neighbor, depth + 1);
                visited[neighbor] = true;
            }
        }
    }
    
    return influence - 1;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> connections(n);
    for (auto& edge : connections) {
        cin >> edge.first >> edge.second;
    }
    
    // 计算影响力并输出结果
    cout << calculateInfluence(1000, m, k, connections) << endl;
    
    return 0;
}

♦️ 02.方块放置游戏评测链接🔗

问题描述

K小姐最近迷上了一款名为"方块放置"的游戏。游戏中有一个 $n \times n$ 的正方形网格,玩家需要在网格中放置由四个正方形小方块组成的大方块。游戏规则如下:

方块不能重叠。
方块不能超出网格的边界。
网格中部分位置不能放置方块。

现在,K小姐想知道在给定网格大小和不可放置方块的位置的情况下,最多可以放置多少个大方块。

输入格式

第一行包含两个正整数 $n$ 和 $k$ ,表示网格的边长和不可放置方块的位置数量。

接下来 $k$ 行,每行包含两个正整数 $y_i$ 和 $x_i$ ,表示第 $i$ 个不可放置方块的位置的行号和列号。行号和列号都从 $0$ 开始编号,左上角的位置为 $(0, 0)$ 。

输出格式

输出一个整数,表示最多可以放置的大方块数量。

样例输入1

2 0

样例输出1

样例输入2

样例输出2

样例输入3

样例输出3

数据范围

$1 \leq n \leq 8$
$0 \leq k \leq 64$
$0 \leq y_i, x_i < n$

题解

DFS

这题其实挺经典的，是在网格上回溯的问题，比如和经典的 n皇后问题 的写法和核心思路其实差不多的

我们可以从网格的左上角开始，尝试在每个位置放置大方块。对于每个位置，检查是否能放置大方块。

如果可以，就填入继续搜索下一个位置，或者不填继续搜索下一个位置。
如果不可以，就跳过这个位置，继续搜索下一个位置。

参考代码

Python

def main():
    # 读取网格大小 n 和不可放置方块的位置数量 k
    n, k = map(int, input().split())
    
    # 创建两个 n*n 的二维数组,用于记录网格状态和不可放置的位置
    st = [[0] * n for _ in range(n)]
    g = [[0] * n for _ in range(n)]
    
    # 如果网格大小为 1,直接输出 0 并返回
    if n == 1:
        print(0)
        return
    
    # 读取不可放置方块的位置,并将其标记为 1
    for _ in range(k):
        x, y = map(int, input().split())
        g[x][y] = 1
    
    # 记录最多可以放置的大方块数量
    res = 0
    
    # 定义 DFS 搜索函数
    def dfs(x, y, cnt):
        nonlocal res
        # 更新最多可以放置的大方块数量
        res = max(res, cnt)
        
        # 如果当前位置是最后一列,就移动到下一行的第一列
        if y == n - 1:
            x += 1
            y = 0
            # 如果已经到达最后一行,就返回
            if x == n - 1:
                return
        
        # 检查当前位置是否能放置大方块
        flg = True
        for i in range(2):
            for j in range(2):
                v = st[i + x][j + y] | g[i + x][j + y]
                if v == 1:
                    flg = False
        
        # 如果可以放置大方块,就放置大方块,然后继续搜索下一个位置
        if flg:
            for i in range(2):
                for j in range(2):
                    st[i + x][j + y] = 1
            df

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

互联网春秋招笔试题汇总文章被收录于专栏

这里收集了超全的互联网春秋招笔试题，欢迎大家的订阅，会持续跟新的