讨论/题目交流/🏆 第 159 场力扣周赛/
🏆 第 159 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

缀点成线
删除子文件夹
替换子串得到平衡字符串
规划兼职工作

match 159

P1

判断N个点是否在一条直线上

根据初中数学,两点确认一条直线,用前两个点先算出直线:
y = kx+b,然后把后面的点带进去验证就行了。

不过这道题我煞笔了,一直在担心斜率k的精度问题,如果k是只能用分数表示的无限不循环小数,
那么float64的精度肯定有问题。为了避免这个问题,只能用分数来表示斜率k,而不能简单地做除法。

这种做法就让复杂度高了一个数量级……大佬们4题都AK了,我才刚提交第一道题。

看题解的话,这道题不用考虑这么麻烦,直接裸的除法就行了,不过我依然认为应该这样做,只是数据太弱了

P2

这道题就是个裸的前缀树的题目。每个节点是一个词,不断构建这棵树。最后遍历这棵树时,每颗子树遍历到第一个terminal节点即可

P3

这道题使用滑动窗口。由于最终每个字母必须出现n/4次,也就意味着,当某个字符出现次数大于n/4,一定要把它替换成别的字符。
举例来说,如果Q多了2个,R多了4个,我们要找到一个区间,这个区间必须包含至少2个Q和4个R,这样才能通过替换使得最终所有字符都是n/4个。我们的目标就是找到一个最短的这样的子区间。
因此我们可以先统计出哪些字符多了,然后从头开始先找到一个包含了所有多余字符的区间,按照这个长度向右滑动。滑动过程中,根据情况不断收缩左边界,过程中记录最优值就行了

P4

可以非常容易地想到n^2的地推公式,首先对任务按照结束时间进行排序,f[i]表示前i个任务中一定要做第i个任务能获得的最大值。
那么f[i] = max(f[j]+value[i])其中end[j] <= start[i]。但是看看数据规模,这种方法肯定TLE了,因此需要优化。
这里的一个关键问题是,可以转移过来的上一个状态必须满足end[j] <= start[i]。如果我们直接用时间做状态呢?
f[i]表示0..=i时刻,能够获取得的最大价值。此时,第i时刻要么刚好完成一个任务(j,i,v)并且获得价值v,所以f[i] = max(f[j]+v, f[i])
或者,i时刻什么也不做,f[i] = f[i-1]。但是这又面临两个问题:

  • i太大,10^9
  • 怎么知道有任务在i时刻结束

针对第一个问题,我们发现由于数据量是10^4,因此如果我们可以对每个任务的时间进行一个离散化,比如:
(10, 1000) (15, 10000) 映射成 (0, 2) (1, 3)
针对第二个问题,当把时间离散化后,我们就可以用Vec<end_time><Vec<(start_time, value)>>来保存时刻i有哪些任务结束。当然,为了节约空间,实际上也可以用HashMap<end_time><Vec<(start_time, value)>>来存

这样,这个问题就变成了一个类似于01背包的简单dp

展开全部 16 讨论