题目1
思路
使用vector<string>模拟一个栈就行了</string>
- cd s相当于进栈
- cd ..相当于出栈
- pwd命令打印出vector中的内容
代码
#include<iostream> #include<vector> #include<string> #include<unordered_set> #include<algorithm> #include<numeric> #include<queue> using namespace std; int main() { int n; cin >> n; string a; string b; vector<string> dir; for (int i = 0; i < n; i++) { cin >> a; if (a == "cd") { cin >> b; if (b == ".." && dir.size()) dir.pop_back(); if (b!="..") dir.push_back(b); } if (a == "pwd") { if(dir.empty()) cout<<"\\"; else { for (auto ss : dir) { cout << "\\" << ss; } } cout << endl; } }
题目2
思路
从不平衡度限制来进行考虑,检验k个段是否可以满足该不平衡度的需求。不平衡度越小,限制越大,所期望的k越大。举个例子,若不平衡为0,序列为[1,2,3,4,5],需要的k为5才能满足,若不平衡度限制为1,则需要3个可以满足,划分为[1,2],[3,4][5]。基于这个角度,然后使用二分查找即可。
(这个题目是有点绕,想清楚了就很简单)
代码
#include<iostream> #include<vector> #include<string> #include<unordered_set> #include<algorithm> #include<numeric> #include<queue> using namespace std; //检验k能够满足不平衡度为ret的需求 bool ub_satisfied(vector<int>& nums, int ret, int k) { int index = 0; int min_v = 1e5; int max_v = 0; for (; index < nums.size(); index++) { max_v = max(max_v, nums[index]); min_v = min(min_v, nums[index]); if (max_v - min_v > ret) { --k; max_v = min_v = nums[index]; } if (k == 0) break; } if (index == nums.size()) return true; else return false; } //标准二分,没啥好说的 int bin_search(vector<int>& nums,int k,int l=0,int r=1e5) { if (l == r) return l; int mid = (l + r) / 2; if (ub_satisfied(nums, mid, k)) { return bin_search(nums, k, l, mid); } else { return bin_search(nums, k, mid+1,r); } return -1; } int main() { int n, k; cin >> n >> k; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } int ret = bin_search(nums, k); cout << ret << endl; }
题目3
思路
首先问题可以转换为子问题,由于题目是连续的1进行拆分,最大化分数。首先提取出每段连续1的长度,以111111001111101111为例,划分为三个连续1子串,长度分别为6,5,4,这三个子问题之间互不干扰。每个子问题就是给定一个数字n(代表着连续1的长度),进行拆分,使其分数最大化,这是标准的dp,dp[n]=max(dp[n],score(c)+dp[n-c]) for all c. score(c)代表着消除c个1的分数。
代码
#include<iostream> #include<vector> #include<string> #include<unordered_set> #include<algorithm> #include<numeric> #include<queue> using namespace std; vector<int> dp; int max_score(int num, vector<vector<int>>& score) { if (num < score[0][0]) return 0; if (dp[num]) return dp[num]; int ret = 0; for (int i = 0; i < score.size(); i++) { if (num < score[i][0]) break; ret = max(ret, score[i][1] + max_score(num - score[i][0], score)); } dp[num] = ret; return ret; } int main() { int n, m; cin >> n >> m; dp.resize(n+1); vector<vector<int>> score(m, vector<int>(2, 0)); string ss; int ret = 0; cin >> ss; for (int i = 0; i < m; i++) { cin >> score[i][0] >> score[i][1]; } sort(score.begin(), score.end()); for (int i = 0; i < ss.length(); i++) { if (ss[i] == '0') continue; int s = i; while (i < ss.length() && ss[i] == '1') { i++; } ret += max_score(i - s, score); } cout << ret << endl; }
全部评论
(1) 回帖