腾讯3.31 笔试AK C++题解

评价是都是常规mid,昨晚做美团笔试做的道心破碎

T3 并查集

使用并查集划分得到数个连通域,连通域的数量应为2.

仅建立一次连接就可以使得整个联通的连接数等于 第一个连通域内点数乘以第二个连通域内的点数.

class UnionFind{
private:
    vector<int>parents;
    vector<int>ranks;
    long long summary;

public:
    unordered_map<int,int>mp;
    UnionFind(int max_size):
            parents(max_size),
            ranks(max_size){
        for(int i=0;i<max_size;i++){
            parents[i] = i;
            mp[i] = 1;
        }
    }
    int find(int x){
        return x==parents[x] ? x : (find(parents[x]));
    }
    void to_union(int x1,int x2){
        int f1 = find(x1);
        int f2 = find(x2);
        if(f1 == f2){
            return;
        }
        summary -= mp[f1]*mp[f2];
        if(ranks[f1] > ranks[f2]){
            parents[f2] = f1;
            mp[f1] +=mp[f2];
            mp.erase(f2);
        } else{
            parents[f1] = f2;
            mp[f2] += mp[f1];
            mp.erase(f1);
            if(ranks[f1] == ranks[f2]){
                ranks[f2]++;
            }
        }
    }
    bool isConnected(int x,int y){
        return find(x) == find(y);
    }
};

int main() {
    int n,m;
    cin >> n >> m;
    int u,v;
    UnionFind uf(n);
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        uf.to_union(u - 1, v - 1);
    }
    if(uf.mp.size() > 2){
        cout << 0 << endl;
        return 0;
    }
    vector<int>nums;
    for(const auto &p : uf.mp){
        nums.emplace_back(p.second);
    }
    cout << nums[0] * nums[1] << endl;
}

T4 前缀异或和 + 动态规划

这个题的数量级在400,感觉不用前缀和,暴力求异或和也能过.

int main() {
    long long n,k;
    cin >> n >> k;
    vector<long long >nums(n);
    long long val;
    for(int i = 0; i < n; i++){
        cin >> val;
        nums[i] = val;
    }
    vector<long long>prefix(n,0);
    long long sum = 0;
    for(int i = 0; i < nums.size(); i++){
        sum ^= nums[i];
        prefix[i] = sum;
    }
    // [j-i]的前缀异或和 = prefix[j] ^ prefix[i]
    vector<vector<long long> >dp(k + 1,vector<long long>(n,0ll));
    // dp[i][j] 表示 分了i段时,以下标 j 结尾的 最大和
    // dp[i][j] =  max(dp[i-1][m] + (prefix[j] ^ prefix[m]) ) m∈[0,j-1]
    for(int j = 0;j < dp[0].size();j++){
        dp[1][j] = prefix[j];
    }
    for(int i = 2 ; i < dp.size(); i++){
        for(int j = i-1; j < dp[0].size(); j++){
            long long cur = 0;
            for(int m = j-1; m >= 0; m--){
                cur = max(cur,dp[i-1][m] + (prefix[j] ^ prefix[m]) );
            }
            dp[i][j] = cur;
        }
    }
    cout << dp[k][n-1] << endl;
}

T5 dfs

dfs + 回溯 LC79

int main() {
    int n,m;
    cin >> n >> m;
    vector<string>grid(n);
    for(int i = 0; i < n; i++){
        string str;
        cin >> str;
        grid[i] = str;
    }
    string target = "tencent";
    int cnt = 0;
    auto isValid = [&](int i,int j){
        return i >=0 && i < grid.size() && j >= 0 && j < grid[0].size() ;
    };
    function<void(int,int,int)> dfs = [&](int i,int j,int id)->void {
        if(!isValid(i,j)  || grid[i][j] != target[id]){
            return ;
        }
        if(id == target.size()-1){
            cnt++;
            return;
        }
        dfs(i+1,j,id+1); // 下
        dfs(i-1,j,id+1); // 上
        dfs(i,j+1,id+1); // 右
        dfs(i,j-1,id+1); // 左
    };
    for(int i = 0 ; i < grid.size(); i++){
        for(int j = 0; j < grid[0].size(); j++){
            dfs(i,j,0);
        }
    }
    cout << cnt << endl;
}

#实习，投递多份简历没人回复怎么办#