网易2021秋季校招C++笔试
100,100,100,0,75分能不能面试凭运气吧。
1. Append least characters to a given string so that the string becomes a palindrome. Print the final palindrome.
#include <iostream> using namespace std; string solve(string s) { int i = 0, j = s.size() - 1; for(; i < j; i++) { if(s[i] == s[j]) { j--; } else { j = s.size() - 1; } } int m = min(i, j); int n = max(i, j); for(; m >= 0; m--, n++) { if(n > s.size() - 1) { s.push_back(s[m]); } } return s; } int main() { string s; cin >> s; std::cout << solve(s); return 0; }2. 把一些物品分给a或者b,也可以弃置,要求最后a和b拿到的物品的权重和相同,且弃置物品的权重和最小,输出最小弃置物品的权重和。
数据规模比较小,最多15个物品,直接brute-force。
#include <iostream> #include <vector> using namespace std; const int inf = 999999; // kth item void solve(vector<int> items, int a, int b, int k, int discard, int* minimum) { if(k == -1) { if(a == b) { if(discard < *minimum) *minimum = discard; } return; } if(discard > *minimum) return; solve(items, a + items[k], b, k - 1, discard, minimum); solve(items, a, b + items[k], k - 1, discard, minimum); solve(items, a, b, k - 1, discard + items[k], minimum); } int solve(vector<int> items) { int minimum = inf; solve(items, 0, 0, items.size() - 1, 0, &minimum); return minimum; } int main() { int T; cin >> T; while(T--) { int n; cin >> n; vector<int> items(n); for(int i = 0; i < n; ++i) { cin >> items[i]; } cout << solve(items) << endl; } return 0; }
3. 一群人排队买票,可以一个人单独买,也可以前后两个人一起买,单独买的时间总和和一起买的时间不一样,售票处8点开门,求最早关门时间,如08:00:40 am关门。
#include <iostream> #include <vector> #include <sstream> using namespace std; int a[2010], b[2010], cost[2010]; string sec2str(int sec) { stringstream ss; bool is_am = true; int hour = sec / 3600; sec = sec - hour * 3600; int minute = sec / 60; sec = sec - minute * 60; if(hour + 8 > 12) { hour = hour + 8 - 12; is_am = false; } else { // if(hour + 8 == 12) is_am = false; hour += 8; } if(hour < 10) { ss << "0"; } ss << hour << ":"; if(minute < 10) { ss << "0"; } ss << minute << ":"; if(sec < 10) { ss << "0"; } ss << sec << " "; if(is_am) { ss << "am"; } else { ss << "pm"; } return ss.str(); } string solve(int* a, int* b, int n) { if(n == 0) return sec2str(0); if(n == 1) return sec2str(a[0]); if(n == 2) return sec2str(min(a[0] + a[1], b[0])); cost[0] = 0; cost[1] = a[0]; for(int i = 2; i < n + 1; ++i) { cost[i] = min(cost[i-1] + a[i-1], cost[i-2] + b[i-2]); } return sec2str(cost[n]); } int main() { int T; cin >> T; while(T--) { int n; cin >> n; for(int i = 0; i < n; ++i) { cin >> a[i]; } for(int i = 0; i < n - 1; ++i) { cin >> b[i]; } cout << solve(a, b, n) << endl; } return 0; }
4. Directed Graph,大概就是要在里面找到cycle,不熟悉这个类型的,时间也不够了,放弃了。