本场周赛细节题比较多,整体难度其实不是很大,一共做出来两题,排名740+。

后三题都挺有意思的。

第二题:

大餐计数

本质上是一个two sum的变形题,也就是有多个target,在本题中就是多个2次幂,比赛的时候因为范围给定,事先枚举好就行。

class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
c = Counter(deliciousness)
res = 0
hh = [1,2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648]
nums = c.keys()
mp = {}
for num in nums:
for h in hh:
if h - num in mp.keys():
if num == h-num:
res += (c[num] * (c[num]-1)) // 2 # 若相同就是自身组合
else:
res += (c[num] * c[h-num])

mp[num] = 0

return (res) % int(1e9 + 7)

第三题:

将数组分成三个子数组的方案数

这个题是一个裸的前缀和+二分,边界的取值很恶心,比赛的时候一发dfs直接超时,最后抄别人的的题解

class Solution:
def waysToSplit(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
pre = list(accumulate(nums))
ans = 0
for i in range(n):
l = max(i+1,bisect_left(pre,pre[i]+pre[i]))
r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))
ans = (ans + max(0,r - l)) % mod
return ans % mod
class Solution {
public:
int waysToSplit(vector<int>& nums) {
int mod = 1e9 + 7;
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + nums[i - 1];
int res = 0;
for (int i = 3, j = 2, k = 2; i <= n; i ++ ) {
while (s[n] - s[i - 1] < s[i - 1] - s[j - 1]) j ++ ;
while (k + 1 < i && s[k] <= s[i - 1] - s[k]) k ++ ;
if (j <= k && s[n] - s[i - 1] >= s[i - 1] - s[j - 1] && s[k - 1] <= s[i - 1] - s[k - 1])
res = (res + k - j + 1) % mod;
}
return res;
}
};

第四题

得到子序列的最少操作次数

是一个LIS的变种,这里抄了浩哥一个nlogn的解法,以后一定要记住


def CeilIndex(A, l, r, key):

while (r - l > 1):

m = l + (r - l)//2
if (A[m] >= key):
r = m
else:
l = m
return r

def LongestIncreasingSubsequenceLength(A, size):

# Add boundary case,
# when array size is one

tailTable = [0 for i in range(size + 1)]
len = 0 # always points empty slot

tailTable[0] = A[0]
len = 1
for i in range(1, size):

if (A[i] < tailTable[0]):

# new smallest value
tailTable[0] = A[i]

elif (A[i] > tailTable[len-1]):

# A[i] wants to extend
# largest subsequence
tailTable[len] = A[i]
len+= 1

else:
# A[i] wants to be current
# end candidate of an existing
# subsequence. It will replace
# ceil value in tailTable
tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]


return len

class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
idxs = collections.defaultdict(list)
for i, v in enumerate(arr):
idxs[v].append(i)
k = []
# print(idxs)
for t in target:
k += idxs[t][::-1]
# print(k,'#')
n = LongestIncreasingSubsequenceLength(k, len(k))
return len(target) - n

$1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots+\frac{x^n}{n!} = e^{x}$

$\frac{x}{1!}+\frac{x^3}{3!}+\cdots+\frac{x^{2i+1}}{(2i+1)!} = \frac{e^x-e^{-x}}{2}$

$1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots+\frac{x^{2i}}{(2i)!} = \frac{e^x+e^{-x}}{2}$

$1+x+x^2+x^3+\cdots+x^n=\frac{1}{1-x}$

$1+x^2+x^4+\cdots+x^{2i}=\frac{1}{1-x^2}$