813 小红书笔试题解

中途加入只写了1，3，第二题没看懂要干啥
第一题：优先队列 + 贪心
可以想到贪心，先把所有的数给拆出来，比如[11, 299]，拆成[9,9,2,1,1]，然后贪心，把大的数放在位数高的那个元素就行了，比如例子中可以变成[(1,2), (2,3)]表示第一个数有两位，第二个数有三位，然后放入优先队列，首先取出第二个元素，将第三位变成9，现在第二个元素只剩两位了，继续放入优先队列，按照该顺序写就OK。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N] ,h[10];
pair<int, int> b[N];
int main() {
    int n;
    cin >> n;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        b[i].second = i;
        while (a[i]) {
            h[a[i] % 10] ++;
            a[i] /= 10;
            b[i].first ++;
        }
        pq.push(b[i]);
    }
    while(pq.size() > 0) {
        pair<int, int> t = pq.top();
        pq.pop();
        int num = 0;
        for (int i = 9; i >= 0; i --) {
            if (h[i] != 0) {
                h[i] --;
                num = i;
                break;
            }
        }
        a[t.second] = a[t.second] * 10 + num;
        t.first--;
        if (t.first !=0) {
            pq.push(t);
        }
    }
    long long res = 0;
    for (int i = 0; i < n; i ++) res += a[i];
    cout << res;
}

第三题：组合数
首先要推公式，如果两个数a[i]和a[j]之间有n个0，设z = a[j] - a[i]， 有多少种可能的序列，设为f(z, n)，C是组合数。
当n = 1 时，记为f(z, 1)，很简单，该0可能是a[i] - a[j]之间的任何数，有z + 1 种可能，f(z, 1) = z + 1 = C(z+1, 1)。
当n = 2 时，固定第一个0，如果第一个0为x，那么第二个0就和n = 1 时一样，此时枚举第一个0从[0-z]，
f(z, 2) = f(z,1) +f(z-1,1) + ...+f(1, 1) + f(0, 1) = 1 +... +z+1 = C(z+2, 2)。
同理， n=3时，同理枚举第一个0。
f(z, 3) = f(z, 2) +... f(0, 2) = C(z+2, 2) + C (z + 1, 2) + ... C(2, 2) = C(z+3, 3)

可以看出来f(z, n) = C(z + n, n) = (z +n)!/(n! & z!);
 #include <bits/stdc++.h>
using namespace std;
#define int long long
const int p = 1e9 + 7;
const int N = 6e5 + 10;
int a[N];
int mul[N], dmul[N];
int qs(int a, int b) {
    int res = 1;
    while (b) {
        if (b&1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
int C(int n, int m) {
    int cc = 1;
    for (int i = n - m + 1; i <= n; i ++) cc = cc * i %p;
    return cc * dmul[m] % p;
}
int lucas(int n, int m) {
    if (m == 0) return 0;
    int a = n % p, b = m % p;
    if (b > a) return 0;
    return C(a, b) * lucas(n/p, m /p) % p;
}
signed main() {
    int n; cin >> n;
    vector<int> v;
    int res = 1;
    mul[0] = dmul[0] = 1;
    for (int i = 1 ; i < N ; i ++) {
        mul[i] = mul[i - 1] * i % p;
        dmul[i] = qs(mul[i], p - 2);
        
    }
    
    for (int i = 1 ;i <= n; i ++) cin >> a[i];
    for (int i = 1 ; i < n; ) {
        if (a[i] == 0) {
            int j = i;
            while (a[j] == 0) j++;
            int d = a[j] - a[i - 1];
            int z = j - i;
            res = res * C(z + d, z) % p;
            i = j;
        } else i++;
    }
    cout << res << '\n';
}

#笔试##小红书求职进展汇总##小红书#