第十四届蓝桥杯大赛软件组国赛 Python大学A组 个人暴力题解
摘要
Title: 第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解
Tag: A, B, C, D, E, F, G, H, I
Powered by:NEFU AB-IN
博主个人的暴力题解，基本很少是正解，求轻喷
代码是赛后凭着印象复原的，可能会有记错的
国赛 Python大学A组 个人暴力题解
-
A
-
思路
调日期库，模拟
-
代码
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
50from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(2e5 + 10)
M = 20
INF = int(2e9)
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
def check(st):
if str(st.year).count("1") or str(st.month).count("1") or str(st.day).count("1") or str(st.weekday() + 1).count("1"):
return True
else:
return False
st = datetime(year=2023, month=1, day=1)
ans = 0
while st.year == 2023:
# print(st.date())
if check(st):
ans += 5
else:
ans += 1
st = st + timedelta(days=1)
print(ans)
-
-
B
-
思路
模拟
-
代码
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
78
79
80
81
82from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(2e5 + 10)
M = 20
INF = int(2e9)
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
d = Counter(
{
0: "1111110",
1: "0110000",
2: "1101101",
3: "1111001",
4: "0110011",
5: "1011011",
6: "1011111",
7: "1110000",
8: "1111111",
9: "1111011"
}
)
ans = [
"0000011",
"1001011",
"0000001",
"0100001",
"0101011",
"0110110",
"1111111",
"0010110",
"0101001",
"0010110",
"1011100",
"0100110",
"1010000",
"0010011",
"0001111",
"0101101",
"0110101",
"1101010",
]
res = 1
for i in range(len(ans)):
cnt = 0
for j in range(10):
s, t = ans[i], d[j]
flag = 1
for k in range(len(s)):
if s[k] == '1' and t[k] == '0':
flag = 0
break
cnt += flag
res *= cnt
print(res)
-
-
C
-
思路
模拟
-
代码
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
47from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(2e5 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
n, = read()
def f(x):
ans = 0
x = str(x)
for i in x:
ans += int(i)
return ans
ans = 0
while n:
n -= f(n)
ans += 1
print(ans)
-
-
D
-
思路
排列组合 + 逆元
-
代码
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
49from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(1e5 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
MOD = 998244353
fact = AR(0)
def init():
fact[0] = 1
for i in range(1, N):
fact[i] = fact[i - 1] * i % MOD
init()
n, m = read()
a = n - 3 * m
b = m
fz = fact[a]
fm = pow(fact[a - b] * fact[b] % MOD, MOD - 2, MOD)
print(fz * fm * 10 % MOD)
-
-
E
-
思路
01背包
我写的不是正解，会有贪心的感觉 -
代码
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
64from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(5e3 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
w = AR(0)
n, a, b = read()
w[1:] = read()
def init(a, b):
w1, dpa, dpb, st = AR(0), AR(0), AR(0), AR(0)
dp = [[] for _ in range(N)]
for i in range(1, n + 1):
for j in range(a, w[i] - 1, -1):
if dpa[j - w[i]] + w[i] > dpa[j]:
dpa[j] = dpa[j - w[i]] + w[i]
dp[j] = dp[j - w[i]][:]
dp[j].append(i)
for i in dp[a]:
st[i] = 1
for i in range(1, n + 1):
if st[i] == 0:
w1[i] = w[i]
for i in range(1, n + 1):
for j in range(b, w1[i] - 1, -1):
if dpb[j - w1[i]] + w1[i] > dpb[j]:
dpb[j] = dpb[j - w1[i]] + w1[i]
return dpa[a] + dpb[b]
# ____先a后b
# ____先b后a
print(max(init(a, b), init(b, a)))
-
-
F
-
思路
DP + 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
N = int(1010)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
g = [AR(0) for _ in range(N)]
n, = read()
for i in range(1, n + 1):
g[i][1:] = read()
# 首先求每一行的每个点的可递增最长序列的长度，0代表走不动，1代表可走一格
# 首先求往右的
dpr, dpl = [AR(0) for _ in range(N)], [AR(0) for _ in range(N)]
for i in range(1, n + 1):
for j in range(n - 1, 0, -1):
if g[i][j] < g[i][j + 1]:
dpr[i][j] = dpr[i][j + 1] + 1
else:
dpr[i][j] = 0
for j in range(1, n + 1):
if g[i][j] < g[i][j - 1]:
dpl[i][j] = dpl[i][j - 1] + 1
else:
dpl[i][j] = 0
dist = [AR(INF) for _ in range(N)]
q = deque()
dx = [1, 0]
dy = [0, 1]
def bfs():
dist[1][1] = 0
q.appendleft(sa(1, 1))
while len(q):
point = q.pop()
x, y = point.x, point.y
for i in range(2):
x1 = x + dx[i]
y1 = y + dy[i]
if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
continue
if dist[x1][y1] > dist[x][y] + 1:
dist[x1][y1] = dist[x][y] + 1
if x1 == n and y1 == n:
return dist[x1][y1]
q.appendleft(sa(x1, y1))
l, r = dpl[x][y], dpr[x][y]
if l != 0:
for i in range(1, l + 1):
x1, y1 = x, y - i
if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
continue
if dist[x1][y1] > dist[x][y] + 1:
dist[x1][y1] = dist[x][y] + 1
if x1 == n and y1 == n:
return dist[x1][y1]
q.appendleft(sa(x1, y1))
if r != 0:
for i in range(1, r + 1):
x1, y1 = x, y + i
if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
continue
if dist[x1][y1] > dist[x][y] + 1:
dist[x1][y1] = dist[x][y] + 1
if x1 == n and y1 == n:
return dist[x1][y1]
q.appendleft(sa(x1, y1))
return dist[n][n]
print(bfs())
-
-
G
-
思路
至今没搞懂题意，是一个数只能取一次，还是一个数能取三次，如果能取三次，那么样例就不对，如果只能取一次，n给的范围能取到1，索性直接暴力了
-
代码
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
62from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(2e5 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
# 得出结论 这个数列只有两种数字 只有aab abb两种组合
# aab 满足 2 * a > b
# abb 满足 2 * b > a
# 问题转化为 将数组中的数字转换为a, b 代价最小
# 思路 二分a 找b
# 暴力版本
a = AR(0)
n, = read()
a[1:] = read()
ans = INF
def check(p, q):
# p为双边
cnt = 0
for i in range(1, n + 1):
cnt += min(abs(a[i] - p), abs(a[i] - q))
return cnt
l, r = min(a[1:]), max(a[1:])
for i in range(l, r + 1): # i双边
for j in range(l, r + 1):
if 2 * i > j and 2 * j > i:
ans = min(ans, check(i, j))
print(ans)
-
-
H
-
思路
不是特别会
BFS + dijkstra -
代码
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(1e6 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
g = [[] for _ in range(N)]
gg = [[] for _ in range(N)]
n, q = read()
color = AR(0)
def f(x, y, z):
dist = AR(INF)
dist[x] = 0
st = AR(0)
q = []
heappush(q, [0, x])
while q:
t = heappop(q)
v, dst = t[0], t[1]
if st[x]:
continue
st[x] = 1
for [v, w] in gg[x]:
if dist[v] > dist[x] + w:
dist[v] = dist[x] + w
heappush(q, [v, dist[v]])
for i in range(1, n + 1):
if dist[i] <= y:
color[i] = z
for i in range(1, n // 2 + 1):
g[i].append([i * 2, 1])
g[i].append([i * 2 + 1, 1])
g[i * 2].append([i, 1])
g[i * 2 + 1].append([i, 1])
def bfs(i, j):
st = AR(0)
st[i] = 1
q = deque()
q.appendleft([i, 0])
while len(q):
t = q.pop()
u, dst = t[0], t[1]
for [v, w] in g[u]:
if st[v] == 0:
q.appendleft([v, dst + w])
st[v] = 1
if v == j:
return dst + w
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if i == j:
gg[i].append([i, 0])
continue
ans = bfs(i, j)
gg[i].append([j, ans])
gg[j].append([i, ans])
lst = AR(0)
for i in range(q):
lst = list(read())
if len(lst) == 4:
x, y, z = lst[1], lst[2], lst[3]
f(x, y, z)
else:
print(color[lst[1]])
'''
6 6
1 1 1 1
2 3
1 5 2 2
2 4
2 1
2 3
'''
-
-
I
-
思路
不会
直接暴力 -
代码
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
44from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, ceil, gcd, sqrt, fabs
class sa:
def __init__(self, x , y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
N = int(2e5 + 10)
M = 20
INF = int(2e9)
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65
NTL = lambda x: ascii_uppercase[x]
AR = lambda x: [x] * N
# _____________________________________________________
a = AR(0)
n, p, q = read()
a[1:] = read()
ans = abs(a[p] - a[q])
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if i > p and j < q:
continue
b = sorted(a[i : j + 1])
an = a[:i] + b + a[j+1 :]
ans = max(ans, abs(an[p] - an[q]))
print(ans)
-