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

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

第一题

题目

小红有一个长度为n的字符串s，由0、1和 * 组成，可以把*替换成0或者1，小红想知道替换后的字符串的最短周期是多少。如果一个字符串每一个位置的字母都与后k位的字母相同，那么k即为该字符串的一个周期。形式化的说，如果存在一个正整数k 使得对于所有的 i属于[1,n - k] 都有 s[i]= s[i+k] ，那么称k是字符串s的周期。

输入描述

第一行输入一个长度为n(1<=n<=1e3)，且只由0、1和*组成的字符串s。

输出描述

在一行上输出一个整数，表示替换后的字符串的最短周期。

样例输入

1*011*0*1

样例输出

4

说明

一共有六种替换方式，其中 100110011拥有最短周期。

参考题解

从1-n枚举周期，对于每一个周期k，将字符串分成多个k长度的部分，检查每一部分在相同位置上的字符是否可以相同。如果k可以作为周期，则记录最小的周期。

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

#include <iostream>
#include <vector>
#include <set>
#include <string>

int get(const std::string& s) {
    int n = s.length();
    int ans = 0;
    
    for (int i = 1; i <= n; i++) {
        bool f = true;
        std::vector<std::set<char>> g(i + 1);
        
        for (int j = 0; j < n; j++) {
            if (s[j] == '*') {
                continue;
            }
            g[j % i].insert(s[j]);
        }
        
        for (int j = 0; j < i; j++) {
            if (g[j].size() >= 2) {
                f = false;
            }
        }
        
        if (f) {
            ans = i;
            break;
        }
    }
    
    return ans;
}

int main() {
    std::string s;
    std::cin >> s;
    int result = get(s);
    std::cout << result << std::endl;
    return 0;
}

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

import java.util.*;

public class Main {
    public static int get(String s) {
        int n = s.length();
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            boolean f = true;
            List<Set<Character>> g = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                g.add(new HashSet<>());
            }
            
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == '*') {
                    continue;
                }
                g.get(j % i).add(s.charAt(j));
            }
            
            for (int j = 0; j < i; j++) {
                if (g.get(j).size() >= 2) {
                    f = false;
                }
            }
            
            if (f) {
                ans = i;
                break;
            }
        }
        
        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int result = get(s);
        System.out.println(result);
    }
}

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

def get(s):
    n = len(s)
    ans = 0
    
    for i in range(1, n + 1):
        f = True
        g = [set() for _ in range(i + 1)]
        
        for j in range(n):
            if s[j] == '*':
                continue
            g[j % i].add(s[j])
        
        for j in range(i):
            if len(g[j]) >= 2:
                f = False
        
        if f:
            ans = i
            break
    
    return ans
s = input().strip()
result = get(s)
print(result)

第二题

题目

二维平面上有几 个整点 a[1],a[2],·..,a[n]，其中第个点的坐标为(i,a[i])。小苯想知道有多少个点对“,j满足第i个点和第j个点的连线所在的直线恰好经过原点，请你帮他算一算吧。

输入描述

第一行输入一个正整数n(2 <= n < =2e5)代表整点数量。

第二行输入n个正整数 a[1],a[2],·..,a[n]](1 <= a[i]< 1e9)代表整点的纵坐标。

输出描述

在一行上输出一个正整数，表示连线所在直线经过原点的点对个数。

样例输入

5

1 2 4 4 5

样例输出

6

参考题解

对于任意两个点(i, a[i])和(j, a[j])，若连线经过原点，则它们的斜率必须相同。斜率可以表示为a[i] / i。为了避免浮点数的精度问题，可以将斜率表示为一个最简分数 (a[i] / gcd(i, a[i]), i / gcd(i, a[i]))。

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

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <numeric> // for gcd

using namespace std;

int get(int n, const vector<int>& a) {
    map<pair<int, int>, int> ma;
    int ans = 0;
    
    for (int i = 1; i <= n; i++) {
        int d = gcd(i, a[i-1]);
        pair<int, int> slope = make_pair(i / d, a[i-1] / d);
        ans += ma[slope];
        ma[slope]++;
    }
    
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int result = get(n, a);
    cout << result << endl;
    return 0;
}

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

import java.util.*;
import java.math.BigInteger;

public class Main {
    public static int get(int n, int[] a) {
        Map<Pair<Integer, Integer>, Integer> ma = new HashMap<>();
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            int d = gcd(i, a[i-1]);
            Pair<Integer, Integer> slope = new Pair<>(i / d, a[i-1] / d);
            ans += ma.getOrDefault(slope, 0);
            ma.put(slope, ma.getOrDefault(slope, 0) + 1);
        }
        
        return ans;
    }
    
    public static int gcd(int a, int b) {
        return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int result = get(n, a);
        System.out.println(result);
    }
    
    static class Pair<U, V> {
        public final U first;
        public final V second;
        
        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }

        @Override
        public int