Leetcode【LC周赛赛后发布会】Weekly Contest 363

今天题目比上次简单多了。

第一题：
  Python求1-bit就转换成字符串来count其中一的数量。

第二题：
  最重要的条件是每个人都要happy。所以排序后，
  最后一个被选的要小于选了的人数
  而最小的那个没选的要大于选了的人数。

第三题：
  简单而复杂的实现题。每个机器二分搜索一下就可以。

第四题：
  每个数可以转化为若干质数。注意偶数个质数不必考虑。比如48=【2，2，2，2,3】 相当于【3】
  而600 = 【2,2,2,3,5,5】相当于【2,3】。
  所以把每个数转换成奇数个的素数的乘积。
  48转成3。600转成6.
  求最大的和。

  

amocaki 发表于 2023-9-17 02:00
第四题如果precalculate所有符合条件的的pairs算不算作弊呢。数学不好想不到这么巧的方法。笨一点的是找到 ...

把每个数的平方因子去掉的话，貌似复杂度是 O(n * (1 + 1/4 + 1/9 + 1/16 ...)) <= O(2n) (  (1 + 1/4 + 1/9 + 1/16 +.. + 1/(n^2)) <= 1 + (1/x^2从1到无穷的定积分）=2）  ，比分解质因数看奇偶的O(n^1.5)还好一点

lz好厉害～ 第二题一开始用dfs tle想半天怎么剪枝 最后一刻发现排序即可

我觉得第四题比第二题还简单

第四题如果precalculate所有符合条件的的pairs算不算作弊呢。数学不好想不到这么巧的方法。笨一点的是找到所有平方数，然后每个分解pairs。这样是O(n1.5)。