✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

小米

题目一：社交网络关系验证系统

1️⃣：将分歧关系建立成无向图，用DFS/BFS找出每个连通块

2️⃣：检查每个连通块是否为完全图，边数应等于k(k-1)/2

3️⃣：所有连通块都是完全图则输出Yes，否则输出No

难度：中等

这道题目的关键在于理解社交关系中的传递性，通过图论将问题转化为连通块完全图检查。如果三个用户中任意两对存在分歧关系，那么第三对也必须存在分歧关系，这样才符合逻辑。通过建图和连通性分析，可以高效地验证关系的合理性。

题目二：数据中心能量优化任务

1️⃣：使用动态规划从终点往起点逆向推导

2️⃣：计算每个位置到达终点所需的最小正能量

3️⃣：状态转移方程：need[i][j] = max(1, min(need[i+1][j], need[i][j+1]) - a[i][j])

难度：中等

这道题目是经典的动态规划路径优化问题，类似于地下城游戏。关键思路是逆向思维，从终点开始计算每个位置需要的最小能量值。通过自底向上的动态规划，避免了正向模拟所有可能路径的复杂性，实现了O(N×M)的高效解法。

01. 社交网络关系验证系统

问题描述

小兰在一家社交媒体公司工作，最近她开发了一套用于验证社交网络中朋友关系的系统。该系统通过分析用户间的互动数据来判断用户之间是否存在分歧或矛盾。

在小兰的系统中，如果两个用户之间存在分歧，系统会将他们标记出来。但是小兰担心系统的逻辑可能存在问题：如果三个用户 、、 中，其中某两对存在分歧而第三对没有分歧，那么这种判断结果就是不合理的。因为在真实的社交关系中，如果 与 有分歧， 与 有分歧，那么 与 之间理论上也应该有分歧才对。

现在请你帮助小兰判断她的系统输出是否合理。

输入格式

第一行包含一个正整数 （），表示测试数据的组数。

对于每组测试数据，包含三行：

第一行包含两个正整数 和 （，），分别表示用户总数以及系统检测到存在分歧的用户对数目。

接下来两行每行均包含 个正整数，第 列的两个数 、 表示系统认为第 号用户和第 号用户之间存在分歧。

输出格式

对于每组测试数据，如果系统输出的结果合理，输出 Yes，否则输出 No。（注意首字母大写）

样例输入

3
4 4
1 1 4 4
2 3 2 3
3 1
1
2
5 8
1 1 2 5 1 3 2 3
2 4 5 4 3 5 3 4

样例输出

Yes
No
Yes

数据范围

题解

这道题的关键是理解什么叫"合理的分歧关系"。

如果我们把所有存在分歧的用户对看作图中的边，那么问题就转化为：对于图中的任意三个节点，如果其中两条边存在，那么第三条边也必须存在。

换句话说，每个连通块内部必须是一个完全图（任意两个节点之间都有边）。

具体分析：

• 假设有三个用户 、、，如果 与 有分歧， 与 有分歧，但 与 没有分歧，那么就违反了传递性
• 在图论中，这相当于在同一个连通块中存在路径 ，但缺少边

解题思路：

1. 将所有分歧关系建立成无向图
2. 用DFS或BFS找出每个连通块
3. 对于每个连通块，检查它是否是完全图
4. 如果连通块有 个节点，完全图应该有 条边
5. 所有连通块都是完全图则输出 Yes，否则输出 No

时间复杂度：，对于 的数据范围完全可以接受。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    n, m = map(int, input().split())
    x_arr = list(map(int, input().split()))
    y_arr = list(map(int, input().split()))
    
    # 建立邻接表
    graph = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v = x_arr[i], y_arr[i]
        graph[u].append(v)
        graph[v].append(u)
    
    visited = [False] * (n + 1)
    
    # 检查每个连通块
    def check_component(start):
        component = []
        stack = [start]
        visited[start] = True
        
        while stack:
            node = stack.pop()
            component.append(node)
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append(neighbor)
        
        # 计算连通块中的边数
        k = len(component)
        edge_count = 0
        for node in component:
            edge_count += len(graph[node])
        edge_count //= 2  # 每条边被计算了两次
        
        # 完全图应有的边数
        expected_edges = k * (k - 1) // 2
        return edge_count == expected_edges
    
    # 检查所有连通块
    for i in range(1, n + 1):
        if not visited[i]:
            if not check_component(i):
                return "No"
    
    return "Yes"

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<int> x(m), y(m);
        for (int i = 0; i < m; i++) cin >> x[i];
        for (int i = 0; i < m; i++) cin >> y[i];
        
        // 建立邻接表
        vector<vector<int>> adj(n + 1);
        for (int i = 0; i < m; i++) {
            adj[x[i]].push_back(y[i]);
            adj[y[i]].push_back(x[i]);
        }
        
        vector<bool> vis(n + 1, false);
        bool is_valid = true;
        
        // 检查每个连通块
        for (int i = 1; i <= n && is_valid; i++) {
            if (!vis[i]) {
                vector<int> comp;
                queue<int> q;
                q.push(i);
                vis[i] = true;
                
                // BFS遍历连通块
                while (!q.empty()) {
                    int u = q.front();
                    q.pop();
                    comp.push_back(u);
                    
                    for (int v : adj[u]) {
                        if (!vis[v]) {
                            vis[v] = true;
                            q.push(v);
                        }
                    }
                }
                
                // 计算边数
                int k = comp.size();
                int edge_cnt = 0;
                for (int u : comp) {
                    edge_cnt += adj[u].size();
                }
                edge_cnt /= 2;  // 每条边计算了两次
                
                // 检查是否为完全图
                int need_edges = k * (k - 1) / 2;
                if (edge_cnt != need_edges) {
                    is_valid = false;
                }
            }
        }
        
        cout << (is_valid ? "Yes" : "No") << "\n";
    }