Burnling's Blog
0%

220405总结

发表于 更新于

T1 潜水员

和普通的01背包的不不同点在于，有两个状态需要转移：氧气量和氮气量

令 $f(u,v)$ 为拥有 $u$ 升氧气 $v$ 升氮气所需的最小气缸重量

想到 最小 二字，自然能想到用 $\min$ 去转移

其他的就和普通的背包相同了

$f(u,v)=\displaystyle\min_{i=1}^k(f(u-a_i,v-b_i)+c_i)$

T2 分组背包

裸的板子题

枚举背包编号，先确定背包限制大小，再选物品去更新

1
2
3
4
5
6
7
8
9
10
for(int i = 1;i<=T;i++){
	for(int j = V;j>=0;j--){
		for(int k = 1;k<=BAGn[i][0];k++){
			int ind = BAGn[i][k];
			if(j >= A[ind].w){
				dp[j] = max(dp[j],dp[j-A[ind].w]+A[ind].v);
			}
		}
	}
}

T3 小球

因为是一棵满二叉树，所以节点 $i$ 的左孩子是 $2i$ ，右孩子是 $2i+1$

设这棵树的高度为 $dep$

则所有的叶子节点的编号都在 $[2^{dep-1},2^{dep})$ 这个区间里面

模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool tree[2000000];

leaL = 1<<(D-1);

while(I--){
	k = 1;
	while(k < leaL){
		ad = 0;
		if(tree[k]) ad = 1;
		tree[k] = !tree[k];
		k = (k << 1) | ad;
	}
	res = k;
}
printf("%d",res);