牛客周赛143-EF未补#

https://ac.nowcoder.com/acm/contest/134529#question

A-模拟

题意比较乱，实际上，直接输出1，n即可

1
x = int(input())
2
print(1,x)

B-counter

map后计数并加上是0的即可

1
from collections import Counter
2
n, m, x = map(int, input().split())
3
a = list(map(int, input().split()))
4
cnt = Counter(a)
5
ans = 0
6
for v in cnt.values():
7
    if v <= x:
8
        ans += 1
9
ans += (m - len(cnt))
10
print(ans)

C-质因数分解

题意：

给你x和y求x*y所有正因子的d**d和

题解：

分别分解x和y，合并质因数指数，利用合并后的质因数生成所有因子，求和即可

1
MOD = 10 ** 9 + 7
2
def fc(num):
3
    factors = {}
4
    d = 2
5
    while d * d <= num:
6
        if num % d == 0:
7
            cnt = 0
8
            while num % d == 0:
9
                num //= d
10
                cnt += 1
11
            factors[d] = factors.get(d, 0) + cnt
12
        d += 1 if d == 2 else 2
13
    if num > 1:
14
        factors[num] = factors.get(num, 0) + 1
15
    return factors
16
def get_factors(factors):
17
    res = [1]
18
    for p, e in factors.items():
19
        new = []
20
        for f in res:
21
            mul = 1
22
            for _ in range(e + 1):
23
                new.append(f * mul)
24
                mul *= p
25
        res = new
26
    return res
27
x, y = map(int, input().split())
28
fac_x = fc(x)
29
fac_y = fc(y)
30
for p, e in fac_y.items():
31
    fac_x[p] = fac_x.get(p, 0) + e
32
c = get_factors(fac_x)
33
ans = 0
34
for d in c:
35
    ans = (ans + pow(d, d, MOD)) % MOD
36
print(ans)

D-差分

题意：

有一些区间，选择一个长度为K的区间，使得与这个区间相交的给定区间的数量最多

题解：

对于给定区间 $[l_i, r_i]$ 与 $[L, L+k]$ 相交，等价于：

[l_i, r_i] \cap [L, L+k] \neq \varnothing

即：

L \le r_i \quad \text{且} \quad L+k \ge l_i

即：

L \in [l_i - k, r_i]

因此，区间 $[l_i, r_i]$ 能与 $[L, L+k]$ 相交的 $L$ 的范围是 $[l_i - k, r_i]$

每个给定区间对应一个 $L$ 的可选区间 $[l_i - k, r_i]$ 。我们要求一个点 $L$ 被最多的这样的区间覆盖。

转换为一维区间最大重叠问题：给定若干区间 $[l_i - k, r_i]$ ，求一个点被覆盖的最大次数。

1
n, k = map(int, input().split())
2
g = []
3
for _ in range(n):
4
    l, r = map(int, input().split())
5
    g.append((l - k, 1))
6
    g.append((r + 1, -1))
7
g.sort()
8
cur = 0
9
ans = 0
10
for _, d in g:
11
    cur += d
12
    ans = max(ans, cur)
13
print(ans)

E：状压DP+轮廓线+并查集

F：动态规划+线段树+坐标压缩

音乐

音乐

牛客周赛143-EF未补#

文章分享

音乐

目录

音乐

音乐

[算法训练] 牛客周赛143①质因数分解/差分/状压DP②轮廓线+并查集/动态规划+线段树+坐标压缩

牛客周赛143-EF未补#

文章分享

音乐

目录