首页 > 3.21百度笔试编程题(三题均AC)
头像
精神病科黄主任
编辑于 2021-04-07 09:52
+ 关注

3.21百度笔试编程题(三题均AC)

第一题
/*
    给了n个数字和一个价值m,让输出任意一种满足的组合,使得和大于等于m
    没有就输出-1
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 18:01:17
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const ll mod=1e9+7;
struct node {
 ll x,id;   
}a[N];
int main(){
    int T;cin>>T;
    while(T--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i].x;
            a[i].id=i;
        }
        sort(a+1,a+n+1,[](node a,node b){
            return a.x>b.x;
        });
        vector<int> ans;
        for(int i=1;i<=n;i++){
            if(m>a[i].x){
                ans.push_back(a[i].id);
                m-=a[i].x;
            }
            else{
                ans.push_back(a[i].id);
                m=0;
                break;
            }
        }
        if(m){
            cout<<-1<<endl;
        }
        else{
            cout<<ans.size()<<endl;
            for(auto &X:ans) cout<<X<<" ";
            cout<<endl;
        }

    }
    return 0;
}


第二题
/*
    有n个物品,m个可以装物品的,装物品的东西大小要大于等于物品的大小
    输出一种满足的序列,使得能装的物品个数最大,装不下就输出-1,
    否则输出装物品的东西的id
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 18:07:17
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const ll mod=1e9+7;
struct node {
 ll x,id;   
 friend bool operator<(node a,node b){
     return a.x>b.x;
 }
}a[N],b[N];
int ans[N];
int main(){
    int T;cin>>T;
    while(T--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i].x;
            a[i].id=i;
        }
        for(int i=1;i<=m;i++){
            cin>>b[i].x;
            b[i].id=i;
        }
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        int j=1;
        for(int i=1;i<=n;i++){
            if(j<=m &&  b[j].x>=a[i].x){
                ans[a[i].id]=b[j].id;
                ++j;
            }
            else ans[a[i].id]=-1;
        }
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}


第三题
/*
    n<=1e5   2<=m<=7
    跳台阶,每次跳的不能和前面两次有重复的,即第i+2次跳的阶数不能和第i次、第i+1次跳的一样,求跳到n的方案数
    取模1e9+7
 * @Author: 7QQQQQQQ
 * @IDE: vscode
 * @Date: 2021-03-21 18:01:17
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const ll mod=1e9+7;
ll dp[N][10][10];
int DFS(int n,int m,int a,int b){
    if(n==0) return 1;
    if(!dp[n][a][b]){
        ll ans=0;
        for(int i=1;i<=m;i++){
            if(i!=a && i!=b){
                if(n>=i)ans+=DFS(n-i,m,i,a);
                ans%=mod;
            }
        }
        dp[n][a][b]=ans;
    }
    return dp[n][a][b];
}
int main(){
    int n,m;cin>>n>>m;
    cout<<DFS(n,m,0,0);
    return 0;
}


全部评论

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