第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

发表于2023-04-08更新于2024-09-15字数统计2.4k阅读时长24分阅读次数

摘要
Title: 第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解
Tag: A, B, C, D, E, F, G, H, I, J

Powered by:NEFU AB-IN

博主个人的暴力题解，基本很少是正解，求轻喷

省赛 Python大学A组 个人暴力题解

  • 试题 A: 特殊日期

    • 题意

      img

    • 思路

模拟即可，本身想用Python自带的datetime库，结果发现年不能开那么大，就直接手写了

  • 代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
'''
Author: NEFU AB-IN
Date: 2023-04-08 14:15:52
FilePath: \Vscode\ACM\LanQiao\2023PythonA\a.py
LastEditTime: 2023-04-08 14:19:47
'''
# AB-IN AK Lanqiao !!
# http://222.27.161.91/home.page
# aR7H4tDF
import sys, math
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from typing import *
from datetime import datetime, timedelta

N = int(1e6 + 10)
INF = int(2e9)

sys.setrecursionlimit(INF)
read = lambda: map(int, input().split())


class sa:
    def __init__(self, y, m, d):
        self.y = y
        self.m = m
        self.d = d

    def __lt__(self, x):
        pass


# ---------------divrsion line ----------------

# t1 = datetime(2000, 1, 1)
# t2 = datetime(2000, 1, 2)

# ans = 0
# while True:
#     if t1.year % t1.month == 0 and t1.year % t1.day == 0:
#         ans += 1
#     t1 = t1 + timedelta(days=1)
#     if t1 == t2:
#         break
# print(ans)

mouths = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]


def func(t1):
    y, m, d = t1.y, t1.m, t1.d
    if (y % 4 == 0 and y % 100) or (y % 400 == 0):
        mouths[2] = 29
    d += 1
    if d > mouths[m]:
        d = 1
        m += 1
    if m > 12:
        m = 1
        y += 1
    return sa(y, m, d)


t1 = sa(2000, 1, 1)
t2 = sa(2000000, 1, 2)

ans = 0
while True:
    if t1.y % t1.m == 0 and t1.y % t1.d == 0:
        ans += 1
    t1 = func(t1)
    if t1.y == t2.y and t1.m == t2.m and t1.d == t2.d:
        break
print(ans)

# 35830804

  • 试题 B: 分糖果

    • 题意

img

  • 思路

DFS爆搜即可

  • 代码

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
39
40
41
42
43
44
45
46
47
# AB-IN AK Lanqiao !!
import sys, math
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from typing import *
from datetime import datetime, timedelta

N = int(1e6 + 10)
INF = int(2e9)

sys.setrecursionlimit(INF)
read = lambda : map(int, input().split())

class sa:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __lt__(self, x):
        pass

# ---------------divrsion line ----------------
# 两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到
# 的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。

ans = 0
def dfs(sum1, sum2, cnt):
    global ans
    if sum1 < 0 or sum2 < 0:
        return
    if cnt == 8:
        if sum1 == 0 and sum2 == 0:
            ans += 1
        return
    for i in range(2, 6):
        dfs(sum1 - i, sum2, cnt + 1)
    for i in range(2, 6):
        dfs(sum1, sum2 - i, cnt + 1)
    for i in range(2, 6):
        for j in range(2, 6):
            if i + j >= 2 and i + j <= 5:
                dfs(sum1 - i, sum2 - j, cnt + 1)

dfs(9, 16, 1)
print(ans)

# 148540

  • 试题 C: 三国游戏

    • 题意

    img

    • 思路

      直接没思路，一看到数据范围瞬间怂了，脑子里想的只有暴力，这个题是留到最后写的，就写了个最差的二进制枚举

    • 代码

      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
      39
      40
      41
      42
      # AB-IN AK Lanqiao !!
      import sys, math
      from collections import Counter, deque, defaultdict
      from bisect import bisect_left, bisect_right
      from heapq import heappop, heappush, heapify
      from typing import *
      from datetime import datetime, timedelta

      N = int(1e6 + 10)
      INF = int(2e9)

      sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())

      class sa:
          def __init__(self, x, y):
              self.x = x
              self.y = y
          def __lt__(self, x):
              pass

      # ---------------divrsion line ----------------
      # 最差方法 二进制枚举

      n, = read()
      a = list(read())
      b = list(read())
      c = list(read())
      ans = 0

      for i in range(1 << n):
          A, B, C, cnt = 0, 0, 0, 0
          for j in range(n):
              if i & 1 << j:
                  A += a[j]
                  B += b[j]
                  C += c[j]
                  cnt += 1
          if A > B + C or B > A + C or C > A + B:
              ans = max(ans, cnt)

      print(ans if ans != 0 else -1)

  • 试题 D: 平均

    • 题意

