牛客周赛 27

牛客周赛 Round 27

A 小红的二进制删数字

2的幂为1个1加几个0，所以多余的1都要删除，找1的个数即可

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @return int整型*/int minCnt(string s) {// write code hereint cnt = count(s.begin() , s.end() , '1');if(cnt == 1)return 0;return cnt - 1;}
};

B 嘤嘤的新平衡树

从下往上，值为两个子节点的最大值*2+1

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param tree TreeNode类 * @return int整型*/int getTreeSum(TreeNode* tree) {// write code hereint mod = 1e9 + 7;function<long long(TreeNode*)> dfs = [&](TreeNode* u) -> long long{long long l = 0 , r = 0;if(u == nullptr)return 0;l = dfs(u-> left);r = dfs(u-> right);return 2 * max(l , r) + 1;};return dfs(tree)%mod;}
};

C 连续子数组数量

统计下2和5的数量，再用滑动窗口统计个数

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param a int整型vector * @param x int整型 * @return int整型*/int getSubarrayNum(vector<int>& a, int x) {#define ll long longconstexpr ll p = 1e9 + 7;int n = a.size();vector< int > c2( n, 0 );vector< int > c5( n, 0 );for( int i = 0; i < n; ++i ) {int x = a[ i ];while( x % 2 == 0 ) {x /= 2;++c2[ i ];}while( x % 5 == 0 ) {x /= 5;++c5[ i ];}}ll ans = 0;//区间内2和5的数量for( int i = 0, j = 0, n2 = 0, n5 = 0; i < n; ++i ) {//对于每个i,j到哪里可以满足while( j < n && min( n2, n5 ) < x ) {n2 += c2[ j ];n5 += c5[ j ];++j;}if( min( n2, n5 ) >= x ) {ans += n - j + 1;}n2 -= c2[ i ];n5 -= c5[ i ];}return ans % p;}
};

D 好矩阵

存存组合数学

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @param x int整型 * @return int整型*/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) {// write code herereturn 1LL*p(x,n+m-1)*p(x/2,1LL*(n-1)*(m-1))%mod;}
};

---