第 1 场双周赛

第 1 场双周赛

A.

模拟

class Solution {
public:
    int fixedPoint(vector<int>& arr) {
        for(int i = 0; i < arr.size(); ++i)
            if(arr[i] == i) return i;
        return -1;
    }
};

B.

模拟，hash

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        unordered_map<string, int> mp;
        vector<vector<int>> res;
        for(auto& u : words) mp[u] = 1;
        for(int i = 0; i < text.size(); ++i) {
            string temp = "";
            for(int j = i; j < text.size(); ++j) {
                temp += text[j];
                if(mp.count(temp)) res.push_back({i, j});
            }
        }
        return res;
    }
};

C.

• 解法一：匈牙利算法，二分图的最大完美匹配KM算法
• 解法二：考查是否会全排列的剪枝
  众所周知：全排列有 n ! n! n!种， 10 ! 10! 10!是 3628800 3628800 3628800，可以通过本题
  但是如果爆搜不加剪枝的话是 1 0 10 10^{10} 1010，无法通过。
  

  
  加上二进制 b i t bit bit优化即可优化成为 10 ! 10! 10!。
  

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
    	w = workers;
    	b = bikes;
        int nb = b.size();
        memset(lo, -1, sizeof lo);
        for(int i = 0; i < nb; ++i)
            lo[1 << i] = i;
        res = 0x3f3f3f3f;
        int bit = (1 << nb) - 1;
        dfs(0, 0, bit);
        return res;
    }
    
private:
    vector<vector<int>> w;
    vector<vector<int>> b;
    int res;
    int lo[1024];
    
    void dfs(int u, int sum, int bit) {
        if(u == w.size()) {
            res = min(res, sum);
            return ;
        }
        
        int temp = bit;
        while(bit > 0) {
            int bi = bit & (-bit);
            dfs(u + 1, sum + abs(w[u][0] - b[lo[bi]][0]) + abs(w[u][1] - b[lo[bi]][1]), temp - bi);
            bit -= bi;
        }
    }
};

D.

数位 d p dp dp模板，也是较难的数位dp。

当前计算 x x x的个数，考虑 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i位数，已经有 j j j个为 x x x这个状态下的数的 x x x数的个数。

class Solution {
public:
    int digitsCount(int d, int low, int high) {
        return int(dp(high, d) - dp(low - 1, d));
    }
private:
    int f[30][30];
    int digit[30];
    
    long long dfs(bool lead, bool limit, int dep, int num, int cnt) {
        if(dep == 0) return cnt;
        if(lead && !limit && ~f[dep][cnt]) return f[dep][cnt];
        int last = limit ? digit[dep] : 9;
        
        long long res = 0;
        for(int i = 0; i <= last; ++i)
            res += dfs(lead | i, limit && i == digit[dep], dep - 1, num, cnt + ((lead | i) && i == num));
        if(lead && !limit) f[dep][cnt] = res;
        return res;
    }
    
    long long dp(int x, int d) {
        int g = 0;
        memset(f, -1, sizeof f);
        while(x > 0) digit[++g] = x % 10, x /= 10;
        // lead, limit, dep, num, cnt
        return dfs(false, true, g, d, 0);
    }
    
    
};