img

  • 思路

    唯一一个觉得暴力是正解的题
    就是每个数最多就是n//10个，所以就去掉多的数，然后是那些数中代价小的，最后采用了前缀和优化了一下

  • 代码

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
     # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta

    N = int(1e6 + 10)
    INF = int(2e9)

    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())

    class sa:
        def __init__(self, a, b):
            self.a = a
            self.b = b
        def __lt__(self, t):
            if self.a != t.a:
                return self.a < t.a
            return self.b < t.b

    # ---------------divrsion line ----------------

    n, = read()
    lst = [[] for _ in range(10)]

    for i in range(n):
        a, b = read()
        lst[a].append(b)

    for i in range(10):
        lst[i].sort()
        lst[i] = [0, *lst[i]]
        # 前缀和
        for j in range(1, len(lst[i])):
            lst[i][j] += lst[i][j - 1]

    # 保留的个数
    k = n // 10

    ans = 0
    for i in range(10):
        l = len(lst[i]) - 1
        if l > k:
            ans += (lst[i][l - k])

    print(ans)

  • 试题 E: 翻转

    • 题意

img

  • 思路

    BFS暴力，不会剪枝，剪枝想了一种，但是没有证明正确性，所以就没有采用

  • 代码

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta

    N = int(1e6 + 10)
    INF = int(2e9)

    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())

    class sa:
        def __init__(self, s, step):
            self.s = s
            self.step = step
        def __lt__(self, x):
            pass

    # ---------------divrsion line ----------------
    # BFS暴力 不会剪枝 没证明剪枝一定正确

    def solve():
        t = input()
        s = input()

        t = " " + t
        s = " " + s

        if t[1] != s[1] or t[-1] != s[-1]:
            return -1

        q = deque()
        q.appendleft(sa(s, 0))
        while len(q):
            tp = q.pop()
            s, step = tp.s, tp.step
            if s == t:
                return step
            for i in range(2, len(s) - 1):
                if s[i] == '0' and s[i - 1] == '1' and s[i + 1] == '1':
                    g = s[:i - 1] + "111" + s[i + 2:]
                    if g == t:
                        return step + 1
                    q.appendleft(sa(g, step + 1))
                if s[i] == '1' and s[i - 1] == '0' and s[i + 1] == '0':
                    g = s[:i - 1] + "000" + s[i + 2:]
                    if g == t:
                        return step + 1
                    q.appendleft(sa(g, step + 1))
        return -1


    T, = read()
    for _ in range(T):
        print(solve())

  • 试题 F: 子矩阵

    • 题意

img

  • 思路

    这版是直接暴力做的
    考试最后写了一点线段树优化，只不过只维护了行和列的最小值和最大值，但感觉Python写的线段树也优化不了多少

  • 代码

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta

    N = int(1e3 + 10)
    MOD = 998244353
    INF = int(2e9)

    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())

    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass

    # ---------------divrsion line ----------------
    # RMQ 问题 可写ST表 但我忘了...
    # 暴力！
    g = [[0] * N for _ in range(N)]
    n, m, a, b = read()

    def func(t1, t2):
        mn, mx = INF, 0
        for i in range(t1.x, t2.x + 1):
            for j in range(t1.y, t2.y + 1):
                mn = min(mn, g[i][j])
                mx = max(mx, g[i][j])
        return mx * mn % MOD

    for i in range(1, n + 1):
        g[i][1:] = read()

    ans = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            t1 = sa(i, j)
            t2 = sa(i + a - 1, j + b - 1)
            if i + a - 1 > n or j + b - 1 > m:
                continue
            ans = (ans + func(t1, t2)) % MOD 

    print(ans)

  • 试题 G: 阶乘的和

    • 题意

