A 跑步计划
题意简述：小蓝计划在某天的日期或星期中出现数字"1"时跑5千米，否则只跑1千米。计算2023年全年跑步的总距离。
解题思路：使用Python的datetime模块遍历2023年的每一天，检查日期或星期中是否包含"1"。
代码：
B 残缺的数字
题意简述：给定一个有缺失数字的数，每个缺失位可能是0-9中的任意数字，问所有可能情况的数目。
解题思路：统计每个缺失位置的可能性数量，使用乘法原理计算总数。
代码：
C 整数变换
题意简述：每分钟数字会变为当前数字减去其各位数字之和，直到变为0，求变换次数。
解题思路：直接模拟变换过程，直到数字变为0。
代码：
1
2
3
4
5
6
7
|
n = int(input())
ans = 0
while n != 0:
tot = sum(int(ch) for ch in str(n))
n -= tot
ans += 1
print(ans)
|
D 2023
题意简述：构造特定条件的数字串，使用容斥原理计算。
解题思路：使用二进制反演处理容斥问题，预处理阶乘和逆元。
代码：
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
|
import math
N, maxn = 10**5+5, 10**5
fact, inv = [1]*N, [1]*N
mod = 998244353
def init():
for i in range(1, maxn+1):
fact[i] = fact[i-1] * i % mod
inv[maxn] = pow(fact[maxn], mod-2, mod)
for i in range(maxn-1, 0, -1):
inv[i] = inv[i+1] * (i+1) % mod
def comb(n, m):
if n < m:
return 0
return fact[n] * inv[m] % mod * inv[n-m] % mod
init()
n, m = map(int, input().split())
k = n // 4
ans = 0
for i in range(m, k+1):
ans = (ans + (-1)**(i-m) * comb(i, m) % mod * comb(n-3*i, i) % mod * pow(10, n-4*i, mod) % mod) % mod
print(ans)
|
E 火车运输
题意简述：将物品装入两个容量分别为a和b的火车，求能装载的最大总量。
解题思路：二维动态规划，状态表示当前两火车装载量。
代码：
1
2
3
4
5
6
7
8
9
10
11
|
n, a, b = map(int, input().split())
w = list(map(int, input().split()))
dp = [[0]*1005 for _ in range(1005)]
for weight in w:
for j in range(a, -1, -1):
for k in range(b, -1, -1):
if j >= weight:
dp[j][k] = max(dp[j][k], dp[j-weight][k] + weight)
if k >= weight:
dp[j][k] = max(dp[j][k], dp[j][k-weight] + weight)
print(dp[a][b])
|
F 走方格
题意简述：在n×n网格中从左上角到右下角，求最短步数。
解题思路：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
|
from collections import deque
n = int(input())
mp = [list(map(int, input().split())) for _ in range(n)]
vis = [[0]*n for _ in range(n)]
q = deque([(0, 0, 0)])
vis[0][0] = 1
while q:
x, y, t = q.popleft()
if x == n-1 and y == n-1:
print(t)
break
# 常规移动
if x+1 < n and not vis[x+1][y]:
vis[x+1][y] = 1
q.append((x+1, y, t+1))
if y+1 < n and not vis[x][y+1]:
vis[x][y+1] = 1
q.append((x, y+1, t+1))
# 特殊移动
for i in range(y+1, n):
if mp[x][i] < mp[x][i-1] and not vis[x][i]:
vis[x][i] = 1
q.append((x, i, t+1))
else:
break
for i in range(y-1, -1, -1):
if mp[x][i] < mp[x][i+1] and not vis[x][i]:
vis[x][i] = 1
q.append((x, i, t+1))
else:
break
|
G 等腰三角形
题意简述：分类讨论几何问题。
解题思路：待补充。
H 彩色二叉树
题意简述：在完全二叉树上进行染色操作和查询操作。
解题思路：利用完全二叉树性质，可以快速求出两点距离,然后由于染色具有覆盖性,故从后往前处理染色操作。
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
|
n, q = map(int, input().split())
history = []
def distance(a, b):
cnt = 0
while a != b:
if a > b:
a = a // 2
else:
b = b // 2
cnt += 1
return cnt
def query(node):
for i in range(len(history)-1, -1, -1):
x, y, z = history[i]
if distance(node, x) <= y:
return z
return 0
for _ in range(q):
cmd = list(map(int, input().split()))
if cmd[0] == 1:
history.append((cmd[1], cmd[2], cmd[3]))
else:
print(query(cmd[1]))
|
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
|
import heapq
n, p, q = map(int, input().split())
a = [0] + list(map(int, input().split()))
res = 0
# 处理初始区间[p,q]
max_heap = []
min_heap = []
for i in range(p, q+1):
heapq.heappush(max_heap, -a[i])
heapq.heappush(min_heap, a[i])
current_max = -max_heap[0]
current_min = min_heap[0]
res = max(res, current_max - current_min)
# 向右扩展
for i in range(q+1, n+1):
current_min = min(current_min, a[i])
heapq.heappush(max_heap, -a[i])
heapq.heappop(max_heap)
current_max = -max_heap[0]
res = max(res, current_max - current_min)
# 向左扩展
max_heap = [-a[i] for i in range(p, q+1)]
heapq.heapify(max_heap)
current_max = -max_heap[0]
current_min = min_heap[0]
for i in range(p-1, 0, -1):
current_max = max(current_max, a[i])
heapq.heappush(min_heap, a[i])
heapq.heappop(min_heap)
current_min = min_heap[0]
res = max(res, current_max - current_min)
print(res)
|
J 最长同类子串
题意简述：找两个字符串的最长子串，使得字符出现位置同类。
解题思路：字符串哈希（示例为30%暴力解法）。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
s, t = input(), input()
n, m = len(s), len(t)
def check(k):
for i in range(n-k+1):
for j in range(m-k+1):
pattern1 = [[] for _ in range(26)]
pattern2 = [[] for _ in range(26)]
for l in range(k):
pattern1[ord(s[i+l])-ord('a')].append(l)
pattern2[ord(t[j+l])-ord('a')].append(l)
if sorted(pattern1) == sorted(pattern2):
return True
return False
left, right = 0, min(n, m)
while left < right:
mid = (left + right + 1) // 2
if check(mid):
left = mid
else:
right = mid - 1
print(left)
|
