9.4 滴滴笔试编程题题解
1. 二分+暴力枚举
#include <bits/stdc++.h>
using namespace std;
int main() {
using ll = long long;
int n, k; cin >> n >> k;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
vector<ll> preSum(n+1);
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i-1] + v[i-1];
}
auto ck = [&] (int m) -> bool {
for (int i = 0; i < n-m+1; i++) {
if (1.0*(preSum[i+m]-preSum[i])/m*k >= v[i+m-1]) {
return true;
}
}
return false;
};
int low = 1, high = n;
int ans = 1;
while (low <= high) {
int m = (low+high)/2;
if (!ck(m)) {
high = m-1;
} else {
ans = m;
low = m+1;
}
}
cout << ans << endl;
return 0;
} 2. 前缀和初始化。有个要注意的点是 t 大于等于16时可以直接输出0，因为 0-9 内的任意个数异或范围为 [0, 16)。总的来说两题都不难，即使想不到也能暴力过一部份。 #include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<int>> cnt(70001, vector<int>(20));
cnt[0][0] = 1;
for (int i = 1; i < 70001; i++) {
int s = 0, tmp = i;
while (tmp) {
s ^= tmp % 10;
tmp /= 10;
}
for (int j = 0; j < 16; j++) {
cnt[i][j] = cnt[i-1][j]+(j==s);
}
}
int n; cin >> n;
vector<int> l(n), r(n), t(n);
for (int i = 0; i < n; i++) cin >> l[i];
for (int i = 0; i < n; i++) cin >> r[i];
for (int i = 0; i < n; i++) cin >> t[i];
for (int i = 0; i < n; i++) {
if (t[i] >= 16) {
cout << 0 << " ";
continue;
}
cout << cnt[r[i]][t[i]] - (l[i] ? cnt[l[i]-1][t[i]] : 0) << " ";
}
cout << endl;
return 0;
}
