526互联

第 360 场周赛 （二进制枚举、树上倍增）

发布时间 2023-08-28 21:29:33作者: 深渊之巅

2833. 距离原点最远的点

 

本题要求最远的距离，所有‘_’必须全为左或全为右。利用前缀和的思想看看L多还是R多，最后加上_的数目就是答案。

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int n = moves.size();
        int tt = 0, lc = 0, rc = 0, tc = 0;
        for(auto it: moves) {
            if(it == '_') {
                tc ++ ;
                continue;
            } else if(it == 'L') {
                lc ++ ;
                tt -- ;
            } else {
                rc ++ ;
                tt ++ ;
            }
        }

        if(tt == 0) {
            return tc;
        } else {
            return abs(tt) + tc;
        }
    }
};



2834. 找出美丽数组的最小和

 一个简单的哈希表

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        long long cnt = 0, sum = 0;
        unordered_map<int, int> mp;
        for(int i = 1; ; i ++ ) {
            if(mp[i]) continue;
            sum += i, cnt ++ ;
            if(cnt == n) break;
            mp[target - i] ++ ;
        }

        return sum;
    }
};

 

2835. 使子序列的和等于目标的最少操作次数

 若nums的和大于target，由于可以不断除以2会变为1，所以此时一定是有解的。

从二进制的角度看问题，若target的第i位为0，则跳过

　　　　　　　　　　　 若target的第i为为1，则先看<= 2**i的数能否拼出target & mask， 其中mask为（2 ** （i + 1））-1。target&mask表示后i位。若能拼出，则不需要操作。若不　　　　　　　　   　　　　　　　　　　 能拼出则找出更大的2的次幂，将其分解为 2 ** i 

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        if sum(nums) < target:
            return -1
        
        cnt = Counter(nums)
        ans = s = i = 0

        while 1 << i <= target:
            s += cnt[1 << i] << i
            mask = (1 << (i + 1)) - 1
            i += 1
            if s >= target & mask:
                continue
            
            ans += 1
            while cnt[1 << i] == 0:
                ans += 1
                i += 1
        
        return ans

 

2836. 在传球游戏中最大化函数值

 

树上倍增算法 = 动态规划 + 二进制枚举、
f[i][j] 表示从第i个点开始，操作 2 ** j次到达的节点中路径的权值和。
节点信息转移方程：f[i][j] = f[f[i][j - 1]][j - 1]
 额外信息为： g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1]
class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        n = len(receiver)
        m = k.bit_length() - 1
        pa = [[(p, p)] + [None] * m for p in receiver]  //这里是记录两维信息

        for i in range(m):
            for x in range(n):
                p, s = pa[x][i]
                pp, ss = pa[p][i]
                pa[x][i + 1] = (pp, s + ss)
        

        ans = 0
        for i in range(n):
            x = sum = i
            for j in range(m + 1):
                if (k >> j) & 1:
                    x, s = pa[x][j]
                    sum += s
            ans = max(ans, sum)

        return ans