大疆 8.6 软开B卷
大疆 先贴代码,题目在后面
第一题 爱玩游戏的小J 简单的背包问题
#include <iostream> #include <vector> using namespace std; int main(){ int T; cin >> T; for(int i=0; i<T; i++){ int N, X; cin >> N >> X; vector<int> dp(X+1, 0); vector<int> val(N, 0); vector<int> tim(N, 0); for(int i=0; i<N; i++){ cin >> val[i] >> tim[i]; for(int j=X; j>=0 && j>= tim[i]; j--) dp[j] = max(dp[j], dp[j-tim[i]] + val[i]); } cout << dp[X] << endl; } return 0; }
第二题 不听话的机器人 直接hashMap即可
#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main(){ int N, M; while(cin >> N >> M){ unordered_map<string, string> hashMap; for(int i=0; i<N; i++){ string str1, str2; cin >> str1 >> str2; hashMap[str1] = str2; } for(int i=0; i<M; i++){ string str; cin >> str; cout << hashMap[str] << endl; } } return 0; }
第三题 应该怎么吃呢
暴力递归,过了 50%
不过直接输出 1,也是 50% 手动捂脸
#include <iostream> #include <vector> #include <algorithm> using namespace std; int mode = 1e9+7; void dfs(vector<int> &arr, int &res, int val, int st, int last){ if(val == 0) { res = (res+1) % mode; return ; } if(val < 0 || st >= arr.size()) return ; for(int i=min(last-1, val/arr[st]); i>=0; i--) dfs(arr, res, val-arr[st]*i, st+1, i); } int main(){ int V, N, M; while(cin >> V >> N){ // 每件物品的价值 vector<int> arr(N); // 喜爱程度,越小越喜爱 vector<int> brr(N, N); for(int i=0; i<N; i++) cin >> arr[i]; cin >> M; for(int i=0; i<M; i++){ int tem; cin >> tem; brr[tem-1] = i; } sort(arr.begin(), arr.end(), [&](int a, int b){ return brr[a] < brr[b]; }); int res = 0; dfs(arr, res, V, 0, V); cout << res << endl; } return 0; }#大疆##笔试题目#