深信服笔试深信服笔试题 0316

笔试时间：2025年03月16日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

毒入侵往往从内网开始，企业为了防范内部违规接入非企业的设备，需要对违规接入企业的设备进行发现，这其中就包括违规接入的NAT设备。NAT设备也叫共享上网设备，它对外表现为只有一个IP地址，而内部可以接入很多个物理设备。典型的家庭拨号上网场景，拨号之后路由器对外使用统一IP，而内部接入的多个设备则使用内网私有IP。为了检测企业内部是否接入NAT设备，深信服同事研究发现，虽然经过NAT后设备只有一个IP地址，但它们还有一些可以识别内部物理设备的独特指纹存在，可以根据统计某个IP下一段时间独特指纹的数量来判断设备是否为NAT设备。独特的指纹我们统一使用A、B、C、D等来表示。同一个IP下的指纹序列存在以下示例。AAAAAAAAAAAA

如上，IP一直只有一个指纹A，则输出终端数量1。

AAAAAABBBBBB

如上，考虑DHCP场景。A设备释放IP之后正好被B设备使用，表现为这个IP下原来全是A的指纹，后面切换全是B的指纹，则输出终端数量依旧日为1。

AAAAAABBBBBBBCCCCCCCC

如上，按照上面的解释，DHCP场景，一个IP下的指纹从 A切换为B再切换为C，输出的终端数量依旧日为1。AAABBBAAAAAAAA

如上，A指纹后是B再是A，分了提升检测的可靠性，需要检测某类指纹是否交替出现，此例中A指纹交替1次，而B指纹仅出现1次没有交替，则认为只有1个可信终端A。

АААВВССАССССВВА

如上，A指纹在一段时间内交替出现2次。B指纹也交替出现1次，C指纹也交替出现1次，则认为A、B、C三个终端在同一时间内共同使用，输出的终端数量为3。

现存在交替次数n（n表示终端指纹至少交替多少次才算1个可信终端，比如上面的例子中交替1次即算1个可信终端，也可以是2或者3），m组某个iP特定时间段内的指纹序列，请输出每组指纹对应的可信终端数量是多少？

输入描述

第一行输入两个正整数n，m(1 <= n <= 4, 1 <= m <= 1000)，其中n表示终端指纹至少

需要交替多少次才可算作1个可信终端，接下来m行，每行输入某个IP的一组指纹序列。指纹序列的格式如下

AAAAAAA

AAABBBCCCDDD

ABBACCBDDA

输出描述

对于每一个指纹序列，输出其可信终端数量。

样例输入

38

DDDDD

XXXXXYYYY

EFFFFQ

BFFFFFFFFBBBFBFFBB

CDDAAAADDCADDDCC

CCDAADDDACCCCDDAAADCDDAAA

EEEQQQBBBQQQEEEBEQBBEEQOBBBB

EEBBAAGGEEBBAAGGEEBBAAGGEBAQ

样例输出

1

1

1

1

1

2

3

4

参考题解

根据题目的意思，一段连续的字符就算作某个主机的一次活动，如果某个主机交替了k次，那么这台主机连续的活动段数应该为（k+1），因此，使用一个哈希表记录每个主机（其实就是每个字符）的连续的段数，最后判断一下即可。注意肯定会有一台，因此ans = max(1, ans)。

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

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        unordered_map<char, int> cnt;
        int ans = 0;
        int len = s.size();
        for (int i = 0; i < len; ) {
            int j = i;
            while (j < len && s[j] == s[i]) {
                j++;
            }
            cnt[s[i]]++;
            i = j;
        }
        for (auto [k, v] : cnt) {
            if (v - 1 >= n) {
                ans++;
            }
        }
        ans = max(1, ans);
        cout << ans << "\n";
    }
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 阈值
        int m = scanner.nextInt();  // 测试字符串数量
        scanner.nextLine(); // 吃掉换行符

        for (int t = 0; t < m; t++) {
            String s = scanner.nextLine();
            Map<Character, Integer> cnt = new HashMap<>();
            int i = 0;
            int len = s.length();

            while (i < len) {
                int j = i;
                while (j < len && s.charAt(j) == s.charAt(i)) {
                    j++;
                }
                cnt.put(s.charAt(i), cnt.getOrDefault(s.charAt(i), 0) + 1);
                i = j;
            }

            int ans = 0;
            for (Map.Entry<Character, Integer> entry : cnt.entrySet()) {
                if (entry.getValue() - 1 >= n) {
                    ans++;
                }
            }
            System.out.println(Math.max(1, ans));
        }
    }
}

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

n, m = map(int, input().split())

for _ in range(m):
    s = input()
    cnt = {}
    i = 0
    length = len(s)

    while i < length:
        j = i
        while j < length and s[j] == s[i]:
            j += 1
        cnt[s[i]] = cnt.get(s[i], 0) + 1
        i = j

    ans = sum(1 for v in cnt.values() if v - 1 >= n)
    print(max(1, ans))