百度2023秋招研发A卷（10月11日）

第一题

暴力即可，注意需要判断字符串长度是否为5

第二题

map存 数字 -> 出现次数
滑动窗口，限制窗口内元素总和不大于k，等于k则为一个答案
注意有元素出窗口时不能只-1，需要减去该元素出现次数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 10010;

map<int, int> s;
int n, k;

int q[N], hh = 0, tt = 0;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        s.clear();
        hh = tt = 0;
        int sum = 0;
        bool success = false;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; ++i) {
            int x;
            scanf("%d", &x);
            ++s[x];
        }
        for (auto item : s) {
            int num = item.first, cnt = item.second;
            sum += cnt;
            q[tt++] = num;
            while (sum > k) {
                sum -= s[q[hh]];
                ++hh;
            }
            if (sum == k) {
                success = true;
                printf("%d %d\n", q[hh], q[tt - 1]);
                break;
            }
        }
        if (!success)
            puts("-1");
    }
}

第三题

数字末尾零的个数 = min(数字2的因子个数，数字5的因子个数)
树链剖分，对子树的更新和查询转化为链上的连续节点操作。
转化为一个维护带懒更新的线段树。

最后三分钟调出来，发现query函数写错了，需要全部返回后在quert_tree里取min

LL a_cnt2, a_cnt5; // add_cntx 懒标记
LL s_cnt2, s_cnt5; // sum_cntx 以该节点为根的子树，所有2和5的因子的数量

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N = 100010, M = (N << 1);

int n, q;
int w[N], h[N], e[M], ne[M], idx;
int dfn[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Tree {
    int l, r;
    LL a_cnt2, a_cnt5;
    LL s_cnt2, s_cnt5;
};
Tree tr[N << 2];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int father, int depth) {
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father)
            continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j])
            son[u] = j;
    }
}

void dfs2(int u, int t) {
    dfn[u] = ++cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u])
        return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u])
            continue;
        dfs2(j, j);
    }
}

pair<int, int> getval(int num) {
    int cnt2 = 0, cnt5 = 0;
    while (num) {
        if (num % 2 == 0) {
            ++cnt2;
            num /= 2;
        } else if (num % 5 == 0) {
            ++cnt5;
            num /= 5;
        } else {
            break;
        }
    }
    return {cnt2, cnt5};
}

void pushup(int f) {
    tr[f].s_cnt2 = tr[f << 1].s_cnt2 + tr[f << 1 | 1].s_cnt2;
    tr[f].s_cnt5 = tr[f << 1].s_cnt5 + tr[f << 1 | 1].s_cnt5;
}

void pushdown(int f) {
    auto &root = tr[f], &left = tr[f << 1], &right = tr[f << 1 | 1];
    if (root.a_cnt2 || root.a_cnt5) {
        left.a_cnt2 += root.a_cnt2, left.s_cnt2 += root.a_cnt2 * (left.r - left.l + 1);
        left.a_cnt5 += root.a_cnt5, left.s_cnt5 += root.a_cnt5 * (left.r - left.l + 1);
        right.a_cnt2 += root.a_cnt2, right.s_cnt2 += root.a_cnt2 * (right.r - right.l + 1);
        right.a_cnt5 += root.a_cnt5, right.s_cnt5 += root.a_cnt5 * (right.r - right.l + 1);
        root.a_cnt2 = root.a_cnt5 = 0;
    }
}

void build(int f, int l, int r) {
    auto [cnt2, cnt5] = getval(nw[r]);
    tr[f] = {l, r, 0, 0, cnt2, cnt5};
    if (l == r)
        return;
    int mid = l + r >> 1;
    int lc = f << 1, rc = lc | 1;
    build(lc, l, mid), build(rc, mid + 1, r);
    pushup(f);
}

void update(int f, int l, int r, int k2, int k5) {
    if (l <= tr[f].l && r >= tr[f].r) {
        tr[f].a_cnt2 += k2;
        tr[f].a_cnt5 += k5;
        tr[f].s_cnt2 += k2 * (tr[f].r - tr[f].l + 1);
        tr[f].s_cnt5 += k5 * (tr[f].r - tr[f].l + 1);
        return;
    }
    pushdown(f);
    int mid = tr[f].l + tr[f].r >> 1;
    if (mid >= l)
        update(f << 1, l, r, k2, k5);
    if (mid < r)
        update(f << 1 | 1, l, r, k2, k5);
    pushup(f);
}

pair<LL, LL> query(int f, int l, int r) {
    if (l <= tr[f].l && r >= tr[f].r)
        return {tr[f].s_cnt2, tr[f].s_cnt5};
    pushdown(f);
    int mid = tr[f].l + tr[f].r >> 1;
    LL res2 = 0, res5 = 0;
    if (mid >= l) {
        auto [cnt2, cnt5] =  query(f << 1, l, r);
        res2 += cnt2;
        res5 += cnt5;
    }
    if (mid < r) {
        auto [cnt2, cnt5] =  query(f << 1 | 1, l, r);
        res2 += cnt2;
        res5 += cnt5;
    }
    return {res2, res5};
}

void update_tree(int u, int num) {
    auto [cnt2, cnt5] = getval(num);
    update(1, dfn[u], dfn[u] + sz[u] - 1, cnt2, cnt5);
}

LL quert_tree(int u) {
    auto [cnt2, cnt5] = query(1, dfn[u], dfn[u] + sz[u] - 1);
    return min(cnt2, cnt5);
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", w + i);
    for (int i = 1; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        update_tree(x, y);
    }

    for (int i = 1; i <= n; ++i) {
        LL res;
        res = quert_tree(i);
        printf("%lld", res);
        if (i != n) printf(" ");
    }
    return 0;
}

/*
5
1 2 6 3 1
1 2
1 3
2 4
2 5
1
2 5

*/