周賽第三題 今天清醒一點血寫出來了 當天是結束後五分鐘寫了個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 -- ※ 發信站: 批踢踢實業坊(ptt-site.org.tw), 來自: 125.229.37.69 (臺灣) ※ 文章網址: https://ptt-site.org.tw/Marginalman/M.1731341325.A.D5E