2023-09-08 滴滴后端笔试编程题
第一题 糖果,二分找到最小满足的天数
#include <bits/stdc++.h> using i64 = long long; int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); i64 n, a, b; std::cin >> n >> a >> b; std::vector<i64> c(n); for (int i = 0; i < n; i++) { std::cin >> c[i]; } auto check = [&](i64 mid) -> bool { i64 sum = 0; for (int i = 0; i < n; i++) { sum += c[i] * mid / b; } return sum >= a; }; i64 l = 0, r = 1e14; while (l < r) { i64 mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } std::cout << l << "\n"; return 0; }
第二题 字符串哈希,因为不出现包含的情况,所以一个字符串的前缀和后缀必然不会存在于同一个字符串里面(有点绕,具体可看代码)
#include <bits/stdc++.h> using i64 = long long; int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); int n; std::cin >> n; std::vector<std::string> S(n); for (int i = 0; i < n; i++) { std::cin >> S[i]; } std::map<std::string, bool> pre, suf; for (auto s : S) { for (int i = 1; i < s.size(); i++) { pre[s.substr(0, i)] = true; suf[s.substr(i, s.size() - i)] = true; } } std::set<std::string> ans; for (auto s : S) { for (int i = 1; i < s.size(); i++) { if (suf[s.substr(0, i)] && pre[s.substr(i, s.size() - i)]) { ans.insert(s); break; } } } std::cout << ans.size() << "\n"; for (auto res : ans) { std::cout << res << "\n"; } return 0; }#我的实习求职记录##滴滴#