滴滴9.17 笔试算法 AK 代码
1. 暴力 dfs 可解 。一个数被3整除，则各个位之和，也是3的倍数。
bool finded;
string ans;
void dfs(int first, int value, string& str) {
if (finded) return;
if (first == str.size()) {
if (value % 3 == 0) {
finded = true;
ans = str;
}
return;
}
if (str[first] != '?') {
if (first > 0 && str[first] == str[first - 1]) return;
dfs(first + 1, value + (str[first] - '0'), str);
}
else {
for (char ch = '0'; ch <= '9'; ++ch) {
if (first == 0 && ch == '0') continue;
if (first > 1 && ch == str[first - 1]) continue;
str[first] = ch;
dfs(first + 1, value + str[first] - '0', str);
}
}
}
void solve() {
string str; cin >> str;
if (str.size() == 1) {
cout << 3 << endl;
return;
}
dfs(0, 0, str);
cout << ans << endl;
}
2. 对于一个颜色，我们 只需要构建一个数组 preSum1, 对于 区间[L, R] 填充 1号色，只需 preSum1[L] += 1, preSum1[R + 1] -= 1；所有的颜色染完后，求preSum的前缀和，则第 i 个位置的值含义为：该点被染色的次数。对另一种颜色，也可以利用该方法解决。但是该问题一个核心点在于，区间范围[1, 1e9]，我们定义的数组开不了这么大，怎么办？其实，这里可以采用离散化的技术来解决。
#define complete_unique(a) a.erase(unique(begin(a),end(a)),end(a))
void solve() {
int n, p, q; cin >> n >> p >> q;
vector<int>l(n), r(n), c(n);
vector<int> allNum;
for (int i = 0; i < n; ++i) {
cin >> l[i];
if (l[i] > 1) allNum.emplace_back(l[i] - 1);
allNum.emplace_back(l[i]);
allNum.emplace_back(l[i] + 1);
}
for (int i = 0; i < n; ++i) {
cin >> r[i];
if (r[i] > 1) allNum.emplace_back(r[i] - 1);
allNum.emplace_back(r[i]);
allNum.emplace_back(r[i] + 1);
}
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
sort(all(allNum));
complete_unique(allNum);
unordered_map<int, int> idx, ridx;
for (int i = 0; i < allNum.size(); ++i) {
idx[allNum[i]] = i + 1;
ridx[i + 1] = allNum[i];
}
vector<int> preSum1(allNum.size() + 1, 0);
vector<int> preSum2(allNum.size() + 1, 0);
for (int i = 0; i < n; ++i) {
int left = l[i], right = r[i], color = c[i];
left = idx[left]; right = idx[right];
auto& pre = color == 1 ? preSum1 : preSum2;
pre[left] += 1; pre[right + 1] -= 1;
}
int ans = 0;
int color1 = preSum1[0], color2 = preSum2[0];
for (int i = 1; i < allNum.size(); ++i) {
int cha = ridx[i] - ridx[i - 1];
if (color1 >= p && color2 >= q) {
ans += cha;
}
color1 += preSum1[i]; color2 += preSum2[i];
}
cout << ans << endl;
}
类似资料：