先放题目
1979. 找出数组的最大公约数
1980. 找出不同的二进制字符串
1981. 最小化目标值与所选元素的差
1982. 从子集的和还原数组
A题B题
俩签到题
A题:排序之后求个gcd
B题:bitset + next_permutation + to_string 循环nums.find() 找不到的就return
C题
本题的一眼解有点像 16. 最接近的三数之和 的改编。但仔细思考之后发现,如果使用双指针,在70*70的矩阵下面,时间复杂度是$O(n^{68})$。
接着便想到到了之前学过的背包九讲中有一种分组背包问题。
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。
这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。
K求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
于是DP直接A掉。
D题
我太菜了,不会:(