雪豹的数

签到题

直接开始猜，第一个除 $3$ 余数是 $2$ 的数是 $5$，而 $5$ 恰好又满足第二个条件，所以这个数就是 $5$。

直接计算结果打印即可

---

最大乘积

高精度，动态规划

这题的第一个考点是，如何分解自然数，使其分解的数乘积最大

这里我们从对数的角度去想，有 $\ln{a} + \ln{b} = \ln{a \times b}$

也就是说，要想让 $a \times b$ 最大，我们只要保证其对数和最大就可以了，那么接下来就是一个简单的 $01$ 背包了

第二个考点是高精度乘法的实现，数据范围较小，我们可以采用高精乘低精的实现，比较简单

一个简单的solve实现

using Int = BigInt;
auto solve() {
    int64_t n;
    cin >> n;
    vector dp(n + 1, 0.0);
    vector flag(n + 1, 0ll);
    for (auto i = 0ll; i <= n; ++i)
        for (auto j = n; j >= i; --j) {
            if (const auto v = dp[j - i] + log10(i); v > dp[j]) {
                dp[j] = v;
                flag[j] = j - i;
            }
        }
  // 这里我是用dfs来实现打印而已，写循环也可以
    function<Int(int64_t)> dfs = [&](const int64_t &x) -> Int {
        if (x == 0)
            return 1;
        const auto tmp = x - flag[x];
        const auto res = dfs(flag[x]);
        cout << tmp << ' ';
        return res * tmp;
    };
    const auto result = dfs(n);
    cout << endl << result;
}

---

小冀拼数

排序

这道题其实就是考查对字典序的理解。 拼接根据拼接两个字符串的结果进行排序即可得出答案

需要注意的是，你应该使用 s2 + s1 < s1 + s2 来作为比较依据，这样才是最准确的方案

例如以下 hack 数据

10
100

直接默认从大到小排序的结果是

100
10

明显结果不是最优，拼接的结果是 10010

按照 s2 + s1 < s1 + s2 来作为比较依据，排序结果为

10
100

结果最优，拼接的结果为 10100

一个简单的solve实现

auto solve() {
    int64_t n;
    cin >> n;
    vector<string> lst(n);
    for(auto &&i : lst)
        cin >> i;
    sort(lst.begin(), lst.end(), [&](const string &s1, const string &s2){
        return s2 + s1 < s1 + s2;
    });
    for(const auto &i : lst)
        cout << i;
}

---

不同的子串

字符串哈希

这道题容易想到的就是直接利用 substring 或者字符串切片来进行比较，但是 substring 会爆空间，在哈希函数实现较慢的情况下切片也会爆时间

为此，我们应该考虑手动实现 rolling hash。将每次查询的结果存入一个 HashSet 中，最后set的长度就是答案

代码就不用 C++ 重写了，理解上面给的思路就行

rust代码实现

fn solve(scan: &mut Scanner) {
    let n = scan.next_usize().unwrap();
    let m = scan.next_usize().unwrap();
    let s: Vec<u8> = scan.next_line().unwrap().chars().map(|c| c as u8).collect();
    const PRIME: usize = 233;
    let mut hash = vec![0usize; n + 1];
    let mut primes = vec![1usize; n + 1];
    for i in 0..n {
        hash[i + 1] = hash[i].wrapping_mul(PRIME).wrapping_add(s[i] as usize);
        primes[i + 1] = primes[i].wrapping_mul(PRIME);
    }
    let get = |l: usize, r: usize| { hash[r].wrapping_sub(hash[l - 1].wrapping_mul(primes[r - l + 1])) };
    let mut set = HashSet::new();
    for _ in 0..m {
        let l = scan.next_usize().unwrap();
        let r = scan.next_usize().unwrap();
        set.insert(get(l, r));
    }
    println!("{}", set.len());
}

补上一个能过此题，但是不算正解的解法

直接对求出来的切片进行哈希。切片可以节约空间，防止MLE，但是这样实现的性能相对较低

auto solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    hash<string_view> hasher;
    unordered_set<size_t> hashSet;
    while(m--) {
        int l, r;
        cin >> l >> r;
        hashSet.emplace(hasher(string_view(s.data() + l - 1, r - l + 1)));
    }
    println("{}", hashSet.size());
}

---

“雪冀”互卷

字符串哈希

要求 $T$ 的循环同构，其实就是在求两个 $T$ 拼接在一块后，长度为 $|T|$ 的子串

我们先利用 rolling hash 处理并用 HashSet 储存下 $T$ 的循环同构，随后对于每次给出的查询串

我们只需要查询长度为 $|T|$ 的同构存在不存在就行了，查询的过程也可以是对查询串跑一遍 rolling hash

随后直接直接查询哈希的结果在 HashSet 中是否存在

这个的代码也不用 C++ 重写了，理解上面给的思路就行

rust代码实现

use std::collections::HashSet;
use std::io::{Read, stdin};
const PRIME: usize = 233;
fn setup_hash(string: String) -> (Vec<usize>, Vec<usize>) {
    let string = string.chars().map(|c| c as u8).collect::<Vec<u8>>();
    let mut hash = vec![0usize; string.len() + 1];
    let mut primes = vec![1usize; string.len() + 1];
    for i in 0..string.len() {
        hash[i + 1] = hash[i].wrapping_mul(PRIME).wrapping_add(string[i] as usize);
        primes[i + 1] = primes[i].wrapping_mul(PRIME);
    }
    return (hash, primes);
}

fn get_hash(l: usize, r: usize, (hash, primes): &(Vec<usize>, Vec<usize>)) -> usize {
    hash[r].wrapping_sub(hash[l - 1].wrapping_mul(primes[r - l + 1]))
}
fn solve(scan: &mut Scanner) {
    let s = scan.next_line().unwrap().repeat(2);
    let len = s.len() >> 1;
    let hash_tools = setup_hash(s);
    let mut set = HashSet::new();
    for i in 1..=len + 1 {
        set.insert(get_hash(i, i + len - 1, &hash_tools));
    }
    let mut answer = 0;
    for _ in 0..scan.next_line().unwrap().parse().unwrap() {
        let p = scan.next_line().unwrap();
        let p_len = p.len();
        let p_hash_tools = setup_hash(p);
        let mut tmp = 0;
        for i in 1..=p_len - len + 1 {
            if set.contains(&get_hash(i, i + len - 1, &p_hash_tools)) {
                tmp += 1;
            }
            answer = answer.max(tmp);
        }
    }
    println!("{}", answer);
}

---

题外话

• 你要是想用 Set, Map之类的东西也都可以，只要能过就行