字节9.10后端 笔试

T1

给你一个字符串，然后进行q次操作，每次选择一个位置idx 并修改为c，输出每次操作后unique(s) 的值。unique("aabbbcc") = 2，unique表示相邻去重后（"abc"）s的长度

// 本题为考试多行输入输出规范示例，无需提交，不计分。
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n; cin >> n;
    string s; cin >> s;
    int ans = 1;
    for(int i = 1; i < n; i++){
        if(s[i] != s[i-1]) ans++;
    }
    s.insert(s.begin(), '?');
    s += "?";
    int q; cin >> q;
    while(q--){
        int idx;
        char c;
        cin >> idx >> c;
        //idx --;
        bool change = false;
        if(s[idx] != c) change = true;
        if(change){
            //aba
            //cbx
            //aab
            //abb
            if(idx == 1){
                if(n >= 2 && s[1] != s[2]){
                    if(c == s[2]) ans--;
                }else if(n >= 2 && s[1] == s[2]){
                    ans++;
                }
            }else if(idx == n){
                if(n >= 2 && s[n] != s[n-1]){
                    if(c == s[n-1]) ans--;
                }else if(n >= 2 && s[n] == s[n-1]){
                    ans++;
                }
            }else{
                if(s[idx] != s[idx-1] && s[idx] != s[idx+1]){
                    if(c == s[idx-1]) ans--;
                    if(c == s[idx+1]) ans--;
                }else if(s[idx] == s[idx-1] && s[idx] == s[idx+1]){
                    ans += 2;
                }else if(s[idx] == s[idx-1]) {
                    if(c != s[idx+1]) ans++;
                }else if(s[idx] == s[idx+1]){
                    if(c != s[idx-1]) ans++;
                }

            }
            s[idx] = c;
        }
        cout << ans << endl;
    }
    return 0;
}

T2

给你一个数组a, 和一个数x, 定义一个数组的权值如下：a1+max(0,a2-1)+max(0,a3-2)+...

你可以将数组中连续的值进行分组，如数组a = [1, 2, 3, 4, 5], 分为[1, 2] [3, 4, 5]

问你最少几次分组，可以使得各组权值和 >= x

没来得及写

// 本题为考试多行输入输出规范示例，无需提交，不计分。
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int a[N], b[N];

int main(){
    int n, x; cin >> n >> x;
    for(int i = 0; i < n; i++) cin >> a[i];
    int ans = 1;//13.3%

    cout << ans << endl;
    return 0;
}

T3

给你一个长度为n数组a, 和b, 其中a表示重量，b表示特征值，进行q次操作，每次操作选择一个a[i] == x的值，将这个a[i] 尽可能平均或接近分为 b[i] 组，如a[i] = 10, b[i] = 2， 则会分为5， 5， 5， 5， 5. 若a[i] < b[i], 则分为a[i] 个 特征值为1，问q次操作后，还有多少个物品

// 本题为考试多行输入输出规范示例，无需提交，不计分。
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <queue>

using namespace std;

using PII = pair<int, int>;
using ll = int64_t;

const int N = 1e5+10;
ll a[N], b[N];

map<ll, ll> mp[11];

int main(){
    int n; cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    ll ans = n;
    
    for(int i = 0; i < n; i++){
        mp[b[i]][a[i]] += 1;
    }
    ll q, x; cin >> q;
    while(q--){
        cin >> x;
        for(ll i = 1; i <= 10; i++){
            if(mp[i][x] > 0){
                mp[i][x] -= 1;
                ans --;

                if(x < i){
                    mp[i][1] += x;
                    ans += x;
                }else{
                    ll val = x / i;
                    ll yu = x - val * i;//下取整这里不对11 / 3 = 3 3 5是不对的，应该是3 4 4
                    //上取整的话 11 / 3 = 4, 4 4 3， 9 / 2 = 5， 5， 4，
                    // 应该是 yu 个数+1 的重量 += yu;
                    mp[i][val] += i - yu;
                    mp[i][val + 1] += yu;
                    ans += i;
                }
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

T4

给你一个长度为n的数组a，和长度为m的数组b，求有多少个数对a[i], b[i] 满足 lcm(a[i], b[i]) == k

写了一个枚举k的因子，然后求cnt[ai] * cnt[bi]，结果枚举k因子的时候写错了，最后timeover, 不过暴力也有20%

// 本题为考试多行输入输出规范示例，无需提交，不计分。
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;

//裴蜀定理

//gcd(a, b) = a * b / lcm(a, b)
//gcd(4, 2) = 2
//lcm(4, 2) = 4
//现在要求lcm == k
//已知a，有多少个b能满足lcm(a, b) == k

//

const int N = 1e5+10;
int a[N], b[N];

int main(){
    int n, m, k; cin >> n >> m >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(std::lcm(a[i], b[j]) == k) ans++;
        }
    }

    cout << ans << endl;//20%
    return 0;
}