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

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

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

Powered by:NEFU AB-IN

文章目录

  • Python大学A组 个人暴力题解
    • 试题 A: 特殊日期
    • 试题 B: 分糖果
      • 题意
      • 思路
      • 代码
    • 试题 C: 三国游戏
      • 题意
      • 思路
      • 代码
    • 试题 D: 平均
      • 题意
      • 思路
      • 代码
    • 试题 E: 翻转
      • 题意
      • 思路
      • 代码
    • 试题 F: 子矩阵
      • 题意
      • 思路
      • 代码
    • 试题 G: 阶乘的和
      • 题意
      • 思路
      • 代码
    • 试题 H: 奇怪的数
      • 题意
      • 思路
      • 代码
    • 试题 I: 子树的大小
      • 题意
      • 思路
      • 代码
    • 试题 J: 反异或 01 串
      • 题意
      • 思路
      • 代码

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

Python大学A组 个人暴力题解

  • 试题 A: 特殊日期

    • 题意

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

    • 思路

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

    • 代码

      '''
      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, timedeltaN = 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 = yself.m = mself.d = ddef __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.dif (y % 4 == 0 and y % 100) or (y % 400 == 0):mouths[2] = 29else:mouths[2] = 28d += 1if d > mouths[m]:d = 1m += 1if m > 12:m = 1y += 1return 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 += 1t1 = func(t1)if t1.y == t2.y and t1.m == t2.m and t1.d == t2.d:break
      print(ans)# 35813063
      
  • 试题 B: 分糖果

    • 题意

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

    • 思路

      DFS爆搜即可

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, x):pass# ---------------divrsion line ----------------
      # 两种糖果分别有 9 个和 16 个,要全部分给 7 个小朋友,每个小朋友得到
      # 的糖果总数最少为 2 个最多为 5 个,问有多少种不同的分法。ans = 0
      def dfs(sum1, sum2, cnt):global ansif sum1 < 0 or sum2 < 0:returnif cnt == 8:if sum1 == 0 and sum2 == 0:ans += 1returnfor 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: 三国游戏

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, x):pass# ---------------divrsion line ----------------
      # 最差方法 二进制枚举n, = read()
      a = list(read())
      b = list(read())
      c = list(read())
      ans = 0for i in range(1 << n):A, B, C, cnt = 0, 0, 0, 0for j in range(n):if i & 1 << j:A += a[j]B += b[j]C += c[j]cnt += 1if A > B + C or B > A + C or C > A + B:ans = max(ans, cnt)print(ans if ans != 0 else -1)
      
  • 试题 D: 平均

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, a, b):self.a = aself.b = bdef __lt__(self, t):if self.a != t.a:return self.a < t.areturn 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 // 10ans = 0
      for i in range(10):l = len(lst[i]) - 1if l > k:ans += (lst[i][l - k])print(ans)
      
  • 试题 E: 翻转

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, s, step):self.s = sself.step = stepdef __lt__(self, x):pass# ---------------divrsion line ----------------
      # BFS暴力 不会剪枝 没证明剪枝一定正确def solve():t = input()s = input()t = " " + ts = " " + sif t[1] != s[1] or t[-1] != s[-1]:return -1q = deque()q.appendleft(sa(s, 0))while len(q):tp = q.pop()s, step = tp.s, tp.stepif s == t:return stepfor 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 + 1q.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 + 1q.appendleft(sa(g, step + 1))return -1T, = read()
      for _ in range(T):print(solve())
      
  • 试题 F: 子矩阵

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = 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 = xself.y = ydef __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, 0for 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 % MODfor 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:continueans = (ans + func(t1, t2)) % MOD print(ans)
      
  • 试题 G: 阶乘的和

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e5 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, x):pass# ---------------divrsion line ----------------
      # 暴力!
      # 预处理1 ~ 5000阶乘
      dd = Counter()
      cnt = 1
      for i in range(1, 5000):cnt *= idd[i] = cnt
      # ---------------------------------------------
      a = [0] * Nn, = read()
      a[1:] = list(read())
      d = Counter()base = min(a[1:])
      ans = 0
      for i in range(1, n + 1):tmp = 1if 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 *= jd[a[i]] = tmpans += d[a[i]]while True:if ans == 1 or ans % (base + 1) != 0:breakbase += 1ans //= baseprint(base)
      
  • 试题 H: 奇怪的数

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)
      MOD = 998244353sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, x, y):self.x = xself.y = ydef __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 = 0def dfs(s, d):global ansif d == n + 1:ans = (ans + 1) % MODreturnfor 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: 子树的大小

    • 题意

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

    • 思路

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

    • 代码

  • 试题 J: 反异或 01 串

    • 题意

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

    • 思路

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

    • 代码

      # 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, timedeltaN = int(1e6 + 10)
      INF = int(2e9)sys.setrecursionlimit(INF)
      read = lambda : map(int, input().split())class sa:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, x):pass# ---------------divrsion line ----------------
      # 骗分def solve(s):d = Counter(s)if len(s) == d['0']:return 0if len(s) == d['1']:return len(s) // 2if s == "00111011":return 3return d['1']s = input()print(solve(s))