一、本周周赛总结
- 这周考的还行，4道题多多少少都要点数学。
- T1 计数+等差数列求和。
- T2 数论模板，由于质数数组开的不够RE一次。
- T3 分类讨论。
- T4 lca。
二、 [Easy] 6265. 统计相似字符串对的数目
1. 题目描述
2. 思路分析
- 题目只要求字符相同，不要求数量，因此set去重，然后排序来归类。
- 另外，灵神写法是状压，把26个字符压成26位表示出没出现即可。
3. 代码实现
class Solution:
def similarPairs(self, words: List[str]) -> int:
c = Counter()
for w in words:
c[''.join(sorted(set(w)))] += 1
ans = 0
for v in c.values():
ans += v*(v-1)//2
return ans
三、[Medium] 6266. 使用质因数之和替换后可以取到的最小值
1. 题目描述
2. 思路分析
幸好之前写了个取质因数的模板，直接复制过来按题意要求模拟。
- 理论上时间复杂度是开方n，注意记忆化写外边。
- 用欧拉筛预处理质数，然后对每个x分治质因数。
3. 代码实现
def tag_primes_euler(n): # 返回一个长度n+1的数组p，如果i是质数则p[i]=1否则p[i]=0
primes = [1]*(n+1)
primes[0] = primes[1] = 0 # 0和1不是质数
ps = [] # 记质数
for i in range(2,n+1):
if primes[i]:
ps.append(i)
for j in ps:
if j*i>n:
break
primes[j*i] = 0
if i%j == 0:break
# print(ps)
return primes
primes = tag_primes_euler(10**5+5)
@cache
def get_prime_reasons(x):
if x == 1:
return Counter()
if primes[x]:
return Counter([x])
for i in range(2,int(x**0.5)+1):
if x % i == 0:
return get_prime_reasons(i) + get_prime_reasons(x//i)
class Solution:
def smallestValue(self, n: int) -> int:
while n :
c = get_prime_reasons(n)
s = 0
for k,v in c.items():
s += k*v
if s == n:
return s
n = s
return n
四、[Medium] 6267. 添加边使所有节点度数都为偶数
1. 题目描述
2. 思路分析
- 直接分类讨论，注意题目提示中最后两个条件。即原图中没有自环和重边，且要求添加后的图也没有。
- 我们建图后统计原图中的点，有几个奇数度的点x，几个偶数度的点y，把它们分出来。
- 显然如果没有奇数（x==0）,则无需添加，返回True；如果x>=5,因为一条边最多影响2个点，因此仅用2条边无论如何也搞不定，return False.
- 如果x==1，那么这个仅有的点，连哪个点都不行，会使另外一个偶点的度+1变成奇数。return False。
- 同理如果x==3,至少要用一条边改变2个点，剩下一个点变成上一种情况。return False。
- 如果x==2,设这俩点是a,b
- 若ab不是本来就连着，就可以用一条边连起来，把它俩变偶度，且不影响其他边，return True。
- 若ab本来就是连着呢，考虑找一个原本的偶度点c，且不连接a,b,把a,b都连c,return True。
- 如果x==4,那么用两条边只能两两相连，找出任意匹配方式，即匹配的两点不互相连接即可。
3. 代码实现
class Solution:
def isPossible(self, n: int, edges: List[List[int]]) -> bool:
g = [set() for _ in range(n)]
for u,v in edges:
u-=1
v-=1
g[u].add(v)
g[v].add(u)
ji,ou = [],[]
for u in range(n):
if len(g[u]) & 1:
ji.append(u)
else:
ou.append(u)
if len(ji)>=5:
return False
if not ji :
return True
if len(ji)&1:
return False
if len(ji) == 2:
a,b = ji
if a not in g[b]:
return True
for u in ou:
if u not in g[a] and u not in g[b]:
return True
return False
if len(ji) == 4:
a,b,c,d = ji
if a not in g[b] and c not in g[d]:
return True
if a not in g[c] and b not in g[d]:
return True
if a not in g[d] and c not in g[b]:
return True
return False
五、[Hard] 6268. 查询树中环的长度
链接: 6268. 查询树中环的长度
1. 题目描述
2. 思路分析
- 比赛时看到lca吓一跳，因为确实没学会树上倍增，然后仔细看数据范围原来是完全二叉树：
- 那么树高不会超过30，每个询问分开向根节点走即可。
- 由于是完全二叉树，找父节点很方便；参考线段树的数组表示。
- 那么做法就是两个节点都向上走，找到第一个相同的祖宗节点，然后计算总距离+1即可。
- 实现时，令a<b，这样好考虑一些。
- 正经LCA做法，每次让更深的那个向上搜索。
3. 代码实现
正经LCA
class Solution:
def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
def calc(a,b):
ans = 1
while a!=b:
if a > b:
a,b = b,a
ans += 1
b //= 2
return ans
return [calc(a,b) for a,b in queries]
class Solution:
def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
m = len(queries)
ans = []
def calc(a,b):
if a > b:
a,b = b,a
s,p = set(),[]
while a:
s.add(a)
a //= 2
while b:
if b in s:
return len(p) + len([a for a in s if a>b])+1
p.append(b)
b //= 2
for a,b in queries:
ans.append(calc(a,b))
return ans
两个点同时走
class Solution:
def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
def calc(a,b):
if a > b:
a,b = b,a
s,p = set(),0
while b:
if a:
s.add(a)
a //= 2
if b in s:
return p + len([a for a in s if a>b])+1
p += 1
b //= 2
return p
return [calc(a,b) for a,b in queries]
六、参考链接
转载：https://blog.csdn.net/liuliangcan/article/details/128360776
查看评论