科大讯飞实习java一面

选择题、多选题三道编程题：（1）合并两个有序数组（LC88）（2）第K大的数（LC76）（3）IPO（LC502）我太菜了，选择题和多选题会有点懵，基础不牢固。许愿能面来攒经验。

笔试时间：2025年8月13日往年笔试合集：2023春招秋招笔试合集2024春招秋招笔试合集第一题：超级重排Tk 有一个长度为 n 的数组{a1,a2,...,an}。Tk 定义这个数组的权值为：。为了使数组的权值最大，Tk 提出如下超级重排流程：·将所有元素的十进制表示按原序拼接成一个字符串；·对该字符串中的所有字符进行重新排列；·按照原元素的位数切分字符串，恢复为 n 个新数字。或者换句话说，首先，收集所有数字的每一个单独的数位；其次，对于每一个原始数字 ai，记录下它的位数。你必须用收集到的所有数位来构造 n 个新的数字，其中第 j 个新数字的位数必须与原始数组中第 j 个数字 aj 的...

中途加入只写了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 longconst 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';}

笔试时间：2025年8月16日往年笔试合集：2023春招秋招笔试合集2024春招秋招笔试合集第一题你有一个长度为n的序列A: a₁,a₂,…,aₙ，你需要进行如下操作至多一次: 选择一个区间[L,R] (1≤L≤R≤n)，将a_L,a_{L+1},…,a_R全部加1。即a_L,a_{L+1},…,a_R均变为a_L+1,a_{L+1}+1,…,a_R+1 设变化后的序列为B: b₁,b₂,…,bₙ，你需要最大化inv(A)-inv(B)，其中inv()函数表示该序列的逆序对数量，即满足i<j，a_i>a_j的二元组(i,j)个数。换句话说，你需要尽可能地减小序列A的逆序对数量。输入...