字节跳动2024秋招研发第四场笔试【后端方向】

第一题：吃糖果xx值大于等于x（二分答案）

题意：给一个长度为 $n(n \leq 1e5)$ 的数组 $a(0 \leq a_i \leq 1e9)$ 代表 $n$ 个糖果的幸福值，一天可以吃任意个糖果得到幸福值 $a_j a_{j 1}-1 ... max(0,a_{j k}-k)$ 其中 $j$ 不代表下标，吃的顺序可以任意。现在求至少吃多少天可以得到至少 $x$ 的幸福值。

思路：不难发现答案是线性的，存在一个分界天数使得达到这个分界后都能达到 $x$ ，因此使用二分天数 $d$ 。我们可以贪心的认为对于幸福值大的糖果尽量在每一天更早的吃。即先对 $a$ 降序，每次 $Check$ 都长度为 $d$ 累加（我直接累减，这里可以用前缀和优化，但是没啥必要）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
int a[N];
int n, x;
bool cmp(int a,int b) {
    return a > b;
}
bool check(int m) {
    int res = x;
    for(int i = 1, k = 0; i <= n; k ++) {
        for(int j = i; j <= n && j < i + m; j ++) {
            res -= max(0, a[j] - k);
            if(res <= 0) {
                return true;
            }
        }
        i += m;
    }
    return false;
}
int main() {
    cin >> n >> x;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n, cmp);
    int l = 1, r = n + 2;
    while(l < r) {
        int m = (l + r) >> 1;
        if(check(m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    cout << l << endl;
}

第二题：石头劈开后求个数（模拟）

题意：石头有质量 $a_i$ 和特征值 $b_i(b_i \leq 10)$ ，每次选择一个质量为 $a_i$ 的石头质量相同选择特征值最小的那个。然后劈这个石头，这个石头会尽量等量裂开成 $b_i$ 份且特征值均为 $b_i$ ，若 $a_i < b_i$ 则会裂开成 $a_i$ 份质量为1的石子，如 $a_i=10,b_i=3$ 得到 $3,3,4$ ， $a_i=3,b_i=4$ 得到 $1,1,1$ 。现在有 $n(n\leq 1e5)$ 个石头，求选择 $q(q\leq 1e4)$ 个石头后，总共有多少石头。

思路：因为 $b_i$ 值域特别小，可以直接暴力选取到然后插入就行。因此用unordered_map<int, multiset>维护 ${a_i},{b_j,b_{j 1}},...$ 这样可以每次取质量为 $a_i$ 的石头可以方便取最小的 $b_i$ 。

代码：

#include <iostream>
#include <set>

using namespace std;
const int N = 1e5 + 10;
int n, q, x;
int a[N], b[N];
unordered_map<int, multiset<int>> mp;

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        mp[a[i]].insert(b[i]);
    }
    int ans = n;
    while (q--) {
        cin >> x;
        if (mp.find(x) != mp.end()) {
            auto &st = mp[x];
            if (!st.empty()) {
                auto bi = *st.begin();
                if (x <= bi) {
                    // 1
                    for (int i = 0; i < x; i++) {
                        mp[1].insert(bi);
                    }
                    ans += x;
                } else {
                    int minVal = x / bi;
                    int maxCnt = x - minVal * bi;
                    for (int i = 0; i < maxCnt; i++) {
                        mp[minVal + 1].insert(bi);
                    }
                    for (int i = maxCnt; i < bi; i++) {
                        mp[minVal].insert(bi);
                    }
                    ans += bi;
                }
                st.erase(st.begin());
                ans--;
            }
        }
    }
    cout << ans << endl;
}

第三题：求连续相同字符组个数（模拟or线段树）

题意：给一个长度为 $n(n \leq 1e5)$ 的字符串 $S$ ，定义相同字符串组为存在最长的子串 $S_i,S_i 1,...,S_j$ 使得他们为同一种字符。现在有 $q$ 次修改单个字符串的操作，求每次操作后字符组个数。

思路：我一开始看错题意，以为是求最长的字符组。导致直接用线段树了（感兴趣可以自己写写），后面和群里聊其实用if分支就可以了。考虑这个修改的字符左右两边，若左右两边均相等且与原字符也相等，那么此处修改会把这个串拆为三份答案贡献+2，以此类推。 (没有数据验证，仅供参考）

#include <iostream>
#include <set>

using namespace std;
const int N = 1e5 + 10;
int n, q;
char s[N];

int main() {
    cin >> n >> q;
    cin >> (s + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] != s[i - 1])
            ans++;
    }
    int p;
    string c;
    while (q--) {
        cin >> p >> c;
        if (s[p] == s[p + 1]) {
            ans++;
        }
        if (s[p] == s[p - 1]) {
            ans++;
        }
        if (c[0] == s[p + 1]) {
            ans--;
        }
        if (c[0] == s[p - 1]) {
            ans--;
        }
        s[p] = c[0];
        cout << ans << endl;
    }
}

第四题：数组a,b求LCM(ai,bj)=k的对数（模拟）

题意：给一个长度为 $n$ 的数组 $a$ 和长度为 $m$ 的数组 $b$ ，求 $lcm(a_i,b_j)=k$ 的对数。 $n,m\leq 1e5,a_i,b_j,k \leq 1e9$ 。

思路：因为 $lcm(a_i,b_j)=a_i \times b_j / gcd(a_i,b_j)$ 此时 $a_i,b_j$ 一定是 $k$ 的因子此时问题可以转换成求 $a_i/k,b_j/k$ 互质的对数。不难发现（但是我笔试的时候没有发现，直接盲目for循环了） $k$ 的因子的种类数为 $log$ 级别的，因此 $a_i/k,b_i/k$ 的种类数很少，只需要排序计数就可以了。

代码：（没有数据验证，仅供参考）

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 10;
int n, m, k;
int a[N], b[N];
vector<pii> ac, bc;

int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    return gcd(b, a % b);
}
int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    for (int i = 1; i <= n; i++) {
        if (k % a[i] == 0)
            a[i] = k / a[i];
            if (a[i] != a[i - 1]) {
                ac.push_back({a[i], 1});
            } else {
                ac.back().second++;
            }
    }

    for (int i = 1; i <= m; i++) {
        if (k % b[i] == 0) {
            b[i] = k / b[i];
            if (b[i] != b[i - 1]) {
                bc.push_back({b[i], 1});
            } else {
                bc.back().second++;
            }
        }

    }
    ll ans = 0;
    for (auto &pac: ac) {
        for (auto &pbc: bc) {
            if (gcd(pac.first, pbc.first) == 1) {
                ans += (ll) pac.second * pbc.second;
            }
        }
    }
    cout << ans << endl;
}

#字节跳动笔试##字节跳动秋招#