[acwing周赛复盘] 第 93 场周赛20230304

一、本周周赛总结

• 彩笔了，只AC一题。
• T1模拟，整除向上取整。
• T2 BFS。这题应该是能AC的，但是一直TLE，就是样例都TLE，特判了也TLE。最后发现把前边一堆import删了就ac了。。看来import是加时间的。
• T3 分治/01字典树/异或字典树。
• 

二、 4867. 整除数

链接: 4867. 整除数

1. 题目描述

2. 思路分析

• 题目要求整除，且大于n，即最小是n+1的能整除k的数。显然是ceil((n+1) / 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且n==1的情况
• 其它情况只要n<len(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, nums=None, bit_len=31):# 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_len=30)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()

六、参考链接

• 无