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;
} 
