第一题
#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int getIndex(const string& str) { int mid = max(int(str.length() / 2 - 1), 0); int res = str.length() - 1; //mid为中点 while (mid < str.length()) { int index = 0; while (index + 1 + mid < str.length() && mid - index >= 0) { if (str[mid + 1 + index] != str[mid - index]) break; ++index; } if (mid + 1 + index == str.length()) res = min(res, mid - index); if (res == -1) break; index = 0; while (index + mid + 1 < str.length() && mid - index - 1 >= 0) { if (str[mid + index + 1] != str[mid - index - 1]) break; ++index; } if (index + mid + 1 == str.length()) res = min(res, mid - index - 1); ++mid; if (res == -1) break; } return res + 1; } string getRes(const string& str) { int index = getIndex(str); string tmp = str.substr(0, index); reverse(tmp.begin(), tmp.end()); return str + tmp; } int main() { string str; cin >> str; cout << getRes(str) << endl; }第二题
#include<vector> #include<iostream> #include<algorithm> using namespace std; void reduce(vector<int>&nums,int index,int first,int second,int sum,int& res) { if (first == second) res = min(res, sum - first - second); if (index >= nums.size()) return; reduce(nums, index + 1, first + nums[index], second, sum, res); reduce(nums, index + 1, first, second + nums[index], sum, res); reduce(nums, index + 1, first, second, sum, res); } int getMinCost(vector<int>&nums) { int index = 0; int sum = 0; for (int i = 0; i < nums.size(); ++i) sum += nums[i]; int res = sum; reduce(nums, index, 0, 0, sum, res); return res; } int main() { int t, n; cin >> t; while (t-- > 0) { cin >> n; vector<int>nums(n); for (int i = 0; i < n; ++i) cin >> nums[i]; cout << getMinCost(nums) << endl; } }第三题
#include<iostream> #include<vector> #include<algorithm> #include<string> using namespace std; int getMinCost(vector<int>a, vector<int>b) { vector<int>dp(a.size() + 1); dp[1] = a[0]; for (int i = 2; i < dp.size(); ++i) { dp[i] = min(dp[i - 1] + a[i - 1], dp[i - 2] + b[i - 2]); } return dp.back(); } string getTime(int cost) { int h = 8, m = 0, s = 0; s = cost % 60; cost /= 60; m += cost % 60; cost /= 60; h += cost % 24; bool flag = false; if (h > 12) { h -= 12; flag = true; } string sh = to_string(h); if (sh.size() < 2) sh = "0" + sh; string sm = to_string(m); if (sm.size() < 2) sm = "0" + sm; string ss = to_string(s); if (ss.size() < 2) ss = "0" + ss; return sh + ":" + sm + ":" + ss + " " + (flag ? "pm" : "am"); } int main() { int m; cin >> m; while (m-- > 0) { int n; cin >> n; vector<int>a(n); vector<int>b(n); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n - 1; ++i) cin >> b[i]; int cost = getMinCost(a, b); cout << getTime(cost) << endl; } }
第四题(超时,过50%)
#include<unordered_map> #include<unordered_set> #include<vector> #include<iostream> #include<stack> using namespace std; int getNum(int n,vector<vector<int>>&nums) { unordered_map<int, unordered_set<int>>graph; for (int i = 0; i < nums.size(); ++i) graph[nums[i][0]].insert(nums[i][1]); unordered_map<int, unordered_set<int>>hashMap; for (int i = 0; i < n; ++i) { unordered_set<int>visited; stack<int>stack; visited.insert(i); stack.push(i); int m = 0; while (!stack.empty()) { int from = stack.top(); stack.pop(); if (graph.find(from) == graph.end()) continue; auto& ps = graph[from]; for (auto& p : ps) { if (visited.find(p) != visited.end()) continue; visited.insert(p); stack.push(p); ++m; } } hashMap[i] = visited; } int cnt = 0; for (auto& kv : hashMap) { int from = kv.first; auto& set = kv.second; for (auto& to : set) { if (hashMap.find(to) == hashMap.end()) continue; if (hashMap[to].find(from) == hashMap[to].end()) continue; if (to == from) continue; ++cnt; } } return cnt / 2; } int main() { int n, m; cin >> n >> m; vector<vector<int>>nums(m); for (int i = 0; i < m; ++i) { vector<int>vec(2); cin >> vec[0] >> vec[1]; vec[0] -= 1; vec[1] -= 1; nums[i] = vec; } cout << getNum(n,nums) << endl; }
全部评论
(10) 回帖