牛客周赛 Round 27

img

总而言之，我讨厌这种核心代码模式

小红的二进制删数字

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minCnt(string s) {
        // write code here
        int num=0;
        for(auto c:s){
            if(c=='1')num++;
        }
        return max(num-1,0);
    }
};

嘤嘤的新平衡树

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
class Solution 
{
public:
    int mod = 1e9+7;
    int getTreeSum(TreeNode* tree) 
    {
        if(tree->left==nullptr&&tree->right==nullptr)
        //末尾直接赋值为1
        //并返回
        {
            tree->val=1;
            return 1;
        }
        //取左子树
        //取右子树
        //比较大小
        //并返回大的*2+1
        //注意取模
        int x = getTreeSum(tree->left);
        int y = getTreeSum(tree->right);
        if(tree->left->val >tree->right->val){
            tree->val = tree->left->val+1;
            return (x*2+1)%mod;
        }
        else{
            tree->val = tree->right->val +1;
            return (y*2+1)%mod;
        }
    }
};

连续子数组数量

亲爱的滑窗

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
class Solution {
public:
    
    int getSubarrayNum(vector<int>& a, int x) {
        int n=a.size();
        vector<int>sum1(n+1);
        vector<int>sum2(n+1);
        for(int j=0;j<n;j++){
            int i=j+1;
            while(a[j]%2==0){
                sum1[i]+=1;
                a[j]/=2;
            }
            //记录2的个数
            while(a[j]%5==0){
                sum2[i]+=1;
                a[j]/=5;
            }
        }
        //记录5的个数
        for(int i=1;i<=n;i++){
            sum1[i]+=sum1[i-1];
            sum2[i]+=sum2[i-1];
        }
        //前缀和
        int posi=1;
        int posj=1;
        int ans=0;
        int mod = 1e9+7;
        while(posi<=n&&posj<=n)
        {
            while(posi>posj)
                posj++;           
            if(min(sum1[posj]-sum1[posi-1],sum2[posj]-sum2[posi-1])>=x)
            {
                ans+=(n-posj+1)%mod;
                ans%=mod;
                posi++;
            }
            else
            {
                posj++;
            }         
        }
        return ans;
    }
};

好矩阵

组合数学即可

注意到第一行第一列可以乱放，其他只需要放另一半即可

比较思维，不过会也可以一眼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int mod=1e9+7;
    int p(long long  m,long long n)
    {
        int a=1;
        while(n){
            if(n&1)a=1LL*a*m%mod;
            n>>=1;
            m=1LL*m*m%mod;
        }
        return a;
    }
    int numsOfGoodMatrix(int n, int m, int x)
    {
        return 1LL*p(x,n+m-1)*p(x/2,1LL*(n-1)*(m-1))%mod;
    }
};