9.4 滴滴笔试-题解

第一题 选取尽量多的元素，但其中最大值不能超过平均值的k倍

法1：从大到小排序，然后尺取一下
法2：二分

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, k;
long long a[200005];

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1, cmp);

    int l = 1, r = 1, ans = 1;
    long long sum = a[1];
    while (r <= n) {
        while (l < r && sum / (double)(r - l + 1) * k < (double)a[l]) {
            sum -= a[l];
            l++;
        }
        ans = max(ans, r - l + 1);
        if (r == n) {
            break;
        }
        r++;
        sum += a[r];
    }

    cout << ans << endl;

    return 0;
}

第二题 定义f(x)=x的十进制各位的异或和，最多70000次询问，询问[L,R]中f(x)为t的值有多少个。1<=L<=R<=70000

预处理+前缀和，离线查询

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int l[100005], r[100005], q[100005], ans[100005];
int sum[70005][16];

void init() {
    for (int i = 0; i <= 70003; i++) {
        int t = i;
        int x = 0;
        while (t) {
            x ^= t % 10;
            t /= 10;
        }
        sum[i][x] = 1;
    }

    for (int i = 0; i < 16; i++) {
        for (int j = 0; j <= 70003; j++) {
            if (j == 0) {
                continue;
            }
            sum[j][i] += sum[j - 1][i];
        }
    }
}

int main() {
    init();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> q[i];
    }

    for (int i = 1; i <= n; i++) {
        if (q[i] > 15) {
            ans[i] = 0;
            continue;
        }
        if (l[i] == 0) {
            ans[i] = sum[r[i]][q[i]];
        }
        else {
            ans[i] = sum[r[i]][q[i]] - sum[l[i] - 1][q[i]];
        }
    }

    cout << ans[1];
    for (int i = 2; i <= n; i++) {
        cout << ' ' << ans[i];
    }
    cout << endl;

    return 0;
}