8.13 贝壳笔试统计+AK参考代码

vector<long long> solve(int n, long long m) {
    // [0, n-1]，从 1 的位置开始洒，最后 a[0] 加 1,最后洒到的位置减去 1
    long long div = m / (n - 1), mod = m % (n - 1);
    vector<long long> ans(n);
    for (int i = 1; i < n; ++i) {
        ans[i] = (div + 1) / 2;
    }
    for (int i = n - 2; i >= 0; --i) {
        ans[i] = div / 2;
    }
    int last = 0;
    if (div & 1) {
        if (mod == 0) {
            last = n - 1;
        } else {
            for (int i = n - 2; i >= 0 && mod; --i, --mod) {
                ans[i] += 1;
                last = i;
            }
        }
    } else {
        if (mod == 0) {
            last = 0;
        } else {
            for (int i = 1; i < n && mod; ++i, --mod) {
                ans[i] += 1;
                last = i;
            }
        }
    }
    ans[0] += 1;
    ans[last] -= 1;
    return ans;
}

第二题

string solve(string s, int k) {
    // 每次删除 s 中最小的字符，共删除 k 次
    // 笔试时我直接用的 set 做的，但是用位运算更优
    int mask = 0;
    for (char c : s) {
        mask |= 1 << (c - 'a');
    }
    for (int i = 0; i < 26 && k; ++i) {
        if (mask & (1 << i)) {
            mask &= ~(1 << i);
            k -= 1;
        }
    }
    string ans;
    for (char c : s) {
        if (mask & (1 << (c - 'a'))) {
            ans += c;
        }
    }
    return ans;
}

第三题

long long solve(vector<int> &a, int t) {
    int n = a.size();
    long long ans = 0;
    unordered_map<int, int> index;
    int pre = 0;
    for (int i = 0; i < n; ++i) {
        int b = a[i] ^ t;
        int k = index.count(b) ? index[b] + 1 : 0;
        k = max(k, pre);
        pre = k;
        ans += i - k;
        index[a[i]] = i;
    }
    return ans;
}

第四题

import sys
from collections import defaultdict

sys.setrecursionlimit(100005)


def solve(root):
    pattern = defaultdict(int)
    size = defaultdict(int)

    def dfs(root):
        if root is None:
            return ("()", 0)
        l_s, l_cnt = dfs(root.left)
        r_s, r_cnt = dfs(root.right)
        s = "(" + l_s + str(root.val) + r_s + ")"
        cnt = 1 + l_cnt + r_cnt
        pattern[s] += 1
        size[s] = cnt
        return (s, cnt)

    dfs(root)
    ans = 0
    for k, v in pattern.items():
        if v > 1:
            ans = max(ans, size[k])
    return ans