小米笔试小米秋招 0906

笔试时间：2025年9月6日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

Alice在家里搭了一个服务器，发现防火墙防护记录猛增。她使用了一个可以对比两次攻击类型是否一致的分析器。现在给出分析器判断哪些攻击之间存在差别，请判断该分析器是否输出了合理的结果。当且仅当对于某三次攻击a,b,c，分析器判断其中某两对攻击类型相同且第三对攻击类型不同，则认为分析器没有输出合理的结果。

输入描述

第一行有一个正整数T(1<=T<=100)，代表测试数据的组数

对于每组测试数据：第一行有两个正整数n,m(1<=n<=200,1<=m<=n*(n-1)/2)，代表攻击次数以及分析器指出的类型存在差别的攻击对的数目

接下来两行每行均有m个正整数，第i列的两个数x,y代表分析器认为第x次攻击和第y次攻击的类型存在差别

输出描述

对于每组测试数据，若分析器输出的结果合理，输出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，则分析器结果不合理。

C++：

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(m), b(m);
        for (int i = 0; i < m; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];
        
        vector<vector<int>> p(n + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            int x = a[i];
            int y = b[i];
            p[x][y] = 1;
            p[y][x] = 1;
        }
        
        bool ans1 = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    if (p[i][j] + p[i][k] + p[j][k] == 1) {
                        ans1 = false;
                    }
                }
            }
        }
        
        cout << (ans1 ? "Yes" : "No") << endl;
    }
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[m];
            int[] b = new int[m];
            
            for (int i = 0; i < m; i++) a[i] = sc.nextInt();
            for (int i = 0; i < m; i++) b[i] = sc.nextInt();
            
            int[][] p = new int[n + 1][n + 1];
            for (int i = 0; i < m; i++) {
                int x = a[i];
                int y = b[i];
                p[x][y] = 1;
                p[y][x] = 1;
            }
            
            boolean ans = true;
            for (int i = 1; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    for (int k = j + 1; k <= n; k++) {
                        if (p[i][j] + p[i][k] + p[j][k] == 1) {
                            ans = false;
                        }
                    }
                }
            }
            
            System.out.println(ans ? "Yes" : "No");
        }
    }
}