[牛客复盘] 牛客周赛round13 20230924

总结

• 竟然三题下班了，哭了。
• A模拟
• B乘法原理
• C分类讨论乘法原理
• D 最短路方案数，乘法原理
• E 贪心
• 

矩阵转置置

链接: [矩阵转置置

2. 思路分析

• 按题意模拟，翻转两次。

3. 代码实现

def solve():
    n, = RI()
    g = []
    for _ in range(n):
        g.append(RILST())
    for i,row in enumerate(g):
        g[i] = row[::-1]
    for j in range(n):
        l,r = 0,n-1
        while l < r:
            g[l][j],g[r][j] = g[r][j],g[l][j]
            l += 1
            r -= 1
    for row in g:
        print(*row)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

小红买基金

链接: 小红买基金

1. 题目描述

2. 思路分析

• 每个符合要求的基金都可以选择买或不买，最后减去买0枝的方案。

3. 代码实现

def solve():
    n, x, y = RI()
    p = 0
    for _ in range(n):
        a, b = RI()
        if a >= x and b <= y:
            p += 1
    print((pow(2, p, MOD) - 1) % MOD)
1
2
3
4
5
6
7
8

小红的密码修改

链接: 小红的密码修改

1. 题目描述

2. 思路分析

• 由于本身输入是合法的，那么对于每个字符可以修改成同类字符；如果本类字符有超过1个，那么还可以修改成其它类字符。

3. 代码实现

def solve():
    s, = RS()
    n = len(s)

    up = low = dig = sp = 0
    for c in s:
        if c.isdigit():
            dig += 1
        elif c.islower():
            low += 1
        elif c.isupper():
            up += 1
        else:
            sp += 1
    ans = 0
    for c in s:
        if c.isdigit():
            if dig == 1:
                ans += 9
            else:
                ans += 9 + 26 + 26 + 4
        elif c.islower():
            if low == 1:
                ans += 25
            else:
                ans += 10 + 25 + 26 + 4
        elif c.isupper():
            if up == 1:
                ans += 25
            else:
                ans += 10 + 25 + 26 + 4
        else:
            if sp == 1:
                ans += 3
            else:
                ans += 10 + 26 + 26 + 3
        ans %= MOD
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

小红的转账设置方式

链接: 小红的转账设置方式

1. 题目描述

2. 思路分析

题目给出了n个点和m条无向边，要求调整为有向边，且使得所有点到1的最短路最短。问有几种方案。
1

• 先无脑求出最短路，然后考虑每条边的调整方案。
• 不在最短路上的边，两个方向都可以，乘2即可。注意不要算两次。
• 在最短路上的边，连接u，v，那么一定有dis[u]+1==dis[v]，那么我们从v的角度考虑。
  • u可能对应着p条边(点)，都可以使u的最短路最短，那么保留一条或多条都可以。
  • 一共有2^p-1种方案。

3. 代码实现

def solve():
    n, m = RI()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = RI()
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    dis = [n] * n
    dis[0] = 0
    q = deque([0])
    while q:
        u = q.popleft()
        d = dis[u] + 1
        for v in g[u]:
            if d < dis[v]:
                dis[v] = d
                q.append(v)  

    ans = 1
    for u, es in enumerate(g):  # 枚举每个点最短路
        p = 0
        for v in es:
            if dis[v] + 1 == dis[u]:  # u可以从v来
                p += 1
            elif dis[u] + 1 != dis[v] and u > v:  # 如果v从u来，则这条边去v里再计算；否则这条边不在最短路上，可以任意方向，但注意只计算一次
                ans = ans * 2 % MOD

        if p > 1:  # u有超过1条边来，那么只有全是反边的情况不可以
            ans = ans * (pow(2, p, MOD) - 1) % MOD
       
    print(sum(dis) % MOD, ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

小红打boss

链接: 小红打boss

1. 题目描述

2. 思路分析

• 首先每个技能至少都可以打成单倍伤害。
• 然后考虑哪些技能可以双倍，优先让伤害高的技能双倍。
• 那么可以用一个其它种类的小技能垫一下，然后用大的消耗。
• 显然，最多有n//2个技能可以双倍，但如果最多的那类技能超过了一半，那就不行了：垫的数量不够。
• 因此最多有min(n//2,n-max(cnt))个技能可以双倍。

3. 代码实现

def solve():
    n, = RI()
    c = []  # 存所有分数
    cnt = Counter()  # 分别计数
    for _ in range(n):
        a, b = RS()
        c.append(int(b))
        cnt[a[0]] += 1
    ans = sum(c)
    c.sort(reverse=True)
    ans += sum(c[:min(n // 2, n - max(cnt.values()))])  # 最多取一半;如果有一个太多，只能取不到一半
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12

六、参考链接

• 无