Weekly Contest 160

Posted on | In , | |
Words count in article: 626 | Reading time ≈ 3

1237. Find Positive Integer Solution for a Given Equation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> ret;
        for(int i=1; i<=1000; i++){
            int flag = 0;
            for(int j=1; j<=1000; j++){
                if(customfunction.f(i,j) == z){
                    vector<int> cur;
                    cur.push_back(i);
                    cur.push_back(j);
                    ret.push_back(cur);
                }
                else if(customfunction.f(i,j) > z){
                    flag = 1;
                    break;
                }
            }
        }
        return ret;
    }
};

1238. Circular Permutation in Binary Representation

Gray code

https://cp-algorithms.com/algebra/gray-code.html

i ^ i >> 1 生成格雷码

start ^ i ^ i >> 1 保证第一个和最后一个 只差一个bit

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> res;
        for (int i = 0; i < 1 << n; ++i)
            res.push_back(start ^ i ^ i >> 1);
        return res;
    }
};

1239. Maximum Length of a Concatenated String with Unique Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int res = 0;
    int maxLength(vector<string>& arr) {
        vector<int> key(arr.size(), 0);
        for(int i=0; i<arr.size(); i++){
            int key_ = 0;
            for(char c: arr[i]){
                if((key_ & (1<<(c-'a'))) != 0){
                    key_ = INT_MAX;
                    break;
                }
                key_ |= 1 << (c-'a');
            }
            key[i] = key_;
        }
        dfs(key, arr, 0 ,0 , 0);
        return res;
    }
    void dfs(vector<int>& key,vector<string>&arr, int idx, int len, int cur_key){
        res = max(res,len);
        for(int i = idx ; i < key.size() ; i++)
            if((key[i]!= INT_MAX) && (cur_key & key[i]) == 0)
                dfs(key,arr,i+1,len + arr[i].size(), cur_key | key[i]);
    }
};

1240. Tiling a Rectangle with the Fewest Squares

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<vector<int>> a;
    int tilingRectangle(int n, int m) {
        a = vector<vector<int>>(n, vector<int>(m));
        for(int i=1; ; i++){
            if(dfs(1, 0, n, m, i)) return i;
        }
        return 0;
    }
    bool dfs(int step, int cnt, int n, int m, int k){
        if(cnt == n * m) return true;
        if(step > k) return false;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j]) continue;
                for(int l=0; i+l<n && j+l<m && a[i][j+l]==0; l++){
                    for(int ii=0; ii<=l; ii++){
                        for(int jj=0; jj<=l; jj++){
                            a[i+ii][j+jj] = 1;
                        }
                    }   
                    if(dfs(step+1, cnt+(l+1)*(l+1), n, m, k)){
                        return true;
                    }
                    for(int ii=0; ii<=l; ii++){
                        for(int jj=0; jj<=l; jj++){
                            a[i+ii][j+jj] = 0;
                        }
                    }  
                }
                // you will have to fill the first empty cell you find, so if you haven't succeeded, you fail
                return false;
            }
        }
        return false;
    }
};
Donate? comment?