笔试时间：2025年8月31日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：每日一题

这天，小红薯在小红书上看到了一道每日一题之编程题，如下：

定义一个字符串是包裹字符串为：字符串的首字母等于最后一个字母。求解一个字符串的全部子串中，有多少个不是包裹字符串。

刚好，这两天小红薯正在学习字符串相关的知识，字符串的使用非常广泛，所以要认真的学习。

小红薯在评论区看到了这个问题的进阶版：对于给定的字符串

s = s₁s₂…sₙ

对于每一个前缀[¹]依次求解，它的全部非空子串[²]中有多少个不是包裹字符串。

小红薯觉得这个题目很有趣，所以她决定写一个程序，来解决这个问题。

输入描述

第一行输入一个整数n，表示字符串长度。

1 ≤ n ≤ 2×10⁵

第二行输入一个长度为n，由小写字母组成的字符串s。

输出描述

一共n行，第i行输出一个整数，表示原字符串的前缀子串[1,i]的全部子串中，不为包裹字符串的数量。

样例输入

4

abda

样例输出

0

1

3

5

样例解释：对于前缀子串[1,3]，即"abd"，它的全部子串为：

"a"，"b"，"d"，"ab"，"bd"，"abd"

其中，前三个为包裹字符串，后三个不是。

参考题解

对于每个前缀，我们需要统计其所有子串中不是包裹字符串的数量。每个前缀的所有子串总共有k(k+1)/2个，其中k为前缀的长度。我们通过判断哪些子串是包裹字符串来推算哪些不是。

1. 计算所有子串的总数：对于前缀的长度为i的字符串，所有的子串个数为i(i+1)/2。因此，我们先计算所有子串的总数。

2. 判断包裹字符串的个数：包裹字符串是指字符串的首字母等于最后一个字母。我们需要通过遍历每个前缀，统计哪些字符在这个前缀中出现的次数。每当遇到相同的字符时，这些字符可以作为包裹字符串的开头和结尾。

3. 具体实现：我们使用一个数组cnt来记录当前字符在前缀中出现的次数。当我们遍历字符串时，每次遇到一个字符，都统计这个字符之前的出现次数。这个出现次数决定了当前字符可以形成多少个包裹字符串。 每当处理完一个前缀时，输出当前前缀所有子串中非包裹字符串的数量。

C++：

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

using namespace std;

void work() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    vector<int> cnt(26, 0);
    int w = 0;
    int i = 0;
    
    while (i < n) {
        int k = i + 1;
        int j = s[i] - 'a';
        cnt[j]++;
        w += cnt[j];
        int t = k * (k + 1) / 2;
        cout << t - w << endl;
        i++;
    }
}

int main() {
    work();
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void work() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        
        int[] cnt = new int[26];
        int w = 0;
        int i = 0;
        
        while (i < n) {
            int k = i + 1;
            int j = s.charAt(i) - 'a';
            cnt[j]++;
            w += cnt[j];
            int t = k * (k + 1) / 2;
            System.out.println(t - w);
            i++;
        }
        
        scanner.close();
    }
    
    public static void main(String[] args) {
        work();
    }
}

Python：

import sys

def work():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    cnt = [0]*26
    w = 0
    i = 0
    while i < n:
        k = i+1
        j = ord(s[i]) - 97
        cnt[j] += 1
        w += cnt[j]
        t = k*(k+1)//2
        print(t - w)
        i += 1

if __name__ == "__main__":
    work()

第二题：小红书丝带AR特效

在小红书“品牌创意工坊”中，营销人员可以为直播和短视频活动创建定制化丝带AR特效，结合品牌ID与礼盒包装场景，实现动态丝带动画。为了支撑亿级日活的前端渲染，后端需要在活动发布时预先计算并缓存所有可能的切割方案数，确保小程序组件和Web端秒级响应。

现有一根虚拟丝带长度为k，可以将其分割成若干段或保持一整段不动，但是每段长度只能取整数a、b或c中的一个，且不允许任何长度为a的段后面直接跟随长度为c的段。

请对所有长度k（1 ≤ k ≤ n），统计合法的切割方案数，供小红书前端组件批量加载与渲染。由于答案可能很大，请将答案对（10⁹ + 7）取模后输出。顺序不同视为不同方案。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T（1 ≤ T ≤ 10⁴）代表数据组数。

每组测试数据描述如下：

在一行上输入四个整数n、a、b、c（1 ≤ n,a,b,c ≤ 10⁶），代表最大丝带长度、可选分段长度a、b、c。保证a、b、c两两互不相等。

除此之外，保证单个测试文件的n之和不超过10⁶。

输出描述

对于每组测试数据，新起一行，输出n个整数，其中第k个数表示长度为k的丝带的合法分割方案数对（10⁹ + 7）取模的结果。

样例输入

2

5 1 2 3

4 1 2 3

样例输出

1 2 4 6 11

1 2 4 6

参考题解

C++：

#include <iostream>
#include <vector>

using namespace std;

const int M = 1000000007;

void work() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        if (i >= a) {
            dp[i] = (dp[i] + dp[i - a]) % M;
        }
        if (i >= b) {
            dp[i] = (dp[i] + dp[i - b]) % M;
        }
        if (i >= c) {
            long long total = dp[i - c];
            long long end_a = (i - c >= a) ? dp[i - c - a] : 0;
            long long valid = (total - end_a + M) % M;
            dp[i] = (dp[i] + valid) % M;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << dp[i];
        if (i < n) cout << " ";
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        work();
    }
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    static final int M = 1000000007;
    
    public static void work(Scanner scanner) {
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        
        long[] dp = new long[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            if (i >= a) {
                dp[i] = (dp[i] + dp[i - a]) % M;
            }
            if (i >= b) {
                dp[i] = (dp[i] + dp[i - b]) % M;
            }
            if (i >= c) {
                long total = dp[i - c];
                long end_a = (i - c >= a) ? dp[i - c - a] : 0;
                long valid = (total - end_a + M) % M;
                dp[i] = (dp[i] + valid) % M;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(dp[i]);
            if (i < n) sb.append(" ");
        }
        System.out.println(sb.toString());
    }
    
    public static void main(S