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

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

题意：给一个长度为的数组代表个糖果的幸福值，一天可以吃任意个糖果得到幸福值其中不代表下标，吃的顺序可以任意。 现在求至少吃多少天可以得到至少的幸福值。

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

代码：

#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;
}

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

题意：石头有质量和特征值，每次选择一个质量为的石头质量相同选择特征值最小的那个。然后劈这个石头，这个石头会尽量等量裂开成份且特征值均为，若则会裂开成份质量为1的石子，如得到，得到。 现在有个石头，求选择个石头后，总共有多少石头。

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

代码：

#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线段树）

题意：给一个长度为的字符串，定义相同字符串组为存在最长的子串使得他们为同一种字符。现在有次修改单个字符串的操作，求每次操作后字符组个数。

思路：我一开始看错题意，以为是求最长的字符组。导致直接用线段树了（感兴趣可以自己写写），后面和群里聊其实用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的对数（模拟）

题意：给一个长度为的数组和长度为的数组，求的对数。。

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

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

#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;
}