加罚时 44:26,不过排名比想像中好很多
排 50 名,史上最好的一次
https://i.imgur.com/Cl32lr7.png
1. Merge Two 2D Arrays by Summing Values
用 map 收集起来就好,而且 map 会自己帮你排好序
反正 n <= 200, O(nlogn) 绰绰有余,不需要麻烦的用 two-pointer
2. Minimum Operations to Reduce an Integer to 0
随手写了一个每个 node 有 34 条边的 BFS
(+1, +2, ..., +2^16, -1, ..., -2^16)
但 TLE 了,蛮意外的 应该是因为我用 set 而不是 vector 来存走过的点
改成只有 +- least significant bit 才过
仔细想想,好像可以分成若干 1111 的 group
如果长度 >= 2 就花两步,如果长度 == 1 则只花一步
3. Count the Number of Square-Free Subsets
会被 > 1 的平方数整除等价于会被某个质数的平方整除
例如会被 a^2 整除,a 的所有质因子的平方还是可以整除
因为 nums[i] <= 30,用手算可以发现 <= 30 的有 10 个质数:
[2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29]
想要保持以上十个数的平方都不能整除的话
质因子分解以后上面出现的次数要 <= 1
因此只会有 2^10 总共 1024 种状态
n <= 1000 所以 dp 做状态转移即可
状态转移:
oldstate | bit