第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解
Powered by:NEFU AB-IN
文章目录
博主个人的暴力题解,基本很少是正解,求轻喷
Python大学A组 个人暴力题解
-
试题 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: 分糖果
-
题意
-
思路
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: 三国游戏
-
题意
-
思路
直接没思路,一看到数据范围瞬间怂了,脑子里想的只有暴力,这个题是留到最后写的,就写了个最差的二进制枚举
-
代码
# 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: 平均
-
题意
-
思路
唯一一个觉得暴力是正解的题
就是每个数最多就是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: 翻转
-
题意
-
思路
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写的线段树也优化不了多少 -
代码
# 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: 阶乘的和
-
题意
-
思路
还是暴力,思路就是可以把共因子都提出来,剩下的加和,从提出来的共同的因子的最大值开始,让加和除以它,直到不能除了,就是答案
其中,用哈希表记录用过的阶乘值,预处理一些阶乘值 -
代码
# 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: 奇怪的数
-
题意
-
思路
还是暴力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: 子树的大小
-
题意
-
思路
没时间想了,感觉暴力都很麻烦
-
代码
-
-
试题 J: 反异或 01 串
-
题意
-
思路
没时间想了,就特判了几种情况
-
代码
# 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))
-