宝物筛选（C++，多重背包）

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为

W

$W$

的采集车，洞穴里总共有

n

$n$

种宝物，每种宝物的价值为

v_i

$v_{i}$

，重量为

w_i

$w_{i}$

，每种宝物有

m_i

$m_{i}$

件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数

n

$n$

和

W

$W$

，分别表示宝物种数和采集车的最大载重。

接下来

n

$n$

行每行三个整数

v_i,w_i,m_i

$v_{i}, w_{i}, m_{i}$

。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

样例输出 #1

提示

对于

30\%

$30%$

的数据，

≤

∑

≤

n\leq \sum m_i\leq 10^4

$n \leq \sum m_{i} \leq 1 0^{4}$

，

≤

0\le W\leq 10^3

$0 \leq W \leq 1 0^{3}$

。

对于

100\%

$100%$

的数据，

≤

∑

≤

n\leq \sum m_i \leq 10^5

$n \leq \sum m_{i} \leq 1 0^{5}$

，

≤

0\le W\leq 4\times 10^4

$0 \leq W \leq 4 \times 1 0^{4}$

，

≤

100

1\leq n\le 100

$1 \leq n \leq 100$

。

解题思路：

典型的多重背包问题

采用二进制拆分，然后套用01背包动态规划即可

~~（本来说到这里就打算结束了，但感觉太水了就再说点二进制拆分）~~

接下来简单说明一下二进制拆分：

尝试将一个物品拆分为1、2、4、8…份，拆分后的物品看作一个物品

如果最后一次不满足拆分条件，但是仍然有剩余，那么剩余的部分看作一个物品

比如说有8个物品，拆分为1、2、4、1

思路很好理解吧，但是与常规的二进制还是有一点不同的，所以容易让人迷惑

让人迷惑通常是（

~~反正这是我感到迷惑的~~

）为什么这样的二进制拆分与拆分之前是等价的

以有10个物品为例，拆分为1、2、4、3

考虑到01背包的动态规划会尝试每一种可能的组合

也就是说，只要1、2、4、3能够表示0~10的每一个数字，拆分前后就是等价的

可以自行尝试一下，1、2、4、3确实能够表示0~10之间的任意一个数字，但这并不是巧合

1）对于刚好被拆分的数字，如15

15能够拆分为1、2、4、8，不必证明，1、2、4、8一定能够表示0~15之间的任意一个数字

2）而对于不能被刚好拆分的数字

n

$n$

来说，如

∈

[

]

n \in [8, 14]

$n \in [8, 14]$

最后一次拆分出的物品一定在

]

[1,7]

$[1, 7]$

范围内

而前三次拆分出的物品一定可以表示出

]

[0,7]

$[0, 7]$

之内的任意一个数字

已经可以看出来了吧？把最后一次拆分出的数字当作简单的偏移量即可

那么二进制拆分就说明完啦，AC代码如下

//多重背包
#include <iostream>
using namespace std;
const int max_sum_m = 1e5;
const int max_n = 100;
const int max_W = 4e4;

struct treasure { int v, w, m; }t_arr[max_n + 1];//拆分前
struct treasure bin_t_arr[max_sum_m + 1];//拆分后
long long dp[max_W + 1];//滚动数组

//二进制拆分
int bin_disassembly(int n) {
	int index = 1;
	for (int i = 1; i <= n; i++) {
		int power = 1;
		while (t_arr[i].m) {
			bin_t_arr[index].m = 1;
			bin_t_arr[index].v = t_arr[i].v * power;
			bin_t_arr[index].w = t_arr[i].w * power;
			t_arr[i].m -= power;
			power *= 2; index++;
			if (t_arr[i].m < power) {
				bin_t_arr[index].m = 1;
				bin_t_arr[index].v = t_arr[i].v * t_arr[i].m;
				bin_t_arr[index].w = t_arr[i].w * t_arr[i].m;
				index++;
				break;
			}
		}
	}
	return index;//返回物品数量
}

int main() {
	int n, W, v, w, m;
	cin >> n >> W;
	for (int i = 1; i <= n; i++) {
		cin >> t_arr[i].v >> t_arr[i].w >> t_arr[i].m;
	}
	int ret = bin_disassembly(n);
	for (int i = 1; i < ret; i++) {//动态规划
		for (int j = W; j >= bin_t_arr[i].w; j--) {
			dp[j] = max(dp[j], dp[j - bin_t_arr[i].w] + bin_t_arr[i].v);
		}
	}
	cout << dp[W] << endl;
	return 0;
}

尴尬的数字（C++，数学）

题目背景

Bessie 刚刚学会了不同进制数之间的转换，但是她总是犯错误，因为她的两个前蹄不能轻松的握住钢笔。

题目描述

每当 Bessie 将一个数转换成新的进制时，她总会写错一位数字。例如，她将 14 转化成 2 进制数，正确的结果是 1110，但她可能会写成 0110 或 1111。Bessie 从不会意外的增加或删减数字，所以她可能会写出以 0 开头的错误数字。

给出 Bessie 转换后

N

$N$

的 2 进制形式和 3 进制形式，请计算出

N

$N$

的正确数值（用十进制表示）。

