2020.09.05 搜狗研发岗笔试 A~C题解
A. 三种商品，两个可以换一个任意的，三种各一个可以换一个奖品，问最多换几个奖品。
直接二分答案。
class Solution {
public:
int numberofprize(int a, int b, int c) {
int lo = 0, hi = 1E9;
int ret = 0;
auto check = [&](int val) {
int tmp = 0;
int x = a, y = b, z = c;
x -= val, y -= val, z -= val;
if (x >= 0) tmp += x, x = 0;
if (y >= 0) tmp += y, y = 0;
if (z >= 0) tmp += z, z = 0;
return tmp / 2 >= -(x + y + z);
};
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (check(mid)) {
ret = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ret;
}
};
B. 盖房子什么的。
直接模拟。
class Solution {
public:
int getHouses(int t, int* xa, int xaLen) {
int ret = 2;
vector<int> x, a;
for (int i = 0; i < xaLen; i += 2) {
x.emplace_back(xa[i]);
a.emplace_back(xa[i + 1]);
}
int n = x.size();
if (n == 1) return 2;
for (int i = 0; i < n - 1; i++) {
double lo = (double)x[i] + (double)a[i] / 2.0;
double hi = (double)x[i + 1] - (double)a[i + 1] / 2.0;
if (hi - lo < t) continue;
if (hi - lo == t) {
ret++;
} else {
ret += 2;
}
}
return ret;
}
}; C. 构造密码什么的。
记搜，f(i,len)维护当前数字为i，目前匹配到长度为len时的方案数。用一个标记去判重。
using LL = long long;
class Solution {
public:
long long getPasswordCount(string password) {
int n = password.length();
LL f[11][55];
memset(f, -1, sizeof f);
function<LL(int, int, int flag)> dfs = [&](int i, int len, int flag) {
if (~f[i][len]) return f[i][len];
if (len == n) return 1LL - flag;
LL ret = 0;
double tmp = password[len] - '0' + i;
tmp = (double)(tmp) / 2.0;
if (tmp != (int)tmp) {
tmp++;
ret += dfs((int)tmp, len + 1, flag && ((int)tmp == password[len] - '0'));
}
tmp = (password[len] - '0' + i) / 2.0;
ret += dfs((int)tmp, len + 1, flag && ((int)tmp == password[len] - '0'));
return f[i][len] = ret;
};
LL ret = 0;
if (n == 1) return 9;
for (int i = 0; i <= 9; i++) {
memset(f, -1, sizeof f);
ret += dfs(i, 1, i == password[0] - '0');
}
return ret;
}
}; 
