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

2. 一个长为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;
}

3. 长为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;
}