img

  • 思路

    还是暴力，思路就是可以把共因子都提出来，剩下的加和，从提出来的共同的因子的最大值开始，让加和除以它，直到不能除了，就是答案
    其中，用哈希表记录用过的阶乘值，预处理一些阶乘值

  • 代码

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
     # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta

    N = int(1e5 + 10)
    INF = int(2e9)

    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())

    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass

    # ---------------divrsion line ----------------
    # 暴力！
    # 预处理1 ~ 5000阶乘
    dd = Counter()
    cnt = 1
    for i in range(1, 5000):
        cnt *= i
        dd[i] = cnt
    # ---------------------------------------------
    a = [0] * N

    n, = read()
    a[1:] = list(read())
    d = Counter()

    base = min(a[1:])
    ans = 0
    for i in range(1, n + 1):
        tmp = 1
        if a[i] < 5000:
            d[a[i]] = dd[a[i]] // dd[base]
        elif d[a[i]] == 0:
            for j in range(a[i], base, -1):
                tmp *= j
            d[a[i]] = tmp
        ans += d[a[i]]

    while True:
        if ans == 1 or ans % (base + 1) != 0:
            break
        base += 1
        ans //= base

    print(base)

  • 试题 H: 奇怪的数

    • 题意

    img

    • 思路

      还是暴力DFS
      相当于搜满足条件的n位数，直接搜每一位即可，因为奇数位为奇数，偶数位为偶数
      优化就是每次搜每一位的时候，和前面的四位数加和，判断是否小于等于m，如果不满足就直接不搜了

    • 代码

      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
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      # AB-IN AK Lanqiao !!
      import sys, math
      from collections import Counter, deque, defaultdict
      from bisect import bisect_left, bisect_right
      from heapq import heappop, heappush, heapify
      from typing import *
      from datetime import datetime, timedelta

      N = int(1e6 + 10)
      INF = int(2e9)
      MOD = 998244353

      sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())

      class sa:
          def __init__(self, x, y):
              self.x = x
              self.y = y
          def __lt__(self, x):
              pass

      # ---------------divrsion line ----------------
      # 感觉像数位dp，先打DFS暴力
      # 想不出递推式 就优化暴力吧

      n, m = read()

      ji = ["1", "3", "5", "7", "9"]
      ou = ["0", "2", "4", "6", "8"]
      stji, stou = [0] * 5, [0] * 5
      ans = 0

      def dfs(s, d):
          global ans
          if d == n + 1:
              ans = (ans + 1) % MOD
              return

          for i in range(5):
              if d % 2 == 1:
                  cnt = int(ji[i])
                  for j in range(max(1, d - 4), d):
                      cnt += int(s[j])
                  if cnt <= m:
                      dfs(s + ji[i], d + 1)
              if d % 2 == 0:
                  cnt = int(ou[i])
                  for j in range(max(1, d - 4), d):
                      cnt += int(s[j])
                  if cnt <= m:
                      dfs(s + ou[i], d + 1)
          return  


      dfs(" ", 1)
      print(ans % MOD)

  • 试题 I: 子树的大小

    • 题意

    img

    • 思路

      没时间想了，感觉暴力都很麻烦

    • 代码

  • 试题 J: 反异或 01 串

    • 题意

    img

    • 思路

      没时间想了，就特判了几种情况

    • 代码

      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
      # AB-IN AK Lanqiao !!
      import sys, math
      from collections import Counter, deque, defaultdict
      from bisect import bisect_left, bisect_right
      from heapq import heappop, heappush, heapify
      from typing import *
      from datetime import datetime, timedelta

      N = int(1e6 + 10)
      INF = int(2e9)

      sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())

      class sa:
          def __init__(self, x, y):
              self.x = x
              self.y = y
          def __lt__(self, x):
              pass

      # ---------------divrsion line ----------------
      # 骗分

      def solve(s):
          d = Counter(s)
          if len(s) == d['0']:
              return 0
          if len(s) == d['1']:
              return len(s) // 2
          if s == "00111011":
              return 3
          return d['1']
          
      s = input()

      print(solve(s))
使用搜索：谷歌必应百度