周賽第三題
今天清醒一點血寫出來了
當天是結束後五分鐘寫了個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