第 188 场周赛

Posted on | In , | |
Words count in article: 793 | Reading time ≈ 4

5404. 用栈操作构建数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> ret;
        int z = 0;
        for(int i=1; i<=n; i++) {
            if(z == target.size())
                break;
            if(target[z] == i) {
                ret.push_back("Push");
                z++;
            } else {
                ret.push_back("Push");
                ret.push_back("Pop");
            }
        }
        return ret;
    }
};

5405. 形成两个异或相等数组的三元组数目

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 countTriplets(vector<int>& arr) {
        for(int i=1; i<arr.size(); i++) {
            arr[i] ^= arr[i-1];
        }
        int res = 0;
        for(int i=0; i<arr.size()-1; i++) {
            for(int j=i+1; j<arr.size(); j++) {
                for(int k=j; k<arr.size(); k++) {
                    int a = 0, b = 0;
                    if(i == 0) {
                        a = arr[j-1];
                    } else {
                        a = arr[j-1] ^ arr[i-1];
                    }
                    b = arr[k] ^ arr[j-1];
                    if(a == b) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

5406. 收集树上所有苹果的最少时间

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
39
40
class Solution {
private:
    vector<vector<int>> edges;
    vector<bool> has;
    int ans;
        
public:
    void dfs1(int u, int fa) {
        for (int v: edges[u]) {
            if (v != fa) {
                dfs1(v, u);
                has[u] = has[u] | has[v];
            }
        }
    }
    
    void dfs2(int u, int fa) {
        for (int v: edges[u]) {
            if (v != fa && has[v]) {
                ++ans;
                dfs2(v, u);
                ++ans;
            }
        }
    }
    
    int minTime(int n, vector<vector<int>>& _edges, vector<bool>& hasApple) {
        edges.resize(n);
        has = hasApple;
        for (const auto& e: _edges) {
            edges[e[0]].push_back(e[1]);
            edges[e[1]].push_back(e[0]);
        }
        dfs1(0, -1);
        
        ans = 0;
        dfs2(0, -1);
        return ans;
    }
};

5407. 切披萨的方案数

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define ll long long int

class Solution {
public:

    const ll mod=1e9+7;
    int ways(vector<string>& pizza, int k) {
        int row=pizza.size(),col=pizza[0].length();
        //计算num
        vector<vector<int>> num(row,vector<int>(col,0));
        if(pizza[0][0]=='A') num[0][0]=1;
        for(int i=1;i<row;i++) num[i][0]=num[i-1][0]+(pizza[i][0]=='A');
        for(int i=1;i<col;i++) num[0][i]=num[0][i-1]+(pizza[0][i]=='A');
        for(int i=1;i<row;i++) for(int j=1;j<col;j++)
                num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+(pizza[i][j]=='A');
            
        //初始化dp
        vector<vector<vector<ll>>> dp(row,vector<vector<ll>>(col,vector<ll>(k+1,0)));
        dp[0][0][1]=1;

        //从k=2开始填充
        for(int x=2;x<=k;x++){
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    //dp为0代表不存在这种情况
                    if(dp[i][j][x-1]==0)
                        continue;
                    //穷举水平切
                    for(int z=i+1;z<row;z++){
                        if(hasA(num,i,j,z-1,col-1) && hasA(num,z,j,row-1,col-1)){
                            dp[z][j][x]+=dp[i][j][x-1];
                            dp[z][j][x]%=mod;
                        }
                    }
                    //穷举垂直切
                    for(int z=j+1;z<col;z++){
                        if(hasA(num,i,j,row-1,z-1) && hasA(num,i,z,row-1,col-1)){
                            dp[i][z][x]+=dp[i][j][x-1];
                           dp[i][z][x]%=mod;
                        }
                    }
                }
            }
        }
            
        //计算答案
        ll ans=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ans+=dp[i][j][k];
            }
            ans%=mod;
        }
        return ans;
    }
        
    //计算存在A吗
    bool hasA(vector<vector<int>>& num,int sr,int sc,int er,int ec){
        int num1=0,num2=0,num3=0,res;
        if(sr!=0 && sc!=0) num1=num[sr-1][sc-1];
        if(sr!=0) num2=num[sr-1][ec];
        if(sc!=0) num3=num[er][sc-1];
        return num[er][ec]-num2-num3+num1>0;
    }
};
Donate? comment?