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;
}