Aquabet

Talk is cheap. Show me the code.

0%

Leetcode第255场周赛 解题报告

先放题目

  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题

  我太菜了,不会:(

代码

  详见我的github仓库