D
🦐头题。本质就是划分子集，纯暴力。但其实没那么暴力，你得想到加来加去就相当于分成几堆，因为0^X=X，所以零对异或没影响。
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
|
N = int(input()) # 袋子数量
A = list(map(int, input().split())) # 每个石头的数量
ans = set() # 存储所有可能的异或和
def dfs(pos, B):
# 所有石头都处理完毕时
if pos == N:
x = 0
for b in B:
x ^= b # 计算当前状态的异或和
ans.add(x)
return
# 方案1: 将当前石头放入已有的袋子
for i in range(len(B)):
B[i] += A[pos] # 加入当前石头
dfs(pos + 1, B) # 递归处理下一个石头
B[i] -= A[pos] # 回溯还原
# 方案2: 放入新袋子
dfs(pos + 1, B + [A[pos]]) # 创建新袋子存放当前石头
dfs(0, []) # 从空状态开始搜索
print(len(ans)) # 输出不同异或和的数量
|
E
一眼dp。题解的背包什么玩意看不明白为啥又来了一个遍max，还是记录一下自己的。就是三个01背包，然后再枚举等于k的情况，复杂度完全够用。
1
2
3
4
5
6
7
|
# dp[c] = 在热量 c 内能获得的最大维生素值
def build_dp(arr):
dp = [0]*(X+1)
for (val, cal) in arr:
for c in range(X, cal-1, -1):
dp[c] = max(dp[c], dp[c-cal] + val)
return dp
|
然后我们就得到了三个背包的dp数组。X最大是5000，两层循环暴力直接过！
1
2
3
4
5
6
7
|
ans = 0
for i in range(1, X+1):
for j in range(1, X+1):
k = X - i - j
if k < 0:
break
ans = max(ans, min(dp1[i], dp2[j], dp3[k]))
|