复盘｜第89场双周赛

2437. 有效时间的数目 https://leetcode.cn/problems/number-of-valid-clock-times/

【枚举】数据范围较小所以可以枚举。注意到小时的数字和分钟的数字是独立的，可以分开算再相乘。

2438. 二的幂数组中查询范围内的乘积 https://leetcode.cn/problems/range-product-queries-of-powers/

【位运算 + 模拟】题意要求把n转化为2的幂，相当于把n的二进制表示的每个1提取出来，可用lowbit完成此操作，然后模拟每个询问。

也可以用reduce写成一行。

【预处理】由于powers数组很短，可以预处理所有询问（打表），预处理所有2的幂次（不预处理的话就需要用pow()取模快速幂）。

此题也能用前缀积 + 求逆元 的解法，贴一下逆元求法https://zhuanlan.zhihu.com/p/378728642。

复习下常用lowbit：
x >> k & 1 求x的第k位数字
x & -x = x & (~x + 1) 保留x最右边的1，其余位置置0
x & (x - 1) 消除x最右边的1（最右边0变1），其余不变
x | (x + 1) 消除x最右边的0（最右边1变0），其余不变

2439. 最小化数组中的最大值 https://leetcode.cn/problems/minimize-maximum-of-array/

题意是每个数字可以把自己任意多的部分分给它左侧任意位置的数，求操作结束后数组最大值的最小为多少。

【二分】最小化数组的最大值，需要想到二分。只能右边的数匀到左边，所以从右边开始模拟，如果nums[i] > limit，nums[i - 1] += nums[i] - limit。

3.10的bisect支持key。

【贪心】由于后面元素可以把自己的值匀给前面的元素，所以枚举所有前缀的平均值即可，取最大值。

这里ceil(a/b)也可以写成(a + b - 1) // b。

2440. 创建价值相同的连通块 https://leetcode.cn/problems/create-components-with-same-value/

【DFS】dfs自底向上判断每颗子树的点权和是否等于target，如果找到和等于target则切断当前节点与父节点的连接，返回0，如果找到和大于target的子数则返回-1，小于target返回和，dfs没返回-1说明删除边操作合法。这些连通块价值相等，枚举连通块个数是i = sum // target（i是sum(nums)的因子），删除的边数是i-1。由于每个连通块的点权和大于等于max(nums)，所以枚举的上界可以为sum(nums) // max(nums)。