第一题
/* 给了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) 回帖