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