最近比较忙,(指忙着看斗破)所以这次的周赛总结发的比较晚。
这次的难度相较于上一次,明显难了一些,自己只敲出来了两道。
第一题: 三个元素
一开始从题目描述来看,还感觉挺简单的,可真要开敲起来,第一时间竟然不知道如何下手。
然后注意到 n <= 3000 ,便以为可以靠暴力来写,就直接三层循环,然后就TL了。
不过很快我也意识到可以先利用pair存数与其下标,
接着对所有数排序,然后从第一个数开始进行判重,得到三个数的下标,成功AC。
不过听y总讲了其map的方法后,有种恍然大悟的感觉,为何要执着与 下标->数 , 有时也可考虑 数->下标 。
第二题: 收集卡片
这道题个人觉得很简单,自己的思路也很清晰,很流畅的AC了,就没什么好说的。
第三题: 集合操作
现在再回头看这道题,自己做的时候考虑的方法其实都不太对,不过听y总讲后,倒是明白了。
这道题需要明确3点:
1.子集s的最大值一定是集合S的最大值。
2.子集s最大值前面的数,一定是连续的。
3.加入一个数x后,对平均数t的影响(假设加入x后新的平均数为t'):
(1) x < t, x < t' < t
(2) x = t, t = t'
(3) x > t, t < t' < x
有了以上的知识后,写这道题就很简单了,只需一个指针j进行遍历就好。