字节提前批卷3

90分钟3道编程题
1、T组样例，计算整数1~n二进制表示中1的个数（T<=100，n<=1e7）

// 比较一般的方法，大概不能全过
1、预处理：n最高位为i（最右边为第一位），则小于2^(i-1)的数二进制表示中1个数和：dp[i] = 2*dp[i-1]+(1<<(i-1))，dp[1] = 0，i <= 24
解释：最高位为i+1，则i位为0，有dp[i-1]个1，i位为1，有dp[i-1]+(1<<(i-1))
2、对 k （(1<<(hBit(n)-1)) ~ n）进行二进制中1的计数 s（logk，还是太过耗时！！！）
3、return s + dp[hBit(n)]
// 正确解法
对1~1e7先做预处理，遵循两点规则：
1、奇数比前面的偶数多一个1
2、偶数和偶数的一半1的个数相同

2、一个整数数组A（有正有负），A[i]可选可不选，但必须确保相邻的两个数不同时选，问可选的最大和？

// 过97.35%，反例[2 1 1 2]
先找到每个由负数隔开的整数区间，然后对奇数位和偶数为分别求和，取二者较大者即可，累积的区间最大值即为所求最大和。
// 正确方法
dp[i]：表示[0~i]区间可获得的最大收益
dp[i] = max{dp[i-2]+nums[i], dp[i-1]}, dp[0]=nums[0], dp[1]=max{nums[1], nums[0]}

3、一个正整数能分成三个正整数的乘积最大和（n<=1e4）

// 100%
使三个数最接近即可，n/3，余数尽可能均分