首页 > 10.15 百度笔试
头像
牛客lulu
编辑于 10-16 00:28 上海
+ 关注

10.15 百度笔试

投了两个月,终于给我发笔试了,感觉也是海笔,随便做做吧

  1. 整数1~n,选择k个,计算最多可以获得多少积分。计分规则:若选择了i,并且没有选择i+1,积分加1

    分类讨论,如果 k > (n+1)/2,即返回 k(只选奇数)

    否则返回 n+1-k(前n-k个偶数不选,保证前n-k个奇数和n被算到积分当中)

    注意开 long long

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        if (k <= (n+1)/2) cout << k << endl;
        else cout << n+1-k << endl;
    }
    return 0;
}
  1. 一个长为n的字符串s,进行n次操作,第i次操作将 移动到字符串末尾,输出结果字符串

    用队列模拟。每次取出队列的前两个字符,第一个字符添加到队列尾,第二个字符输出

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; 
    cin >> s;
    int n = s.size(), idx = 0;
    while (n--) {
        s.push_back(s[idx++]);
        cout << s[idx++];
    }
    return 0;
}
  1. 长为n的数组a,每次交替在数字中写下加减符号,求最后剩余的数字(对 1e9 + 7 取模)

    例如:[1,2,3,4] -> [1+2, 2-3, 3+4] = [3, -1, 7] -> [3-(-1), -1+7] = [4, 6] -> [4-6] = [-2],取模后输出 1e9 + 5

    只需要计算每个下标的数字在最后的结果中所占的权值即可

    找规律发现,n=4k+1 时最后的权值与杨辉三角有关,于是其他的情况统统归到 4k+1 即可。(应该有比较严格的数学解法)

    (n=5 时,各个位置的权重为 1 0 2 0 1,n=9 时,各个位置的权重为 1 0 4 0 6 0 4 0 1)

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto & x : a) cin >> x;

    vector<ll> fact(n+1), inv(n+1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % mod;
    inv[n] = qpow(fact[n], mod-2);
    for (int i = n-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % mod;

    auto C = [&](int x, int y) {
        return fact[x] * inv[y] % mod * inv[x-y] % mod;
    };

    int k = (n - 1) / 4 * 2 + 1;
    vector<ll> t(2 * k + 1, 0);
    for (int i = 1; i <= k; i++) t[2*i-2] = C(k-1, i-1);

    bool flag = true; // + or -
    while (n % 4 != 1) {
        n--;
        vector<ll> a2(n);
        for (int i = 0; i < n; i++) {
            a2[i] = (a[i] + (flag ? 1 : -1) * a[i+1] + mod) % mod;
            flag = !flag;
        }
        a = move(a2);
    }
    
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + a[i] * t[i] % mod) % mod;
    }
    cout << ans << '\n';
    return 0;
}

全部评论

(16) 回帖
加载中...
话题 回帖