周赛第三题
今天清醒一点血写出来了
当天是结束后五分钟写了个MLE==
没有想到可以用value当维度来DP
所以当初preprocess花了太多空间
def sumOfGoodSubsequences(self, nums: List[int]) -> int:
mod = 10**9+7
cnt, s = defaultdict(int), defaultdict(int)
cnt[nums[0]] = 1
s[nums[0]] = nums[0]
for i in range(1, len(nums)):
cnt_cur = (cnt[nums[i]-1]+cnt[nums[i]+1]+1)
cnt[nums[i]] += cnt_cur
s[nums[i]] = (s[nums[i]] + s[nums[i]-1] + s[nums[i]+1] +
cnt_cur*nums[i]) % mod
ans = 0
for v in s.values():
ans = (ans + v) % mod
return ans
昨天的
妈的又臭又长
呕呕呕==
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
prefix_cnt = [[0 for _ in range(31)] for _ in range(len(nums)+1)] #
prefix_cnt[-1] = [0,...,0]
cur_cnt = [0 for _ in range(31)]
k_cnt = [0 for _ in range(31)]
bit = 0
kk = k
while kk>0:
k_cnt[bit] += (kk&1)
bit += 1
kk = kk>>1
for idx, num in enumerate(nums):
bit = 0
while num>0:
cur_cnt[bit] += (num&1)
bit += 1
num = num >> 1
prefix_cnt[idx] = cur_cnt[:]
def check(l):
if l==0:
return False
for i in range(l-1, len(nums)):
subarr_cnt = [a-b for a,b in zip(prefix_cnt[i], prefix_cnt[i-l])]
flag = True
for j in reversed(range(31)):
if subarr_cnt[j]>k_cnt[j] and k_cnt[j]==0:
flag = True
break
elif subarr_cnt[j]<k_cnt[j]:
flag = False
break
if flag:
return True
return False
# special case
tmp = 0
for num in nums:
tmp = tmp|num
if tmp<k:
return -1
# binary search
l,r = 0, len(nums)
while l<r:
mid = (l+r)//2
if check(mid):
r = mid
else:
l = mid+1
return l if l>0 else -1
今天的
也是binary search
还可
不过我直接开1000的质数表 感觉因为这样所以超慢==
但还是有过
def primeSubOperation(self, nums: List[int]) -> bool:
# preprocess
def isPrime(num):
for i in range(2, int(num**0.5)+1):
if num%i == 0:
return False
return True
prime_list = []
for num in range(2, 1001):
if isPrime(num):
prime_list.append(num)
pre = 0
for i in range(len(nums)):
if pre>=nums[i]:
return False
idx = bisect_left(prime_list, nums[i]-pre)
if idx>0:
nums[i] -= prime_list[idx-1]
pre = nums[i]
return True