河西网站建设制作,广州公司注册地址提供,桂林旅游网站制作公司,怎样维护网站建设[acwing周赛复盘] 第 93 场周赛20230304 一、本周周赛总结二、 4867. 整除数1. 题目描述2. 思路分析3. 代码实现三、 4868. 数字替换1. 题目描述2. 思路分析3. 代码实现四、4869. 异或值1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
彩笔了#xff0c;只A…
[acwing周赛复盘] 第 93 场周赛20230304 一、本周周赛总结二、 4867. 整除数1. 题目描述2. 思路分析3. 代码实现三、 4868. 数字替换1. 题目描述2. 思路分析3. 代码实现四、4869. 异或值1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
彩笔了只AC一题。T1模拟整除向上取整。T2 BFS。这题应该是能AC的但是一直TLE就是样例都TLE特判了也TLE。最后发现把前边一堆import删了就ac了。。看来import是加时间的。T3 分治/01字典树/异或字典树。
二、 4867. 整除数
链接: 4867. 整除数
1. 题目描述 2. 思路分析
题目要求整除且大于n即最小是n1的能整除k的数。显然是ceil((n1) / k)
3. 代码实现
# Problem: 整除数
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4870/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sysRI lambda: map(int, sys.stdin.buffer.readline().split())# ms
def solve():n, k RI()n 1print((n k - 1) // k * k)if __name__ __main__:solve()三、 4868. 数字替换
链接: 4868. 数字替换
1. 题目描述 2. 思路分析
这题的教训是如果在acw卡常先把import都删干净
看完题应该立刻想到一些特例然后BFS即可。特例如果x是0或者1那么n只能是1否则返回-1.如果x里有0那么可以一步到一位数。只有0才能让数字位数变小且只能变到一位特判一下存在0且n1的情况其它情况只要nlen(x) 一定无解。然后bfs即可。
3. 代码实现
# Problem: 数字替换
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4871/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
from collections import *RI lambda: map(int, sys.stdin.buffer.readline().split())
RS lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST lambda: list(RI())
DEBUG lambda *x: sys.stderr.write(f{str(x)}\n)# ms
def solve():n, x RI()ans 0s str(x)if len(s) n:return print(0)if 0 in s and n 1:return print(1)if n len(s):return print(-1)if max(s) 1:return print(-1)q deque([x])vis {x}while q:ans 1for _ in range(len(q)):x q.popleft()s str(x)for i in s:y x * int(i)if len(str(y)) n:return print(ans)if y not in vis:vis.add(y)q.append(y)print(-1)if __name__ __main__:solve()四、4869. 异或值
链接: 4869. 异或值
1. 题目描述 2. 思路分析
这题01字典树或者分治都可以。其实应该立刻想到01字典树的因为是批量异或的最大值问题。假设我们要异或的数字是x最终得到最大值是mx。建完树后从高位向下逐层考虑 如果本层里只有1那可以让x这一位是1则mx的这一位可以是0。那么我们往1走返回递归后的结果即可。如果只有0同理。往0走即可。如果01都有那么x这位无论是几mx这位都会取到1那么我们往01走都要试一下取那个最小的别忘记加上本层的1。 恶心之处在于做这题时用封装版的TLE了拆出来后才过的但也7000ms。 试了下直接分治是更快的。1700ms。直接按位考虑把数字按本位01分组。讨论方法同上。 若只有1的组那就递归1即可。若只有0的组递归0即可。若都有则mx这位必是1递归两边取最小。
3. 代码实现
# Problem: 异或值
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4872/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sysRI lambda: map(int, sys.stdin.buffer.readline().split())
RS lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST lambda: list(RI())
DEBUG lambda *x: sys.stderr.write(f{str(x)}\n)MOD 10 ** 9 7
PROBLEM
class TrieXor:def __init__(self, numsNone, bit_len31):# 01字典树用来处理异或最值问题本模板只处理数字最低的31位# 用nums初始化字典树可以为空self.trie {}self.cnt 0 # 字典树插入了几个值if nums:for a in nums:self.insert(a)self.bit_len bit_lendef insert(self, num):# 01字典树插入一个数字num,只会处理最低bit_len位。cur self.triefor i in range(self.bit_len - 1, -1, -1):nxt (num i) 1if nxt not in cur:cur[nxt] {}cur cur[nxt]cur[3] cur.get(3, 0) 1 # 这个节点被经过了几次cur[5] num # 记录这个数:#或者end等非01的当key都行;这里由于key只有01因此用5self.cnt 1def find_max_xor_num(self, num):# 计算01字典树里任意数字异或num的最大值,只会处理最低bit_len位。# 贪心的从高位开始处理显然num的某位是0对应的优先应取1相反同理cur self.trieret 0for i in range(self.bit_len - 1, -1, -1):if (num i) 1 0: # 如果本位是0那么取1才最大取不到1才取0if 1 in cur:cur cur[1]ret ret 1else:cur cur.get(0, {})ret 1else:if 0 in cur:cur cur[0]ret ret 1else:cur cur.get(1, {})ret 1return retdef find_max_xor_any(self):计算所有数字异或异或同一数字x时结果里max的最小值def dfs(cur, bit): # 计算当前层以下能取到的最小的最大值if bit 0:return 0if 0 not in cur: # 如果这层都是1那么可以使x的这层是1结果里的这层就是0递归下一层即可。return dfs(cur[1], bit - 1)elif 1 not in cur: # 如果这层都是0使x这层是0递归下一层。return dfs(cur[0], bit - 1)# 如果01都有那么x这层不管是几结果最大值里这层都是1那么考虑走1还是走0方向取min后加上本层的值。return min(dfs(cur[0], bit - 1), dfs(cur[1], bit - 1)) (1 bit)return dfs(self.trie, self.bit_len - 1)def count_less_than_limit_xor_num(self, num, limit):# 计算01字典树里有多少数字异或num后小于limit# 由于计算的是严格小于因此只需要计算三种情况:# 1.当limit对应位是1且异或值为0的子树部分全部贡献。# 2.当limit对应位是1且异或值为1的子树部分向后检查。# 3.当limit对应为是0且异或值为0的子树部分向后检查。# 若向后检查取不到直接剪枝breakcur self.trieans 0for i in range(self.bit_len - 1, -1, -1):a, b (num i) 1, (limit i) 1if b 1:if a 0:if 0 in cur: # 右子树上所有值异或1都是0一定小于1ans cur[0][3]cur cur.get(1) # 继续检查右子树if not cur: break # 如果没有1即没有右子树可以直接跳出了if a 1:if 1 in cur: # 右子树上所有值异或1都是0一定小于1ans cur[1][3]cur cur.get(0) # 继续检查左子树if not cur: break # 如果没有0即没有左子树可以直接跳出了else:cur cur.get(a) # limit是0因此只需要检查异或和为0的子树if not cur: break # 如果没有相同边的子树即等于0的子树可以直接跳出了return ans# 封装成类卡常真是吐了 ms
def solve_tle():n, RI()a RILST()trie TrieXor(bit_len30)for x in a:trie.insert(x)ans trie.find_max_xor_any()print(ans)# 7224 ms
def solve1():n, RI()a RILST()trie {}for x in a:cur triefor i in range(29, -1, -1):nxt (x i) 1if nxt not in cur:cur[nxt] {}cur cur[nxt]def dfs(cur, bit): # 计算当前层以下能取到的最小的最大值if bit 0:return 0if 0 not in cur: # 如果这层都是1那么可以使x的这层是1结果里的这层就是0递归下一层即可。return dfs(cur[1], bit - 1)elif 1 not in cur: # 如果这层都是0使x这层是0递归下一层。return dfs(cur[0], bit - 1)# 如果01都有那么x这层不管是几结果最大值里这层都是1那么考虑走1还是走0方向取min后加上本层的值。return min(dfs(cur[0], bit - 1), dfs(cur[1], bit - 1)) (1 bit)ans dfs(trie, 29)print(ans)# 1725 ms
def solve():n, RI()a set(RILST())def dfs(a, bit): # 计算当前层以下能取到的最小的最大值if bit 0:return 0x, y [], []t 1 bitfor v in a:if v t:x.append(v)else:y.append(v)if not x: return dfs(y, bit - 1)if not y: return dfs(x, bit - 1)# 如果01都有那么x这层不管是几结果最大值里这层都是1那么考虑走1还是走0方向取min后加上本层的值。return min(dfs(x, bit - 1), dfs(y, bit - 1)) tprint(dfs(a, 29))if __name__ __main__:solve()
六、参考链接
无
