欢迎光临散文网 会员登陆 & 注册

复盘|第336场周赛

2023-03-12 16:49 作者:UCLmsc  | 我要投稿

统计范围内的元音字符串数

重排数组以得到最大前缀分数

【排序+贪心】从大到小排序后,一开始前缀和加到最大,后面能够减的空间就越大,可以一边遍历一边计算大于0的前缀和数量。

统计美丽子数组数目

【前缀和+哈希表】每次操作要把nums[i]和nums[j]同一个比特位的1改成0等同于每次修改两个1,题中说执行若干次修改后,子数组能变成全为0的数,显然这个子数组每个有1的比特位上都有偶数个1,执行偶数次的1 ⊕ 1 = 0后,该比特位才能全零。把所有比特位合起来看,美丽子数组这等价于子数组的异或和等于 0(子数组每个数的每个比特位异或0等价于子数组异或为0)。问题转换为求异或和为0的子数组的个数。子数组的异或和等于两个前缀异或和的异或,异或为0说明两个前缀和是相等的,即求前缀异或和数组中所有相同的数对。

完成所有任务的最少时间

【排序+贪心】为了尽可能让多个任务同时运行,应该尽量延迟任务的执行,所以按照右端点排序,对于task[i]来说,它右侧的任务要么和它没交集,要么包含它的区间后缀。遍历排序后的任务,先统计区间内电脑运行时间点,如果小于duration,就尽量把运行时间安排在区间[start, end]的后缀上。


复盘|第336场周赛的评论 (共 条)

分享到微博请遵守国家法律