N

$N$

可能会达到

10^9

$1 0^{9}$

，输入数据保证解的存在唯一性。

输入格式

第一行，

N

$N$

的 2 进制表示（有一位是错误的数字）。

第二行，

N

$N$

的 3 进制表示（有一位是错误的数字）。

输出格式

N

$N$

的正确值。

样例 #1

样例输入 #1

1010
212

样例输出 #1

解题思路：

最容易想到的就是暴力枚举，将二进制的每一种可能错误与三进制的每一种可能错误比较，相同则为答案

这里不对这种方法进行说明，采用另一种方法

利用异或
^
的性质，枚举每一种二进制的可能错误

考虑到在三进制只错一位的前提下，如果得出的
N
是正确值

那么将
abs(正确数 - 三进制错误数)
写成

∗

i * 3^j

$i * 3^{j}$

的形式，一定可以得到

i < 3

$i < 3$

从而得出时间复杂度接近
o(n)
的算法

AC代码如下

#include <iostream>
#include <cmath>
using namespace std;

long long binTodec(string str) {//二进制转十进制
	int len = int(str.size());
	int power = 1;
	long long sum = 0;
	for (int i = len - 1; i >= 0; i--) {
		sum += power * (str[i] - '0');
		power *= 2;
	}
	return sum;
}

long long threeTodec(string str) {//三进制转十进制
	int len = int(str.size());
	int power = 1;
	long long sum = 0;
	for (int i = len - 1; i >= 0; i--) {
		sum += power * (str[i] - '0');
		power *= 3;
	}
	return sum;
}

int main() {
	string str_1, str_2;
	cin >> str_1 >> str_2;
	long long t_1 = binTodec(str_1);
	long long t_2 = threeTodec(str_2);
	int power = pow(2, int(str_1.size()) - 1);
	for (int i = 0; i < int(str_1.size()); i++, power /= 2) {//枚举二进制错误
		long long t_3, t_4;
		if ((str_1[i] - '0') ^ 1)//异或操作
			t_3 = abs((t_4 = t_1 + power) - t_2);
		else
			t_3 = abs((t_4 = t_1 - power) - t_2);
		while (t_3 % 3 == 0) t_3 /= 3;//检测是否正确
		if (t_3 < 3) {
			cout << t_4 << endl;
			break;
		}
	}
	return 0;
}

这里简单说明一下，为什么不可能有第二个
N
使得判定条件成立

~~众所周知~~

，暴力枚举一定可以得出正确答案

如果有第二个
N
可以使得差值写成

∗

i * 3^j

$i * 3^{j}$

，那么对于暴力枚举，这个
N
同样也是正确的

因为暴力枚举可以把三进制的

j+1

$j + 1$

位修改，使得二进制修改后的值与之相等

[传智杯 #4 初赛] 小卡和质数（C++，数学）

题目背景

小卡最近迷上了质数，所以他想到了一个和质数有关的问题来考考你。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

题目描述

小卡有

(

≤

)

T(1\le T\le 10^5)

$T (1 \leq T \leq 1 0^{5})$

组询问。每次询问给你两个正整数

(

≤

)

x,y(1\le x,y\le 10^9)

$x, y (1 \leq x, y \leq 1 0^{9})$

。

小卡想知道，第

x

$x$

个质数和第

y

$y$

个质数是否满足

⊕

p_x \oplus p_y =1

$p_{x} \oplus p_{y} = 1$

，即第

x

$x$

个质数和第

y

$y$

个质数的异或值是否是

1

$1$

。

输入格式

第一行一个正整数

T

$T$

，表示询问的数量。

接下来

T

$T$

行，每行两个正整数

x,y

$x, y$

，表示询问的是第

x

$x$

个质数和第

y

$y$

个质数。

输出格式

T

$T$

行，每行一个字符串
Yes
或
No
，分别表示两个质数的异或值是

1

$1$

或不是

1

$1$

。

样例 #1

样例输入 #1

样例输出 #1

Yes
No
No
No

解题思路：

异或
^
：对位操作，同则为假、不同为真

因为

1

$1$

的位模式为

0001

$0001$

，则
x
和
y
应该符合两个条件：

1）最低位上必须一个为

0

$0$

，一个为

1

$1$

2）除了最低位不同，其余位均相同

对于1），二进制表示最低位为

0

$0$

的必然为偶数，而质数里有一个也只能有一个偶数就是

2

$2$

再考虑2），

2

$2$

的二进制表示为

0010

$0010$

，可以推出另外一个数的二进制表示为

0011

$0011$

，也就是

3

$3$

emm对没错，就只有这一种情况，AC代码如下

#include <iostream>
using namespace std;

int main() {
	int num_1, num_2, T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> num_1 >> num_2;
		if (num_1 == 1 && num_2 == 2 || num_1 == 2 && num_2 == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}

原文链接：https://blog.csdn.net/m0_74036684/article/details/128729024

宝物筛选（C++，多重背包）

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

解题思路：

尴尬的数字（C++，数学）

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

解题思路：

[传智杯 #4 初赛] 小卡和质数（C++，数学）

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

解题思路：

你可能也喜欢