44双周赛好题分享

又是一场夜晚的比赛,这次在国际服参加,A了一题就哑火了,第二题,没想到怎么处理这些不能沟通的人,其实就是没想到贪心的策略,现在来分享一下。

5646. 需要教语言的最少人数

这个题蛮有意思,有n种语言,每个人会其中的一种或者多种,然后给你若干对friends,假如他们之间存在同样的语言那么就不会沟通出现问题,否则,沟通就会出现问题,需要再共同学习某门语言,这个题的难点就在于,如何去选择共同的学习的语言,刚开始想的是,将每一门语言会的人枚举出来,然后给某一类中添人,按照语言会的人的数量长度添加,但是这种策略没有考虑到朋友间的关系限制,其实是需要将这些人综合考虑,统计这些人中哪门语言会的人最多,然后让剩下的人学习这门语言即可。

  • 1.无需学习新语言的pair
  • 2.把无法沟通的pair的人放到一起,并统计,哪种语言会的人最多
  • 3.2的人数,减去,会的最多的人数,剩下的人学习这个最多的即可
class Solution:
def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
lan = [set(data) for data in languages]
dont = set()
for f in friendships:
u = f[0] - 1
v = f[1] - 1
if len(lan[u] & lan[v]) > 0: continue
else:
dont.add(u)
dont.add(v)
cnt = [0] * n
for p in dont:
for i in range(1,n+1):
if i in lan[p]:
cnt[i-1] += 1
if len(dont) == 0:
return 0
else:
return len(dont) - max(cnt)

5647. 解码异或后的排列

这个题还是非常的有意思啊,要充分利用题给出的性质,下面我们来推导一下:

首先原数组的元素我们用$a_i$表示,编码后的数组用$e_i$进行表示

由题意知:$a_i \oplus a_{i+1} = e_i$

我们有

$e_1 = (a_1 \oplus a_2)$

$e_1 \oplus e_2 = (a_1\oplus a_2)\oplus(a_2\oplus a_3)$ = $a_1 \oplus a_3$

$e_1 \oplus e_2 \oplus e_3 = (a_1\oplus a_2)\oplus(a_2\oplus a_3) (a_3\oplus a_4) = a_1 \oplus \ a_4$

$e_1 \oplus e_2 \oplus e_3 \cdots e_{n-1}=a_1 \oplus a_n$

将以上所有式子进行异或,可得

$e_1 \oplus e_3 \oplus e_5 \cdots e_{n-1}=a_2 \oplus a_3 \cdots a_n = M$

我们还有$a_1 \oplus a_2 \oplus a_3 \cdots a_n = C$

我们将$C\oplus M =a_1 $ 然后一次带回上面的式子,可以算出其他的$a$

class Solution {
public:
vector<int> decode(vector<int>& encoded) {
int n = encoded.size();
vector<int> pre(n+1,0);
for(int i= 1;i <= n;i++){
pre[i] = pre[i-1] ^ encoded[i-1];
}
int sum1 = 0;
for(int i = 1;i <= n+1;i++) sum1 ^= i;
int sum2 = 0;
for(int i = 0;i < n+1;i++){
sum2 = sum2 ^ pre[i]; // a1
}
vector<int> ans(n+1,0);
ans[0] = sum1 ^ sum2;
for(int i = 1;i <= n;i++){
ans[i] = pre[i] ^ ans[0];
}
return ans;
}
};

5648. 生成乘积数组的方案数

思路

代码:

import math


MOD = 10 ** 9 + 7


class Solution:

@staticmethod
def getPrimes(n):
primes = []
for i in range(2, n):
for j in range(2, i):
if (i % j == 0):
break
primes.append(i)
return primes

def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
result = []

primes = self.getPrimes(100)

for query in queries:
n, k = query
ways = 1
for prime in primes:
if prime > k:
break
cnt = 0
while k % prime == 0:
# 尝试用 prime 分解 k
cnt += 1
k /= prime
ways *= math.comb(n + cnt - 1, cnt)

if k > 1:
# 如果最后 k > 1,那么说明 k 无法进一步被分解
# 此时 k 是一个比较大的质数,比如 2377
# 只要把 k 放在 n 个格子的任意一个位置,所以有 n 种放法
ways = ways * n
result.append(ways % MOD)
return result