UCAS期末复习
UCAS期末复习：算法（卜东波）
UCAS期末复习
算法
1
A
这道题是要判断对于一个数组，是否存在一段子数组，数组和大于这段的最大值。那么要做这个判断需要计算两个东西，即区间和与区间最大值。为了速度，不能使用O(N^2)的暴力方法枚举i，j。应该考虑每个数做最大值时，能取到的区间和最大是多少。这等价于找右边前缀和最大值与左边前缀和最小值。以左侧为例，建立一个单调栈，即栈底到栈顶递减的栈，这样可以通过弹出栈顶元素来找到左侧第一个比当前值大的位置，该元素可以接管这些弹出元素保存的最小值，避免每次便利重复计算。这样每个元素最多出栈一次，算法是O(N)的。右侧同理，只需反过来找到最大的。代码如下：
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
import sys
def solve():
# 1. 快速 I/O 读取所有输入
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
try:
# 读取测试用例数量
t_str = next(iterator)
t = int(t_str)
except StopIteration:
return
results = []
for _ in range(t):
try:
# 读取当前数组长度 N
n = int(next(iterator))
# 读取 N 个数组元素
a = [int(next(iterator)) for _ in range(n)]
except StopIteration:
break
# 2. 计算前缀和数组 P
# P[i] 表示 a[0]...a[i-1] 的和
# P 长度为 n + 1，P[0] = 0
P = [0] * (n + 1)
for i in range(n):
P[i+1] = P[i] + a[i]
# 3. 单调栈 - 向左寻找管辖范围内的最小前缀和
# min_P_left[i] 存储的是：在 a[i] 作为最大值的左侧范围内，能取到的最小 P 值
min_P_left = [0] * n
stack_left = [] # 存储元组 (index_in_a, min_prefix_sum)
for i in range(n):
# 初始候选值：假设子数组只包含 a[i] 自己，那么起始 P 是 P[i]
current_min = P[i]
# 单调栈逻辑：如果当前元素 a[i] 大于等于栈顶元素
# 说明栈顶元素的管辖范围被 a[i] 吞并了
# 我们直接继承栈顶元素那个范围内的最小值
while stack_left and a[stack_left[-1][0]] <= a[i]:
_, popped_min = stack_left.pop()
current_min = min(current_min, popped_min)
min_P_left[i] = current_min
stack_left.append((i, current_min))
# 4. 单调栈 - 向右寻找管辖范围内的最大前缀和
# max_P_right[i] 存储的是：在 a[i] 作为最大值的右侧范围内，能取到的最大 P 值
max_P_right = [0] * n
stack_right = [] # 存储元组 (index_in_a, max_prefix_sum)
# 倒序遍历
for i in range(n - 1, -1, -1):
# 初始候选值：假设子数组只包含 a[i] 自己，那么结束 P 是 P[i+1]
current_max = P[i+1]
# 单调栈逻辑：注意这里用 < 而不是 <=，为了处理重复元素避免重复计算
# 保证一边是严格边界，一边是松边界
while stack_right and a[stack_right[-1][0]] < a[i]:
_, popped_max = stack_right.pop()
current_max = max(current_max, popped_max)
max_P_right[i] = current_max
stack_right.append((i, current_max))
# 5. 最终判定
# 只要存在一个 i，使得该范围内的最大子段和 > a[i]，则条件不满足
found_counter_example = False
for i in range(n):
# 子数组和 = P[end] - P[start]
# 我们找到了管辖范围内的 max(P[end]) 和 min(P[start])
max_subarray_sum = max_P_right[i] - min_P_left[i]
if max_subarray_sum > a[i]:
found_counter_example = True
break
if found_counter_example:
results.append("NO")
else:
results.append("YES")
# 一次性输出结果
print('\n'.join(results))
if __name__ == "__main__":
solve()
B
这道题是一个普通的二分算法，核心点在于如何计算区间内的目标点个数。核心在于每次不需要遍历区间查找，而是在二分的时候，就把目标点的区间按照mid划分成两部分，传递下去即可。（split = bisect.bisect_right(pts, mid, lo, hi)这一行就是再找pts数组中，lo，hi范围内第一个比mid大的数的坐标）代码如下：
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
import sys
import bisect
sys.setrecursionlimit(1 << 25)
input_data = sys.stdin.read().strip().split()
it = iter(input_data)
n = int(next(it))
k = int(next(it))
A = int(next(it))
B = int(next(it))
pts = [int(next(it)) for _ in range(k)]
pts.sort()
def solve(L, R, lo, hi):
"""处理区间[L,R]，pts[lo:hi]是其中的点。"""
cnt = hi - lo
if cnt == 0:
return A
length = R - L + 1
direct = B * cnt * length
if L == R:
return direct
mid = (L + R) >> 1
# 只做一次二分，把当前区间内的点按mid切到左右
split = bisect.bisect_right(pts, mid, lo, hi)
left = solve(L, mid, lo, split)
right = solve(mid + 1, R, split, hi)
return min(direct, left + right)
total_len = 1 << n
# 初始把全体点限定到[1, 2^n]（其实已保证）
ans = solve(1, total_len,
bisect.bisect_left(pts, 1),
bisect.bisect_right(pts, total_len))
print(ans)
C
这道题也是一个二分算法的题目，核心在于如何构造能得到最多的距离为2的点对。题目要求是有向无环图，我们可以约定点从小到大连边，那么就不会有环。观察要求不难发现$n(n-1)/2$是所有点对的个数，因此只需要让连的边尽可能少，因为有连边代表这两点距离为1。下面的构造可以使得除了点之间的距离不会超过二，那么只要边少于$n\log(n)$就行。构造方法是每次选一个点当中间点，二分。左半部分的点都指向中间点，中间点指向右半部分的点。再对每一半持续二分。每次链接n条边，最多log(n)次二分，因此边数不超过nlog(n)。代码如下：
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
def construct_dag_edges(n, L=1, R=None):
if R is None: # 初始调用时设置R=n
R = n
edges = []
# 递归终止：当区间内少于2个节点时，无需添加边
if L >= R:
return edges
# 选取中点作为枢纽节点
mid = (L + R) // 2
pivot = mid
# 左侧部分 [L, pivot-1] 中所有节点指向 pivot
for u in range(L, pivot):
edges.append((u, pivot))
# 枢纽 pivot 指向右侧部分 [pivot+1, R] 中所有节点
for v in range(pivot + 1, R + 1):
edges.append((pivot, v))
# 递归处理左、右两部分
edges += construct_dag_edges(n, L, pivot - 1)
edges += construct_dag_edges(n, pivot + 1, R)
return edges
# 读取输入
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
n = int(data[0])
# 构造边集
edges = construct_dag_edges(n)
m = len(edges)
# 输出边数
print(m)
# 输出每条边（保证无重复且符合拓扑顺序，无环）
for u, v in edges:
print(u, v)
D
题目要对一个范围内的数进行插点，如果直接模拟的话，会很耗时。注意到，在区间范围大小确定的情况下，插入的点数也是固定的，这为我们的二分提供了基础。在拿到一个数后，对其进行判断，如果这个大小之前解决过（用一个字典存储），就直接返回，否则二分进行，这样可以转化为对数级的时间复杂度。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
x = int(input())
memo = {}
def solve(ll,rr):
if (rr - ll) in memo:
return memo[(rr - ll)]
if rr - ll <= 3:
return 1
else:
mid = (ll + rr) // 2
memo[(rr - ll)] = solve(ll, mid) + solve(mid, rr)
return memo[(rr - ll)]
print(solve(1,x)+1 if x>2 else 1)
2
A
这道题要求得到合法序列的数量，是一个动态规划问题。如果只用长度作为标识无法确定状态，因此使用二维dp分别代表-1与1的个数。转移时考虑添加-1或1的情况。代码如下：
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(0,n+1):
dp[i][0] = 1
for i in range(1,n+1):
for j in range(1,i+1):
dp[i][j] = dp[i][j-1]
if i>j:
dp[i][j] += dp[i-1][j]
dp[0][0]=0
print(dp[n][n])
B
先动态规划找到最短路径，之后依次将路径上的点置0，重新计算最大路径，遍历循环后得到答案。代码如下：
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
108
109
110
111
112
113
114
115
116
117
import sys
# 增加递归深度限制（虽然本题是迭代DP，但在Python这也是好习惯）
sys.setrecursionlimit(5000)
def solve():
# 使用快读，一次性读取所有数据
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
try:
n = int(next(iterator))
m = int(next(iterator))
except StopIteration:
return
# 读取网格
grid = []
for _ in range(n):
row = []
for _ in range(m):
row.append(int(next(iterator)))
grid.append(row)
# 用列表模拟 C++ 中的全局向量 v
best_path = []
def cal_max(record_path=False):
"""
计算最大路径和
:param record_path: 是否记录路径到 best_path
:return: 最大路径和
"""
# 初始化 DP 数组，对应 C++ 的 vector<vector<long long>> dp
# 使用 -inf 处理边界，相当于 C++ 的 -1e18
neg_inf = float('-inf')
dp = [[neg_inf] * (m + 1) for _ in range(n + 1)]
# from_dir 记录路径来源: 0=Start, 1=From Up, 2=From Left
if record_path:
from_dir = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
val = grid[i-1][j-1]
# 起点特殊处理
if i == 1 and j == 1:
dp[i][j] = val
continue
# 获取上方和左方的值
up = dp[i-1][j] if i > 1 else neg_inf
left = dp[i][j-1] if j > 1 else neg_inf
# 状态转移
if up > left:
dp[i][j] = up + val
if record_path:
from_dir[i][j] = 1 # 1 代表从上方来 (i-1)
else:
dp[i][j] = left + val
if record_path:
from_dir[i][j] = 2 # 2 代表从左方来 (j-1)
# 路径回溯，对应 C++ 中的 if (record_path) 部分
if record_path:
best_path.clear()
x, y = n, m
while x >= 1 and y >= 1:
# 存入 0-based 坐标
best_path.append((x - 1, y - 1))
if x == 1 and y == 1:
break
direction = from_dir[x][y]
if direction == 1: # 来自上方
x -= 1
elif direction == 2: # 来自左方
y -= 1
else:
break
return dp[n][m]
# 1. 第一次计算，获取初始最大值并记录路径
initial_max = cal_max(record_path=True)
ans = initial_max
# 2. 遍历最优路径上的每一个点
for r, c in best_path:
# 暂存原值
tmp = grid[r][c]
# 将该点设为 0
grid[r][c] = 0
# 重新计算最大路径和 (不需要记录路径)
current_max = cal_max(record_path=False)
# 更新 ans：取所有情况中的最小值
if current_max < ans:
ans = current_max
# 恢复原值
grid[r][c] = tmp
# Python float转int输出，虽然本身计算都是整数
print(int(ans))
if __name__ == '__main__':
solve()
C
这道题求最大值和的最小值，采用动态规划算法求解。dp[n]表示在长度为n的时候的最大和最小值。转移方程为找dp[i]+(i到n的最大值)的最小值，i的范围为从i到n的和不超过m。但是每次向前遍历时间复杂度比较高python会超时，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
47
48
49
50
51
52
53
import sys
# 加速 IO
input = sys.stdin.read
def solve():
data = input().split()
if not data:
return
n = int(data[0])
m = int(data[1])
# 预处理 a，转为整数列表
a = []
idx = 2
for _ in range(n):
a.append(int(data[idx]))
idx += 1
# dp 数组初始化，使用大数代替 1e15
INF = 10**15
dp = [0] * (n + 1)
# dp[1] 单独处理或在循环中自然处理皆可，这里对应 C++ 的 dp[1] = a[0]
dp[1] = a[0]
for i in range(2, n + 1):
cur = i
total = 0
current_max = a[i-1]
min_temp = INF
while cur >= 1:
val = a[cur-1]
total += val
if total > m:
break
if val > current_max:
current_max = val
cost = dp[cur-1] + current_max
if cost < min_temp:
min_temp = cost
cur -= 1
dp[i] = min_temp
print(dp[n])
if __name__ == '__main__':
solve()
D
dp[i][j] 表示第i个牛的喂粮食的操作次数， 需要再计算到dp[i][j]的第二维度的时候用到前缀和，以及在n为偶数的时候，只需要考虑一种情况，因为都是等价的。使用PYTHON会超时，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
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
import sys
# 设置递归深度和整数转字符串的阈值，防止特殊情况（虽然这道题主要靠循环）
sys.setrecursionlimit(2000)
def solve():
# 使用 sys.stdin.read 加快读取速度
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
N = int(next(iterator))
# C++ 中 H 是 1-based (H[1]...H[N])
# 这里我们存为 0-based (H[0]...H[N-1])，处理循环时对应调整即可
H = []
for _ in range(N):
H.append(int(next(iterator)))
MOD = 10**9 + 7
# 对应 C++: min_element(H.begin() + 1, H.end())
minH = min(H)
ans = 0
# 最大的 H[i] 也就到 1000 左右（根据 C++ vector 大小推断）
# 但为了安全，我们根据实际情况动态处理，或者保持 1001 的限制
MAX_VAL = 1005
# 对应 C++ 外层循环: for (int t = 0; t <= minH; t++)
# 以及 break 条件: if(N % 2 == 0) break;
# 如果 N 是偶数，只执行 t=0 一次；如果是奇数，执行 0 到 minH
loop_range = range(1) if N % 2 == 0 else range(minH + 1)
for t in loop_range:
# dp 数组优化：
# C++ 使用二维数组 f[N+1][1001]，但每次只用到上一行 f[i-1]
# 所以我们只用一维数组 prev_dp 代表上一行，new_dp 代表当前行
# f[0][0] = 1
prev_dp = [0] * MAX_VAL
prev_dp[0] = 1
for i in range(N):
# C++ 中的 H[i] 对应这里的 H[i]
# 这里的 i 是从 0 到 N-1
# 计算前缀和
# C++: prefix[j + 1] = (prefix[j] + f[i - 1][j])
# 我们可以直接累加计算
prefix = [0] * (MAX_VAL + 1)
current_sum = 0
for j in range(MAX_VAL):
current_sum = (current_sum + prev_dp[j]) % MOD
prefix[j + 1] = current_sum
# 初始化当前行
new_dp = [0] * MAX_VAL
# 对应 C++: for (int x_i = 0; x_i <= H[i] - t; x_i++)
limit = H[i] - t
if limit < 0:
# 如果上限小于0，无法填充任何值，当前行全为0，且后续都会是0
prev_dp = [0] * MAX_VAL
break
# 逻辑转换：
# C++: max_x_prev = limit - x_i
# f[i][x_i] = prefix[max_x_prev + 1]
#
# 当 x_i = 0 时, max_x_prev = limit, 需要 prefix[limit + 1]
# 当 x_i = limit 时, max_x_prev = 0, 需要 prefix[1]
#
# 利用切片加速：我们需要 prefix[1] 到 prefix[limit+1] 的逆序部分
# Python 切片比 for 循环快很多
# 获取需要的片段并翻转
# 注意：prefix 长度足够，不需要担心越界，因为 limit <= H[i] <= 1000
slice_len = limit + 1
source_segment = prefix[1 : slice_len + 1]
# 将片段逆序赋值给 new_dp 的前 slice_len 个元素
new_dp[:slice_len] = source_segment[::-1]
# 更新 prev_dp
prev_dp = new_dp
# 累加答案: ans = (ans + f[N][0])
ans = (ans + prev_dp[0]) % MOD
print(ans)
if __name__ == '__main__':
solve()
3
A
采用动态规划+贪心算法求解，在遇到2的时候，保留可能得最短的两种情况，一直到下一个2或者结束为止。由于相同会消除，因此最终的路径一定只能是010101这种结构，因此状态只需用长度与栈顶表示。维持2种状态是因为对于0210这种可能会约到头的路径来说，贪心算法不能得到最优解。下面是代码实现：
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
import sys
def solve():
# 使用快速IO读取所有输入
input_data = sys.stdin.read().strip()
if not input_data:
return
# 这里的输入可能包含换行符，我们只取第一行如果不含空格的话，或者直接处理字符串
s = input_data.split()[0] if input_data else ""
if not s:
print(0)
return
# 状态定义: states[length] = mask
# Mask 定义:
# Bit 0 (1): 以 '0' 结尾
# Bit 1 (2): 以 '1' 结尾
# Bit 2 (4): 空栈
# 初始状态: 长度0，掩码4 (Empty)
states = {0: 4}
# 预先定义常量以加速访问
MASK_0 = 1 # stack ends with '0'
MASK_1 = 2 # stack ends with '1'
MASK_EMPTY = 4 # stack is empty
for char in s:
next_states = {}
# 确定当前字符可能的取值
# char '0' -> [0]
# char '1' -> [1]
# char '2' -> [0, 1]
possible_vals = []
if char == '0':
possible_vals = [0]
elif char == '1':
possible_vals = [1]
else: # char == '2'
possible_vals = [0, 1]
for val in possible_vals:
for length, mask in states.items():
# --- 情况 1: 当前是空栈 (检查 bit 2) ---
if mask & MASK_EMPTY:
new_len = 1
# 如果进0，结尾变0(mask 1)；如果进1，结尾变1(mask 2)
# 刚好对应 (1 << val)
new_mask = (1 << val)
next_states[new_len] = next_states.get(new_len, 0) | new_mask
# --- 情况 2: 当前栈顶是 '0' (检查 bit 0) ---
if mask & MASK_0:
if val == 0:
# '0' 碰 '0' -> 消除 (Pop)
new_len = length - 1
# 栈也是交替的 (...10)，消掉0后剩下1。如果消完长度为0则为空。
new_mask = MASK_EMPTY if new_len == 0 else MASK_1
next_states[new_len] = next_states.get(new_len, 0) | new_mask
else:
# '1' 碰 '0' -> 入栈 (Push)
new_len = length + 1
new_mask = MASK_1
next_states[new_len] = next_states.get(new_len, 0) | new_mask
# --- 情况 3: 当前栈顶是 '1' (检查 bit 1) ---
if mask & MASK_1:
if val == 1:
# '1' 碰 '1' -> 消除 (Pop)
new_len = length - 1
# 栈是交替的 (...01)，消掉1后剩下0。如果消完长度为0则为空。
new_mask = MASK_EMPTY if new_len == 0 else MASK_0
next_states[new_len] = next_states.get(new_len, 0) | new_mask
else:
# '0' 碰 '1' -> 入栈 (Push)
new_len = length + 1
new_mask = MASK_0
next_states[new_len] = next_states.get(new_len, 0) | new_mask
# --- 剪枝优化 (Pruning) ---
if not next_states:
# 理论上不会发生，除非输入非法导致无法转移
states = {}
break
# 获取最小长度
min_len = min(next_states.keys())
# 只保留 min_len 和 min_len + 2
# 原理：操作只会改变长度的奇偶性，且为了保留不同的栈顶可能性，只需保留次短路径
pruned_states = {}
pruned_states[min_len] = next_states[min_len]
if (min_len + 2) in next_states:
pruned_states[min_len + 2] = next_states[min_len + 2]
states = pruned_states
# 输出结果
print(min(states.keys()))
if __name__ == "__main__":
solve()
B
贪心算法，每次都选择数量最多的石头会导致超时，因为需要模拟每一块石头。因此我们需要找到一个更快的算法。发现只要数量最多的石头数量不超过其余石头之和加一，就可以满足条件。需要考虑边界条件，即如果数量最大的恰好是边界的石头，且处在边界条件（等于其余石头加一），也会false，需要分类讨论，代码如下：
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
def can_arrange(k, p, q, cnt):
# Switch to 0-index for convenience.
p -= 1
q -= 1
total = sum(cnt)
# Case 1: endpoints are different.
if p != q:
cnt_p = cnt[p] - 1
cnt_q = cnt[q] - 1
if cnt_p < 0 or cnt_q < 0:
return False
cnt[p] = cnt_p
cnt[q] = cnt_q
# Remaining stones after fixing the endpoints.
remaining = total - 2
# If nothing remains, trivially valid.
if remaining == 0:
return True
# If all remaining stones are a single color, that color must differ from both endpoints.
max_color = 0
max_idx = -1
for i, c in enumerate(cnt):
if c > max_color:
max_color = c
max_idx = i
if max_color > (remaining + 1) // 2:
return False
if max_color == (remaining + 1) // 2 and max_color>remaining/2:
if max_idx == p or max_idx == q:
return False
# # Edge safety: if every remaining stone is p or every remaining stone is q, the border would clash.
# if cnt_p == remaining or cnt_q == remaining:
# return False
return True
# Case 2: endpoints are the same (color p == q).
else:
if cnt[p] < 2:
return False
cnt[p] -= 2 # consume two endpoints
remaining = total - 2
if remaining == 0:
return False
# If all remaining stones are the same color, that color must differ from p.
max_color = 0
max_idx = -1
for i, c in enumerate(cnt):
if c > max_color:
max_color = c
max_idx = i
# if max_color == remaining:
# return max_idx != p
# Standard non-adjacent feasibility for a line of length `remaining`.
if max_color > (remaining + 1) // 2:
return False
if cnt[p] >= (remaining + 1) // 2:
return False
return True
def main():
k, p, q = map(int, input().split())
cnt = list(map(int, input().split()))
print(1 if can_arrange(k, p, q, cnt) else 0)
if __name__ == "__main__":
main()
C
首先将所有普通物品与鉴定后赚不到钱的物品卖了做本金，之后判断是否能买起卷轴，买得起就说明可以全部赚钱，否则只能把部分魔法物品直接卖掉。 至于卖哪些物品，用一个01背包问题的动态规划解决。（倒序遍历可以将二维压缩到一维）dp[j]表示赚到j的钱所需要的最少损失，最后用总钱数减去损失即为最终答案。代码如下：
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
def main():
n, p = map(int, input().split())
money = 0
magic = []
for i in range(n):
input_x = []
input_x = list(map(int, input().split()))
if len(input_x)==1:
money += input_x[0]
else:
earn = input_x[1] - input_x[0] - p
if earn <= 0:
money+= input_x[0]
else:
magic.append([input_x[0], earn])
magic.sort(key=lambda x: x[1], reverse=True)
if money >= p:
for x in magic:
money = money+ x[0] + x[1]
print(money)
else:
max_money= money
for x in magic:
max_money += x[0]
if max_money < p:
print(max_money)
return
else:
need = p-money
dp= [float('inf')]*(need+1)
dp[0]=0
all_earn = 0
for item in magic:
cost= item[0]
earn= item[1]
all_earn = all_earn + earn+cost
for j in range(need, 0, -1):
if j - cost >= 0:
dp[j]= min(dp[j], dp[j-cost]+earn)
else:
if dp[0]+earn < dp[j]:
dp[j]= dp[0]+earn
print(money + all_earn - dp[need])
if __name__ == "__main__":
main()
D
本题看似与排课问题类似，但是是环覆盖，衍生出来两个问题：1.如何将环断开成链 2.如何快速求解区间覆盖的最少区间数 首先，若不跨越边界，就添加这个区间，若跨越边界，就添加（r,l+n） 由于起始位置不固定，因此需要枚举所有可能的起始位置。之后在每一跳找到能到达最远的位置，直到覆盖到起始位置+n-1为止。这样的有个问题，可能需要跳许多次才能到终点，因此进行一次预处理，使用倍增思想预处理每个位置跳2^j次能到达的最远位置。这样每次查询从最坏的O(n)降到O(logn)。代码如下：
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
def main():
n, p = map(int, input().split())
edge = []
for i in range(p):
l,r=map(int, input().split())
edge.append((l,r))
if r < l:
edge.append((l,r+n))
else:
edge.append((l+n,r+n))
edge.sort(key=lambda x: x[1])
f = [[0] * (2*n+1) for _ in range(21)]
nxt = [i for i in range(2 * n + 2)]
# 2. 遍历边，只在起跑线标记最远终点
for l, r in edge:
# 这一步要根据题目断环成链的逻辑处理 l 和 r
# 假设 l 和 r 已经处理好是链上的坐标
# 比如：如果在位置 l-1 就能接到这个区间，那么 nxt[l-1] = r
nxt[l - 1] = max(nxt[l - 1], r)
# 3. 线性扫描，继承前面的最大值
for i in range(1, 2 * n + 1):
# 如果我能走到 i-1，那我肯定拥有 i-1 能跳到的最远距离
# 这一步把“在这个位置能用哪些区间”的搜索过程变成了查表
nxt[i] = max(nxt[i], nxt[i - 1])
# 4. 赋值给倍增数组
for i in range(1, 2 * n + 1):
f[0][i] = nxt[i]
for j in range(1,21):
for i in range(1,2*n+1):
f[j][i]=f[j-1][f[j-1][i]]
res = 1e6+1
for l,r in edge:
if l>n:
continue
len = 1
if r>=l+n:
res=min(res,len)
continue
for j in range(20,-1,-1):
if f[j][r]<l+n-1:
len += 1<<j
r=f[j][r]
if f[0][r]>=l+n-1:
res=min(res,len+1)
if res < 1e6+1:
print(res)
else:
print("impossible")
if __name__ == "__main__":
main()
4
A
本题使用最小费用最大流的方法求解，首先需要构建图，然后使用SPFA算法求解最小费用最大流。创建2n个节点分别代表新资源与旧资源，以及超级源点与超级汇点。连接边时需要注意容量与费用的设置。 spfa原理：
维护一个队列，初始时将源点加入队列，并将源点的距离设为0。然后不断从队列中取出节点，遍历其所有邻接边，尝试松弛这些边。如果发现通过当前节点可以使得某个邻接节点的距离更短，就更新该邻接节点的距离，并将其加入队列（如果不在队列中）。这个过程持续进行，直到队列为空为止。最终得到的距离数组即为从源点到各个节点的最短路径距离。为了实现最小费用最大流问题，还要维护每个节点的前驱，找到最短路径的可行的最大流，更新全图（减少正向流量，增加反向流量） 代码如下： ```python import sys from collections import deque
增加递归深度，防止深搜或特殊情况爆栈（虽然这里主要用迭代）
sys.setrecursionlimit(200000)
class Edge: def init(self, to, cap, cost, rev): self.to = to self.cap = cap self.cost = cost self.rev = rev # 反向边在 nodes[to] 中的下标
def solve(): # — 1. 修复输入处理 — input_data = sys.stdin.read().split() if not input_data: return
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
108
109
110
111
112
113
114
iterator = iter(input_data)
try:
N = int(next(iterator))
p = int(next(iterator))
m = int(next(iterator))
f = int(next(iterator))
n = int(next(iterator))
s = int(next(iterator))
require = [int(next(iterator)) for _ in range(N)]
except StopIteration:
return
# 源点 S, 汇点 T
S = 0
T = 2 * N + 1
graph = [[] for _ in range(T + 2)]
# --- 2. 修复加边逻辑（必须添加反向边） ---
def add_edge(u, v, cap, cost):
# 正向边: graph[u] 的最后一个元素
# 反向边: graph[v] 的最后一个元素
graph[u].append([v, cap, cost, len(graph[v])])
graph[v].append([u, 0, -cost, len(graph[u]) - 1])
# 建图
for i in range(1, N + 1):
ri = require[i-1]
# 节点定义：
# i: 第i天晚上（产出脏资源）
# i+N: 第i天早上（需要新资源）
supply_node = i
demand_node = i + N
# 1. 源点 -> 脏资源 (接收脏餐巾)
add_edge(S, supply_node, ri, 0)
# 2. 新资源 -> 汇点 (必须满足需求)
add_edge(demand_node, T, ri, 0)
# 3. 源点 -> 新资源 (直接购买)
add_edge(S, demand_node, float('inf'), p)
# 4. 脏资源延期 (留到明天)
if i < N:
add_edge(supply_node, supply_node + 1, float('inf'), 0)
# 5. 快洗
if i + m <= N:
add_edge(supply_node, demand_node + m, float('inf'), f)
# 6. 慢洗
if i + n <= N:
add_edge(supply_node, demand_node + n, float('inf'), s)
# --- 3. 标准 SPFA + MCMF ---
min_cost = 0
max_flow = 0
while True:
dist = [float('inf')] * (T + 2)
parent_node = [-1] * (T + 2)
parent_edge_idx = [-1] * (T + 2)
in_queue = [False] * (T + 2)
queue = deque([S])
dist[S] = 0
in_queue[S] = True
# SPFA 找最短路
while queue:
u = queue.popleft()
in_queue[u] = False
for idx, (v, cap, cost, rev) in enumerate(graph[u]):
if cap > 0 and dist[v] > dist[u] + cost:
dist[v] = dist[u] + cost
parent_node[v] = u
parent_edge_idx[v] = idx
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
if dist[T] == float('inf'):
break
# 寻找增广路上的最小流量
flow = float('inf')
curr = T
while curr != S:
p_node = parent_node[curr]
edge_idx = parent_edge_idx[curr]
flow = min(flow, graph[p_node][edge_idx][1]) # 1 is cap
curr = p_node
# 更新流量和费用
max_flow += flow
min_cost += flow * dist[T]
curr = T
while curr != S:
p_node = parent_node[curr]
edge_idx = parent_edge_idx[curr]
# 更新正向边
graph[p_node][edge_idx][1] -= flow
# 更新反向边 (通过 rev 索引直接找到)
rev_idx = graph[p_node][edge_idx][3]
graph[curr][rev_idx][1] += flow
curr = p_node
print(min_cost)
if name == ‘main’: solve()
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
### B
志愿者问题：这道题要求满足每天的最小志愿者数量，乍一看没法用MCMF解决，因为那个是约定上界，本题是下界。但我们可以用旁路思想做转化。在每一天的i到i+1之间添加一条容量为inf-need的边，然后从原点到汇点的出发与接受都是inf 的流量，并将所有志愿者都建立为旁路，从i到j+1.这样因为主干道的流量不到inf，只能被迫走有费用的旁路，从而实现了下界的要求。代码如下：
```python
import sys
from collections import deque
# 1. 增加大数定义，防止 overflow
inf = 10**18
class Edge:
def __init__(self, to, cap, cost, rev):
self.to = to
self.cap = cap
self.cost = cost
self.rev = rev
def spfa(nodes, S, T):
queue = deque([S])
in_queue = [False] * len(nodes)
in_queue[S] = True
dist = [inf] * len(nodes)
dist[S] = 0
prev_node = [-1] * len(nodes)
prev_edge = [-1] * len(nodes)
while queue:
u = queue.popleft()
in_queue[u] = False
for i, e in enumerate(nodes[u]):
# 只有剩余容量 > 0 且能使距离变短时才松弛
if e.cap > 0 and dist[e.to] > dist[u] + e.cost:
dist[e.to] = dist[u] + e.cost
prev_node[e.to] = u
prev_edge[e.to] = i
if not in_queue[e.to]:
queue.append(e.to)
in_queue[e.to] = True
# 如果汇点不可达，说明没流了
if dist[T] == inf:
return 0, 0
# 回溯找最大流
max_flow = inf
v = T
while v != S:
u = prev_node[v]
idx = prev_edge[v]
max_flow = min(max_flow, nodes[u][idx].cap)
v = u
# 更新流量
v = T
while v != S:
u = prev_node[v]
idx = prev_edge[v]
# 正向边减流
nodes[u][idx].cap -= max_flow
# 反向边加流 (找到反向边在对端列表中的位置)
rev_idx = nodes[u][idx].rev
nodes[v][rev_idx].cap += max_flow
v = u
return max_flow, max_flow * dist[T]
def solve():
# 使用 sys.stdin.read 统一读取，处理多行输入更稳健
input_data = sys.stdin.read().split()
if not input_data:
return
iterator = iter(input_data)
try:
n = int(next(iterator))
m = int(next(iterator))
need = [int(next(iterator)) for _ in range(n)]
except StopIteration:
return
# 节点规划：
# 0: 源点 S
# n+2: 汇点 T
# 1 ~ n+1: 天数节点
S = 0
T = n + 2
nodes = [[] for _ in range(T + 1)]
def add_edge(u, v, cap, cost):
# 正向边
nodes[u].append(Edge(v, cap, cost, len(nodes[v])))
# 反向边：容量必须为 0，费用取反
nodes[v].append(Edge(u, 0, -cost, len(nodes[u]) - 1))
# 1. 志愿者边 (S_j -> T_j + 1)
# 注意：输入是 start, end, cost
for _ in range(m):
u = int(next(iterator))
v = int(next(iterator))
w = int(next(iterator))
# 志愿者也是旁路，容量无限
if v + 1 <= n + 1:
add_edge(u, v + 1, inf, w)
else:
add_edge(u, n + 1, inf, w)
# 2. 人数限制边 (Main Channel)
# 对应 i -> i+1, 容量 inf - a[i]
for i in range(1, n + 1):
# need[i-1] 对应第 i 天的需求
add_edge(i, i + 1, inf - need[i-1], 0)
# 3. 源点 -> 第一天
add_edge(S, 1, inf, 0)
# 4. 第 n+1 天 -> 汇点
add_edge(n + 1, T, inf, 0)
total_cost = 0
while True:
flow, cost = spfa(nodes, S, T)
if flow == 0:
break
total_cost += cost
print(total_cost)
if __name__ == '__main__':
solve()
本文由作者按照 CC BY 4.0 进行授权