首页 > 百度笔试C++后端开发 AC1.5
头像
牛客861274301号
编辑于 2020-09-14 22:02
+ 关注

百度笔试C++后端开发 AC1.5

1.吃饭吃饱 大到小排贪心,AC
#include <bits/stdc++.h>
using namespace std;

int main() {
    using P = pair<int,int>;
    int T;
    cin >> T;
    while (T--) {
        int n,m;
        cin >> n >> m;
        vector<P> vec;
        int res = 0;                           
        for (int i = 1; i <= n; i++) {
            int v;
            cin >> v;
            vec.push_back({v,i});
        }
        vector<int> r;
        sort(vec.begin(),vec.end(),[](P& x, P& y){return x.first > y.first;});
        for (int i = 0; i < n; i++) {
            res += vec[i].first;
            r.push_back(vec[i].second);
            if (res >= m)
                break;
        }
       
        if (res >= m) {
            cout << r.size() << endl;
            for (auto v : r) { cout << v << " ";}
            cout << endl;
        } else cout << -1<<endl;

    }
}
2. 区间内乘积为奇数或者偶数的个数,通过50%,猜想可能是应为区间内没有去重
求出所求区间奇数的个数n和偶数个数m, 如果求奇数个数则结果为 2^n-1,如果为偶数的个数则结果为(2^m-1)*2^n
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> vec(n+1,0);
    for (int i = 1; i <= n; i++){
        int v;
        cin >> v;
        v %= 2;
        vec[i] = vec[i-1] + v;
    }
    int odd;
    int ou;
    int lr , l, r;
    long long res;
    while (m--) {
        cin >> lr >> l >> r;
        odd = vec[r] - vec[l-1];
        ou = r-l+1-odd;
        res = 1;
        while(odd--)
        res = (res<<1)%1000000007;
        if (lr == 1){
            res--;
        } else {
            long long t = 1;
            while(ou--) {
                t = (t<<1)%1000000007;
            }
            res = res*(t-1)%1000000007;
        }
        cout << res <<endl;
    }
}

3. 求期望,不会

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