第 89 场双周赛复盘

最后一题尚未解决

二的幂数组中查询范围内的乘积

关键在于：求出power数组，power数组存放一个数的二进制分解结果

1
2
3
4
5
int ind=0;
for (int i = 0; i <= MAXP; i++){
	if (n >> i & 1)
        power[ind++]=1<<i;
}

最小化数组中的最大值

最小化最大值 —> 二分答案

二分答案的模板

1
2
3
4
5
6
7
while(l<=r){
    mid=(l+r)>>1;
    if(check(mid))
        ans=mid,r=mid-1;
   	else
        l=mid+1;
}
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
class Solution {
    public int minimizeArrayValue(int[] nums) {
        int left=0;
        int right=1000000000;
        int ans=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(check(nums,mid)){
                ans=mid;
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return ans;
    }
    boolean check(int nums[],int limit){
        long copy[]=new long[nums.length];
        for(int i=0;i<nums.length;i++){
            copy[i]=nums[i];
        }
        //int[] copy=Arrays.copyOf(nums,nums.length);
        for(int i=nums.length-1;i>0;i--){
            if(copy[i]>limit){
                copy[i-1]=copy[i-1]-limit+copy[i];
                copy[i]=limit;
            }
        }
        if(copy[0]<=limit){
            return true;
        }else{
            return false;
        }
    }
}

类似的题

2187. 完成旅途的最少时间

2440. 创建价值相同的连通块

有点难，先放一下

关键：学会统计子树的大小/统计子树的点权和

思路：

  • 首先一个明显的性质，s=sum(nums)，如果要把树分成权值和相同的x个连通块，那么s能整除x。
  • 那么考虑枚举每个连通块的权值和i，如果能整除，那么尝试分成s//i块，删除的边数就是s//i - 1 【因为题目给出的是一棵树】。
  • 问题就是如何尝试分成s//i块，且每块权值和是i。
  • 那么按照灵神给出的计算子树权值和模板,我们试图让每个子树的价值是i。
  • 显然，如果子树和超过i，不合法，可以提前返回，我们用-1标志它不合法。
  • 如果子树和正好是i，那么剪掉这颗子树即可，返回0。
  • 最后检查根节点所在的连通块是0即可。

如果一颗子树的价值等于target，那么可以将其作为一个连通块，和其父节点断开，换句话说，它对其祖先节点的价值贡献是0。

DFS这棵树，统计子树的价值：

如果价值超过target，那么当前删边方案不合法，返回 −1。
如果价值等于target，找到了一个连通块，和其父节点断开，返回 0。
如果价值小于target，尚未找到一个完整的连通块，返回价值。
如果 DFS 完了没有返回−1，则当前删边方案合法。如果从大到小枚举连通块的个数，则此时可以直接返回答案。

1
2
3
4
5
6
7
8
9
10
11
private int dfs(int x, int fa) {
    var sum = nums[x]; // 价值
    for (var y : g[x])
        if (y != fa) {
            var res = dfs(y, x);
            if (res < 0) return -1;
            sum += res;
        }
    if (sum > target) return -1;
    return sum < target ? sum : 0;
}